Almost all one-rule Thue systems have decidable word problems

DOI10.1016/0012-365X(84)90160-2zbMath0563.03020MaRDI QIDQ1057265

Ronald V. Book, Craig C. Squier

Publication date: 1984

Published in: Discrete Mathematics (Search for Journal in Brave)

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Word problems, etc. in computability and recursion theory (03D40) Thue and Post systems, etc. (03D03)

Related Items

The word problem for one-relator semigroups ⋮ Thue systems as rewriting systems ⋮ On public-key cryptosystem based on Church-Rosser string-rewriting systems ⋮ Non-repetitive words relative to a rewriting system ⋮ The word problem for one-relation monoids: a survey

Cites Work

• Homogeneous Thue systems and the Church-Rosser property
• Confluent and Other Types of Thue Systems
• Unnamed Item
• Unnamed Item