Книга: Ondrej Lengal «An Efficient Finite Tree Automata Library»
|
Производитель: "LAP Lambert Academic Publishing" Numerous computer systems use dynamic control and data structures of unbounded size that often have the character of trees or 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 current 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... ISBN:9783659270697 Издательство: "LAP Lambert Academic Publishing" (2012)
ISBN: 9783659270697 |
См. также в других словарях:
Tree automaton — A tree automaton is a type of state machine. Tree automata deal with tree structures, rather than the strings of more conventional state machines. The following article deals with branching tree automata, which correspond to regular languages of… … Wikipedia
Radix tree — In computer science, a radix tree (also patricia trie or radix trie) is a space optimized trie data structure where each node with only one child is merged with its child. The result is that every internal node has at least two children. Unlike… … Wikipedia
Control table — This simple control table directs program flow according to the value of the single input variable. Each table entry holds a possible input value to be tested for equality (implied) and a relevant subroutine to perform in the action column. The… … Wikipedia
Algorithm — Flow chart of an algorithm (Euclid s algorithm) for calculating the greatest common divisor (g.c.d.) of two numbers a and b in locations named A and B. The algorithm proceeds by successive subtractions in two loops: IF the test B ≤ A yields yes… … Wikipedia
Actor model — In computer science, the Actor model is a mathematical model of concurrent computation that treats actors as the universal primitives of concurrent digital computation: in response to a message that it receives, an actor can make local decisions … Wikipedia
Hash table — Not to be confused with Hash list or Hash tree. Unordered map redirects here. For the proposed C++ class, see unordered map (C++). Hash Table Type unsorted dictionary Invented 1953 Time complexity in big O notation Average Worst case Space … Wikipedia
