Simulation of Turing machines by a left-linear rewrite rule

DOI10.1007/3-540-51081-8_103MaRDI QIDQ5055715zbMATH OpenOpenAlexFDO

Authors Max Dauchet

Publication date 9 December 2022

Published in Rewriting Techniques and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-51081-8_103

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Classical models of computation (Turing machines, etc.) (68Q04) Grammars and rewriting systems (68Q42)

Recommendations

• Simulation of Turing machines by a regular rewrite rule
• Automated Deduction – CADE-20
• scientific article; zbMATH DE number 4060699
• Simple termination is difficult
• scientific article; zbMATH DE number 1183250

Cites work

• scientific article; zbMATH DE number 3860380 (Why is no real title available?)
• scientific article; zbMATH DE number 3978424 (Why is no real title available?)
• scientific article; zbMATH DE number 4060699 (Why is no real title available?)
• Thue systems as rewriting systems

Cited in

(17)

• Simulation of Turing machines by a regular rewrite rule
• Some undecidability results concerning the property of preserving regularity
• Decision problems for semi-Thue systems with a few rules
• On termination of confluent one-rule string-rewriting systems
• scientific article; zbMATH DE number 1735649 (Why is no real title available?)
• scientific article; zbMATH DE number 786490 (Why is no real title available?)
• scientific article; zbMATH DE number 1396672 (Why is no real title available?)
• Decidability of confluence and termination of monadic term rewriting systems
• Open problems in rewriting
• Linear interpretations by counting patterns
• More problems in rewriting
• A complete characterization of termination of 0p 1q→1r 0s
• Decidable approximations of term rewriting systems
• Type removal in term rewriting
• Termination of term rewriting by interpretation
• Some undecidable termination problems for semi-Thue systems
• Simulation of operational semantics of machine instructions

This page was built for publication: Simulation of Turing machines by a left-linear rewrite rule

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