Detail publikace

An Efficient Finite Tree Automata Library: The Design of BDD-based Semi-symbolic Algorithms for Nondeterministic Finite Tree Automata

Originální název

An Efficient Finite Tree Automata Library: The Design of BDD-based Semi-symbolic Algorithms for Nondeterministic Finite Tree Automata

Anglický název

An Efficient Finite Tree Automata Library: The Design of BDD-based Semi-symbolic Algorithms for Nondeterministic Finite Tree Automata

Jazyk

en

Originální abstrakt

Numerous computer systems use dynamic control and data structures of unbounded size. These data structures have often the character of trees or they can be encoded as trees with some additional pointers. This is exploited by some currently intensively studied techniques of formal verification that represent an infinite number of states using a finite tree automaton. However, currently there is no tree automata library implementation that would provide an efficient and flexible support for such methods. Thus the aim of this Mas- ter's Thesis is to provide such a library. The present paper first describes the theoretical background of finite tree automata and regular tree languages. Then it surveys the cur- rent implementations of tree automata libraries and studies various verification techniques, outlining requirements for the library. Representation of a finite tree automaton and algo- rithms that perform standard language operations on this representation are proposed in the next part, which is followed by description of library implementation. Through a series of experiments it is shown that the library can compete with other available tree automata libraries, in certain areas being even significantly superior to them.

Anglický abstrakt

Numerous computer systems use dynamic control and data structures of unbounded size. These data structures have often the character of trees or they can be encoded as trees with some additional pointers. This is exploited by some currently intensively studied techniques of formal verification that represent an infinite number of states using a finite tree automaton. However, currently there is no tree automata library implementation that would provide an efficient and flexible support for such methods. Thus the aim of this Mas- ter's Thesis is to provide such a library. The present paper first describes the theoretical background of finite tree automata and regular tree languages. Then it surveys the cur- rent implementations of tree automata libraries and studies various verification techniques, outlining requirements for the library. Representation of a finite tree automaton and algo- rithms that perform standard language operations on this representation are proposed in the next part, which is followed by description of library implementation. Through a series of experiments it is shown that the library can compete with other available tree automata libraries, in certain areas being even significantly superior to them.

BibTex


@book{BUT97066,
  author="Ondřej {Lengál}",
  title="An Efficient Finite Tree Automata Library: The Design of BDD-based Semi-symbolic Algorithms for Nondeterministic Finite Tree Automata",
  annote="Numerous computer systems use dynamic control and data structures of unbounded
size. These data structures have often the character of trees or they can be
encoded as trees with some additional pointers. This is exploited by some
currently intensively studied techniques of formal verification that represent an
infinite number of states using a finite tree automaton. However, currently there
is no tree automata library implementation that would provide an efficient and
flexible support for such methods. Thus the aim of this Mas- ter's Thesis is to
provide such a library. The present paper first describes the theoretical
background of finite tree automata and regular tree languages. Then it surveys
the cur- rent implementations of tree automata libraries and studies various
verification techniques, outlining requirements for the library. Representation
of a finite tree automaton and algo- rithms that perform standard language
operations on this representation are proposed in the next part, which is
followed by description of library implementation. Through a series of
experiments it is shown that the library can compete with other available tree
automata libraries, in certain areas being even significantly superior to them.",
  address="Lambert Academic Publishing",
  chapter="97066",
  edition="NEUVEDEN",
  howpublished="print",
  institution="Lambert Academic Publishing",
  year="2012",
  month="october",
  pages="0--0",
  publisher="Lambert Academic Publishing",
  type="book"
}