Look-ahead on pushdowns

DOI10.1016/0890-5401(87)90014-9MaRDI QIDQ579952zbMATH OpenOpenAlexFDO

Authors Joost Engelfriet, Heiko Vogler

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)

Recommendations

• Properties of deterministic top down grammars
• scientific article; zbMATH DE number 17541
• A pumping lemma for deterministic context-free languages
• scientific article; zbMATH DE number 2150277
• Deterministic top-down tree transducers with iterated look-ahead

Cites work

• scientific article; zbMATH DE number 3821123 (Why is no real title available?)
• scientific article; zbMATH DE number 3924162 (Why is no real title available?)
• scientific article; zbMATH DE number 3972227 (Why is no real title available?)
• scientific article; zbMATH DE number 3786155 (Why is no real title available?)
• scientific article; zbMATH DE number 3478415 (Why is no real title available?)
• scientific article; zbMATH DE number 3495606 (Why is no real title available?)
• scientific article; zbMATH DE number 3509706 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• A Note on Pushdown Store Automata and Regular Systems
• A generalized approach to formal languages
• An automata-theoretical characterization of the OI-hierarchy
• Closure properties of deterministic indexed languages
• Fixed Point Languages, Equality Languages, and Representation of Recursively Enumerable Languages
• Full AFLs and nested iterated substitution
• IO and OI. II
• Indexed Grammars—An Extension of Context-Free Grammars
• LL-regular grammars
• LR-regular grammars - an extension of LR(k) grammars
• Ll-regular grammars
• Macro tree transducers
• Nested Stack Automata
• On LL-regular grammars
• On deterministic indexed languages
• On tree transducers for partial functions
• Parsers for indexed grammars
• Parsing macro grammars top down
• Pushdown machines for the macro tree transducer
• Some definitional suggestions for automata theory
• The IO- and OI-hierarchies
• The equivalence problem for LL- and LR-regular grammars
• Top-down tree transducers with regular look-ahead

Cited in

(11)

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

This page was built for publication: Look-ahead on pushdowns

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