The Turing degree of the inherent ambiguity problem for context-free languages
From MaRDI portal
Publication:1220391
DOI10.1016/0304-3975(75)90013-4zbMath0313.68064MaRDI QIDQ1220391
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
68Q25: Analysis of algorithms and problem complexity
68Q45: Formal languages and automata
03D30: Other degrees and reducibilities in computability and recursion theory
Related Items
THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS, The minimum degree of recursively representable choice functions, Iterated GSMs and CO-CFL
Cites Work