Formal grammars for turn-bounded deterministic context-free languages

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

Authors: 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

• Title not available (Why is that?)
• Title not available (Why is that?)
• Deterministic context free languages
• Title not available (Why is that?)
• An Infinite Hierarchy of Context-Free Languages
• The language theory of bounded context-switching
• On recursive and non-recursive trade-offs between finite-turn pushdown automata
• Finite-Turn Pushdown Automata
• The equivalence problem for deterministic finite-turn pushdown automata
• On the translation of languages from left to right
• On The Space Complexity Of Turn Bounded Pushdown Automata
• The Unsolvability of the Recognition of Linear Context-Free Languages
• Intersection and union hierarchies of deterministic context-free languages and pumping lemmas
• Finite turns and the regular closure of linear context-free languages
• Two iteration theorems for some families of languages
• A pumping lemma for deterministic context-free languages
• Title not available (Why is that?)
• Behavioral strengths and weaknesses of various models of limited automata
• A PUMPING CONDITION FOR ULTRALINEAR LANGUAGES

Cited In (3)

• Generalized forbidding grammars
• Finite turns and the regular closure of linear context-free languages
• On bounded interpretations of grammar forms

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

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