Pushdown tree automata

DOI10.1007/BF01744582zbMath0524.68047OpenAlexW1965061701MaRDI QIDQ3036724

Irène Guessarian

Publication date: 1983

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01744582

zbMATH Keywords

indexed languagescontext-free tree languagesdeterministic tree languagesGreibach tree languagestopdown pushdown tree automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Synchronized tree automata, Bottom-up tree pushdown automata: Classification and connection with rewrite systems, On two-way tree automata, Variétés d'automates descendants d'arbres infinis, Reductions in tree replacement systems, Pushdown machines for the macro tree transducer, Controlled Term Rewriting, Bottom-up tree pushdown automata and rewrite systems, High level tree transducers and iterated pushdown tree transducers, Yield-languages of two-way pushdown tree automata, Deterministic tree pushdown automata and monadic tree rewriting systems, Tree-walking-storage automata, Regular Approximation of Weighted Linear Context-Free Tree Languages, Restarting Tree Automata and Linear Context-Free Tree Languages, Tree-stack automata, Unnamed Item, Generalized automata on infinite trees and Muller-McNaughton's theorem, Decidability of equivalence for deterministic synchronized tree automata, Variable Tree Automata over Infinite Ranked Alphabets, A geometric hierarchy beyond context-free languages, Rigid tree automata and applications, Basic tree transducers, Automata on infinite objects and their applications to logic and programming, Linear weighted tree automata with storage and inverse linear tree homomorphisms, An Automata Characterisation for Multiple Context-Free Languages, The equivalence of bottom-up and top-down tree-to-graph transducers, Lattice-valued tree pushdown automata: pumping lemma and closure properties, Pushdown tree automata, algebraic tree systems, and algebraic tree series, Decidability of EDT0L structural equivalence, On two families of forests

Cites Work

• Extended macro grammars and stack controlled machines
• Algebraic semantics
• DPDA's in 'Atomic normal form' and applications to equivalence problems
• Formal computations of non deterministic recursive program schemes
• Une propri\'et\'e des forêts alg\'ebriques « de greibach \ra
• Bottom-up and top-down tree transformations— a comparison
• On jump-deterministic pushdown automata
• Indexed Grammars—An Extension of Context-Free Grammars
• Nested Stack Automata
• Generalized finite automata theory with an application to a decision problem of second-order logic
• Mappings and grammars on trees
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item