Terminating Turing Machine Computations and the Complexity and/or decidability of Correspondence Problems, Grammars, and Program Schemes

DOI10.1145/62.2737zbMath0632.68048OpenAlexW2025340462MaRDI QIDQ3769965

Harry B. III Hunt

Publication date: 1984

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/62.2737

zbMATH Keywords

decision problemsdecidabilityundecidability resultsprogram schemesarbitrary context-free grammarscorrespondence problemslinear context- free grammarsnonrecursive complexitynonrecursive lower complexity boundsrelative economy of description

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Specification and verification (program logics, model checking, etc.) (68Q60)

Related Items (2)

Promise problems complete for complexity classes ⋮ The language intersection problem for non-recursive context-free grammars

This page was built for publication: Terminating Turing Machine Computations and the Complexity and/or decidability of Correspondence Problems, Grammars, and Program Schemes