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

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

Review text

The general notion of look-ahead on pushdowns is used to prove that (1) the deterministic iterated pushdown languages are closed under complementation, (2) the deterministic iterated pushdown languages are properly included in the nondeterministic iterated pushdown languages; the counter example is a very simple linear context-free language, independent of the amount of iteration, (3) LL(k) iterated indexed grammars can be parsed by deterministic iterated pushdown automata, and (4) it is decidable whether an iterated indexed grammar is LL(k). Analogous results hold for iterated pushdown automata with regular look- ahead on the input, and LL-regular iterated indexed grammars.

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

• A generalized approach to formal languages
• A Note on Pushdown Store Automata and Regular Systems
• 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
• 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?)
• Indexed Grammars—An Extension of Context-Free Grammars
• IO and OI. II
• Ll-regular grammars
• LL-regular grammars
• LR-regular grammars - an extension of LR(k) grammars
• Macro tree transducers
• Nested Stack Automata
• On deterministic indexed languages
• On LL-regular grammars
• 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 equivalence problem for LL- and LR-regular grammars
• The IO- and OI-hierarchies
• Top-down tree transducers with regular look-ahead

Cited in

(11)

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