Name
Abstract | ||
|---|---|---|
When reading an input tree, a bottom-up tree automaton is] “unaware” of where it is relative to the root. This problem is important to the efficient implementation of decision procedures for the Monadic Second-order Logic (M2L) on finite trees. In [KS97], it is shown how exponential state space blow-ups may occur in common situations. The analysis of the problem leads to the notion of guided tree automaton for combatting such explosions. The guided automaton is equipped with separate state spaces that are assigned by a top-down automaton, called the guide. |
Year | DOI | Venue |
|---|---|---|
1996 | 10.1007/3-540-63174-7_2 | Workshop on Implementing Automata |
Keywords | Field | DocType |
guided tree automata,state space,bottom up,top down | Discrete mathematics,Quantum finite automata,Combinatorics,Exponential function,Automaton,Algorithm,Binary decision diagram,Tree automaton,State space,Transition function,Mathematics,Monad (functional programming) | Conference |
Volume | ISSN | ISBN |
1260 | 0302-9743 | 3-540-63174-7 |
Citations | PageRank | References |
25 | 1.97 | 4 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Morten Biehl | 1 | 33 | 2.89 |
| Nils Klarlund | 2 | 645 | 65.43 |
| Theis Rauhe | 3 | 661 | 35.11 |