On the regular equivalence problem for regular Thue systems

DOI10.1016/0304-3975(86)90121-0zbMath0609.68027OpenAlexW2075456171MaRDI QIDQ1087011

Paliath Narendran

Publication date: 1986

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(86)90121-0

zbMATH Keywords

undecidabilitydecision procedurealmost- confluent Thue systemspreperfect Thue systems

Mathematics Subject Classification ID

Free semigroups, generators and relations, word problems (20M05) Abstract data types; algebraic specification (68Q65) Decidability of theories and sets of sentences (03B25) Thue and Post systems, etc. (03D03)

Related Items

Some decision problems about controlled rewriting systems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The undecidability of the preperfectness of Thue systems
• Homogeneous Thue systems and the Church-Rosser property
• The Church-Rosser property and special Thue systems
• Monadic Thue systems
• Infinite regular Thue systems
• Une généralisation des ensembles de Dyck
• The Knuth-Bendix Completion Procedure and Thue Systems
• Confluent and Other Types of Thue Systems