Pushdown tree automata

DOI10.1007/BF01744582zbMATH Open0524.68047OpenAlexW1965061701MaRDI QIDQ3036724FDOQ3036724

Authors: 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)

Cites Work

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

Cited In (30)

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

This page was built for publication: Pushdown tree automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3036724)