Properties of deterministic top-down grammars

DOI10.1016/S0019-9958(70)90446-8zbMath0209.02703WikidataQ55921687 ScholiaQ55921687MaRDI QIDQ5609393

Daniel J. Rosenkrantz, Richard E. Stearns

Publication date: 1970

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

Mathematics Subject Classification ID

68Q42: Grammars and rewriting systems

Related Items

Polynomial time learning of simple deterministic languages via queries and a representative sample, Lower bounds on the size of deterministic parsers, On the complexity of LL(k) testing, New families of non real time dpda's and their decidability results, An extended direct branching algorithm for checking equivalence of deterministic pushdown automata, New techniques for proving the decidability of equivalence problem, Some results on subclass containment problems for special classes of dpda's related to nonsingular machines, The interchange or pump (di)lemmas for context-free languages, Power properties of NLC graph grammars with a polynomial membership problem, A method for transforming grammars into LL(k) form, A representation of trees by languages. II, Iteration theorems for families of strict deterministic languages, Two iteration theorems for the LL(k) languages, A parsing automata approach to LR theory, The equivalence problem for two dpda's, one of which is a finite-turn or one-counter machine, The equivalence problem for LL- and LR-regular grammars, A hierarchy of real-time deterministic languages and their equivalence, On LLP(k) grammars and languages, On the relationship between the LL(k) and LR(k) grammars, Deterministic one-counter automata, Attributed translations, LL(1) grammars supporting an efficient error handling, LL-regular grammars, Program equivalence and context-free grammars, On the equivalence, containment, and covering problems for the regular and context-free languages, A result on the equivalence problem for deterministic pushdown automata, The inclusion problem for simple languages, Normal forms of deterministic grammars, A direct algorithm for checking equivalence of LL(k) grammars, A representation of trees by languages. I, On equivalence and subclass containment problems for deterministic context-free languages, Two decidability results for deterministic pushdown automata, On equivalence of grammars through transformation trees, \(L(A)=L(B)\)? decidability results from complete formal systems, Decidability of the equivalence problem for deterministic pushdown automata, Synchronizable deterministic pushdown automata and the decidability of their equivalence, A metatheorem for undecidable properties of formal languages and its application to LRR and LLR grammars and languages, A direct branching algorithm for checking equivalence of strict deterministic vs. LL(k) grammars, Theory of formal grammars, Equivalence of deterministic pushdown automata revisited, Top-down syntax nalysis, LR-regular grammars - an extension of LR(k) grammars, A note on the number of states of the De Remer's recognizer, Recursive descent parsing for Boolean grammars, On comparingLL(k) andLR(k) grammars, Ll-regular grammars, Recursive-determinate abstract automata, Unnamed Item, A characterization ofLL(1) grammars, Simple context-free languages and free monadic recursion schemes, On jump-deterministic pushdown automata