The Turing degree of the inherent ambiguity problem for context-free languages

DOI10.1016/0304-3975(75)90013-4zbMath0313.68064OpenAlexW2019243334MaRDI QIDQ1220391

Walter J. Savitch, Ann Reedy

Publication date: 1975

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

Full work available at URL: https://doi.org/10.1016/0304-3975(75)90013-4

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items (3)

Iterated GSMs and CO-CFL ⋮ THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS ⋮ The minimum degree of recursively representable choice functions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A helpful result for proving inherent ambiguity

This page was built for publication: The Turing degree of the inherent ambiguity problem for context-free languages