Word problems and confluence problems for restricted semi-Thue systems

DOI10.1007/10721975_12MaRDI QIDQ2723899zbMATH OpenFDO

Authors Markus Lohrey

Publication date 8 July 2001

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/10721975_12

Mathematics Subject Classification ID

Thue and Post systems, etc. (03D03) Word problems, etc. in computability and recursion theory (03D40) Grammars and rewriting systems (68Q42)

Recommendations

• Complexity results for confluence problems
• Word problem for deterministic and reversible semi-Thue systems
• Decision problems for semi-Thue systems with a few rules
• Some undecidable termination problems for semi-Thue systems
• On the termination problem for one-rule semi-Thue system

Cited in

(7)

• Almost all one-rule Thue systems have decidable word problems
• A polynomial algorithm testing partial confluence of basic semi-Thue systems
• Word problem for deterministic and reversible semi-Thue systems
• Some generalized semi-thue systems
• A polynomial algorithm testing partial confluence of basic semi-Thue systems
• On the complexity of some extended word problems defined by cancellation rules
• Quadratic word equations with length constraints, counter systems, and Presburger arithmetic with divisibility

This page was built for publication: Word problems and confluence problems for restricted semi-Thue systems

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