UNSOLVABILITY LEVELS OF OPERATION PROBLEMS FOR SUBCLASSES OF CONTEXT-FREE LANGUAGES
From MaRDI portal
Publication:5462115
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
Algorithmic undecidabilityArithmetical hierarchyLinear and deterministic context-free languagesOperations on languagesRoot and Power operation
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