Jump PDA’s and Hierarchies of Deterministic Context-Free Languages

DOI10.1137/0203009zbMath0288.68031OpenAlexW2094441483MaRDI QIDQ4776849

Sheila A. Greibach

Publication date: 1974

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0203009

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

The hardest \(\operatorname{LL}(k)\) language ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The hardest language for grammars with context operators ⋮ The Hardest LL(k) Language ⋮ On hardest languages for one-dimensional cellular automata ⋮ Hardest languages for conjunctive and Boolean grammars ⋮ Non-prinicipalité du cylindre des langages à compteur ⋮ Le cylindre des langages linéaires ⋮ The Hardest Language for Conjunctive Grammars ⋮ On jump-deterministic pushdown automata ⋮ On hardest languages for one-dimensional cellular automata ⋮ Equivalence problems for deterministic context-free languages and monadic recursion schemes ⋮ On inverse deterministic pushdown transductions ⋮ Nondeterminism and Boolean operations in pda's ⋮ Opérations de cylindre et applications séquentielles gauches inverses ⋮ Une note sur le cylindre des langages déterministes ⋮ Générateurs algébriques et systèmes de paires iterantes ⋮ Remarks on multihead pushdown automata and multihead stack automata ⋮ New families of non real time dpda's and their decidability results