Formal grammars for turn-bounded deterministic context-free languages

DOI10.1007/978-3-031-17715-6_27OpenAlexW4312828186MaRDI QIDQ6164486

Tomoyuki Yamakami

Publication date: 28 July 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-031-17715-6_27

zbMATH Keywords

pumping lemmadeterministic context-free languagefinite turnsmetalinear grammarultralinear grammar

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Intersection and union hierarchies of deterministic context-free languages and pumping lemmas
• A pumping lemma for deterministic context-free languages
• Two iteration theorems for some families of languages
• Behavioral strengths and weaknesses of various models of limited automata
• Finite turns and the regular closure of linear context-free languages
• Insertion operations on deterministic reversal-bounded counter machines
• A PUMPING CONDITION FOR ULTRALINEAR LANGUAGES
• The Language Theory of Bounded Context-Switching
• On The Space Complexity Of Turn Bounded Pushdown Automata
• The equivalence problem for deterministic finite-turn pushdown automata
• Deterministic context free languages
• Finite-Turn Pushdown Automata
• The Unsolvability of the Recognition of Linear Context-Free Languages
• An Infinite Hierarchy of Context-Free Languages
• On the translation of languages from left to right
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Formal grammars for turn-bounded deterministic context-free languages