Abstract | ||
---|---|---|
This paper presents a new type of automaton called a tree pushdown automaton (a bottom-up tree automaton augmented with internal memory in the form of a tree, similar to the way a stack is added to a finite state machine to produce a pushdown automaton) and shows that the class of languages recognized by such automata is identical to the class of context-free tree languages. |
Year | DOI | Venue |
---|---|---|
1985 | 10.1016/0022-0000(85)90002-9 | J. Comput. Syst. Sci. |
Keywords | Field | DocType |
tree pushdown automaton,pushdown automata | Discrete mathematics,Embedded pushdown automaton,Two-way deterministic finite automaton,Deterministic automaton,Nested word,Computer science,Deterministic pushdown automaton,Theoretical computer science,Pushdown automaton,Tree automaton,Büchi automaton | Journal |
Volume | Issue | ISSN |
30 | 1 | Journal of Computer and System Sciences |
Citations | PageRank | References |
18 | 2.61 | 14 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Karl M. Schimpf | 1 | 39 | 4.32 |
Jean H. Gallier | 2 | 749 | 111.86 |