Computer Science – Formal Languages and Automata Theory
Scientific paper
2012-04-15
Computer Science
Formal Languages and Automata Theory
Master's thesis
Scientific paper
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 Master'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 current implementations of tree automata libraries and studies various verification techniques, outlining requirements for the library. Representation of a finite tree automaton and algorithms 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.
No associations
LandOfFree
An Efficient Finite Tree Automata Library does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with An Efficient Finite Tree Automata Library, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Efficient Finite Tree Automata Library will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-287394