UNSOLVABILITY LEVELS OF OPERATION PROBLEMS FOR SUBCLASSES OF CONTEXT-FREE LANGUAGES

DOI10.1142/S0129054105003078zbMath1097.68055OpenAlexW2074335890MaRDI QIDQ5462115

Markus Bolzer, Martin Kutrib, Henning Bordihn

Publication date: 1 August 2005

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054105003078

zbMATH Keywords

Algorithmic undecidabilityArithmetical hierarchyLinear and deterministic context-free languagesOperations on languagesRoot and Power operation

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items (3)

The Boolean closure of linear context-free languages ⋮ Decidability of operation problems for T0L languages and subclasses ⋮ Undecidability of Operation Problems for T0L Languages and Subclasses

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reversal-bounded multipushdown machines
• Control sets on context-free grammar forms
• \(L(A)=L(B)\)? decidability results from complete formal systems
• Context-freeness of the power of context-free languages is undecidable
• A Generalization of Ogden's Lemma
• Some Recursively Unsolvable Problems in ALGOL-Like Languages
• Inherent ambiguity of minimal linear grammars
• The Unsolvability of the Recognition of Linear Context-Free Languages
• Parenthesis Grammars
• Degrees of Unsolvability in Formal Grammars
• General Problems of Formal Grammars

This page was built for publication: UNSOLVABILITY LEVELS OF OPERATION PROBLEMS FOR SUBCLASSES OF CONTEXT-FREE LANGUAGES