Look-ahead on pushdowns

DOI10.1016/0890-5401(87)90014-9zbMath0625.68063OpenAlexW1995721258MaRDI QIDQ579952

Heiko Vogler, Joost Engelfriet

Publication date: 1987

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(87)90014-9

zbMATH Keywords

iterated pushdown automataiterated pushdown languagesLL(k) iterated indexed grammarslook-ahead on pushdowns

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Theory of compilers and interpreters (68N20)

Related Items

Transducers and the decidability of independence in free monoids ⋮ The structure of index sets and reduced indexed grammars ⋮ A hierarchy of deterministic top-down tree transformations ⋮ Iterated stack automata and complexity classes ⋮ Top-down tree transducers with two-way tree walking look-ahead ⋮ \(X\)-automata on \(\omega\)-words ⋮ Storage-to-tree transducers with look-ahead ⋮ Basic tree transducers ⋮ On store languages of language acceptors

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Macro tree transducers
• Pushdown machines for the macro tree transducer
• The IO- and OI-hierarchies
• The equivalence problem for LL- and LR-regular grammars
• LL-regular grammars
• A generalized approach to formal languages
• IO and OI. II
• On tree transducers for partial functions
• On LL-regular grammars
• Some definitional suggestions for automata theory
• LR-regular grammars - an extension of LR(k) grammars
• An automata-theoretical characterization of the OI-hierarchy
• On deterministic indexed languages
• Ll-regular grammars
• Closure properties of deterministic indexed languages
• Fixed Point Languages, Equality Languages, and Representation of Recursively Enumerable Languages
• Top-down tree transducers with regular look-ahead
• Parsers for indexed grammars
• Parsing macro grammars top down
• Indexed Grammars—An Extension of Context-Free Grammars
• A Note on Pushdown Store Automata and Regular Systems
• Nested Stack Automata
• Full AFLs and nested iterated substitution