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

DOI10.1145/62.2737MaRDI QIDQ3769965zbMATH OpenOpenAlexFDO

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

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)

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

Cited in

(5)

• Promise problems complete for complexity classes
• The language intersection problem for non-recursive context-free grammars
• scientific article; zbMATH DE number 3845565 (Why is no real title available?)
• 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)