Word problem for deterministic and reversible semi-Thue systems

DOI10.1007/S00233-013-9550-3MaRDI QIDQ2247995zbMATH OpenOpenAlexFDO

Authors Vesa Halava, Tero Harju

Publication date 30 June 2014

Published in Semigroup Forum (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00233-013-9550-3

zbMATH Keywords

undecidabilityword problemdeterministicreversiblesemi-Thue system

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Thue and Post systems, etc. (03D03) Free semigroups, generators and relations, word problems (20M05) Undecidability and degrees of sets of sentences (03D35)

Recommendations

• Decision problems for semi-Thue systems with a few rules
• On reduced thue systems
• scientific article; zbMATH DE number 1615237
• Deterministic semi-Thue systems and variants of Post correspondence problem
• Some undecidable termination problems for semi-Thue systems

Cites work

• scientific article; zbMATH DE number 3142911 (Why is no real title available?)
• scientific article; zbMATH DE number 3976343 (Why is no real title available?)
• scientific article; zbMATH DE number 3550181 (Why is no real title available?)
• scientific article; zbMATH DE number 3301426 (Why is no real title available?)
• scientific article; zbMATH DE number 3302312 (Why is no real title available?)
• scientific article; zbMATH DE number 3305031 (Why is no real title available?)
• scientific article; zbMATH DE number 3307572 (Why is no real title available?)
• scientific article; zbMATH DE number 3047078 (Why is no real title available?)
• A note on Post's correspondence problem
• Decision problems for semi-Thue systems with a few rules
• Logical Reversibility of Computation
• Noneffective regularity of equality languages and bounded delay morphisms
• Recursive unsolvability of a problem of Thue

Cited in

(15)

• The undecidability of self-embedding for finite semi-Thue and Thue systems
• On a method for proving exact bounds on derivational complexity in Thue systems
• Deterministic semi-Thue systems and variants of Post correspondence problem
• Decision problems for semi-Thue systems with a few rules
• scientific article; zbMATH DE number 1615237 (Why is no real title available?)
• A finite Thue system with decidable word problem and without equivalent finite canonical system
• Recursive unsolvability of a problem of Thue
• scientific article; zbMATH DE number 4114608 (Why is no real title available?)
• Almost all one-rule Thue systems have decidable word problems
• On the \(n\)-permutation Post correspondence problem
• Small Semi-Thue System Universal with Respect to the Termination Problem
• scientific article; zbMATH DE number 4009838 (Why is no real title available?)
• The word matching problem is undecidable for finite special string-rewriting systems that are confluent
• New proof for the undecidability of the circular PCP
• The Thue problem and logical specifications of derivation in formal systems

This page was built for publication: Word problem for deterministic and reversible semi-Thue systems

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