Context-freeness of the power of context-free languages is undecidable

DOI10.1016/J.TCS.2003.08.005zbMath1072.68054OpenAlexW2092786128MaRDI QIDQ1826642

Henning Bordihn

Publication date: 6 August 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2003.08.005

zbMATH Keywords

Context-free languagesAlgorithmic undecidabilityPower of languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Undecidability and degrees of sets of sentences (03D35)

Related Items (1)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Context-freeness of the power of context-free languages is undecidable