MonographLENGÁL Ondřej. An Efficient Finite Tree Automata Library: The Design of BDDbased Semisymbolic Algorithms for Nondeterministic Finite Tree Automata. Saarbrücken: Lambert Academic Publishing, 2012. ISBN 9783659270697.  Publication language:  english 

Original title:  An Efficient Finite Tree Automata Library: The Design of BDDbased Semisymbolic Algorithms for Nondeterministic Finite Tree Automata 

Title (cs):  Efektivní knihovna pro práci s konečnými stromovými automaty: návrh semisymbolických algoritmů pro práci s nedeterministickými konečnými stromovými automaty, jež jsou založeny na BDD 

Pages:  64 

Place:  Saarbrücken, DE 

Year:  2012 

ISBN:  9783659270697 

Publisher:  Lambert Academic Publishing 

Keywords 

tree automata, formal verification, abstract regular tree model checking, binary decision diagrams, multiterminal binary decision diagrams

Annotation 

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{
author = {Ond{\v{r}}ej Leng{\'{a}}l},
title = {An Efficient Finite Tree Automata Library: The
Design of BDDbased Semisymbolic Algorithms for
Nondeterministic Finite Tree Automata},
pages = 64,
year = 2012,
location = {Saarbr{\"{u}}cken, DE},
publisher = {Lambert Academic Publishing},
ISBN = {9783659270697},
language = {english},
url = {http://www.fit.vutbr.cz/research/view_pub.php.en?id=10206}
} 
