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

DOI10.1145/62.2737zbMATH Open0632.68048OpenAlexW2025340462MaRDI QIDQ3769965FDOQ3769965

Authors: H. 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

Recommendations

• scientific article; zbMATH DE number 3845565
• scientific article; zbMATH DE number 1738663
• Deciding the inequivalence of context-free grammars with 1-letter terminal alphapet is \(\sum ^ p_ 2\)-complete
• Decision problems for semi-Thue systems with a few rules
• The complexity of equivalence problems for commutative grammars

zbMATH Keywords

decidabilitydecision problemsundecidability resultsprogram schemesarbitrary context-free grammarscorrespondence problemslinear context- free grammarsnonrecursive complexitynonrecursive lower complexity boundsrelative economy of description

Mathematics Subject Classification ID

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

Cited In (5)

• Promise problems complete for complexity classes
• The language intersection problem for non-recursive context-free grammars
• Title not available (Why is that?)
• On the termination and structural termination problems for counter machines with incrementing errors
• On the termination problem for counter machines with incrementing errors

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3769965)