Terminating Turing Machine Computations and the Complexity and/or decidability of Correspondence Problems, Grammars, and Program Schemes
DOI10.1145/62.2737zbMath0632.68048OpenAlexW2025340462MaRDI QIDQ3769965
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
decision problemsdecidabilityundecidability resultsprogram schemesarbitrary context-free grammarscorrespondence problemslinear context- free grammarsnonrecursive complexitynonrecursive lower complexity boundsrelative economy of description
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Specification and verification (program logics, model checking, etc.) (68Q60)
Related Items (2)
This page was built for publication: Terminating Turing Machine Computations and the Complexity and/or decidability of Correspondence Problems, Grammars, and Program Schemes