On the regular equivalence problem for regular Thue systems

DOI10.1016/0304-3975(86)90121-0MaRDI QIDQ1087011zbMATH OpenOpenAlexFDO

Authors 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

almost- confluent Thue systemsdecision procedurepreperfect Thue systemsundecidability

Mathematics Subject Classification ID

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

Review text

A decision procedure is presented for the equivalence problem for regular almost-confluent Thue systems. On the other hand, the equivalence problem for regular preperfect systems is shown to be undecidable.

Recommendations

• On reduced thue systems
• The undecidability of the preperfectness of Thue systems
• Church-Rosser systems with respect to formal languages
• It is decidable whether a monadic thue system is canonical over a regular set
• scientific article; zbMATH DE number 4210423

Cites work

• Confluent and Other Types of Thue Systems
• Homogeneous Thue systems and the Church-Rosser property
• scientific article; zbMATH DE number 3850464 (Why is no real title available?)
• scientific article; zbMATH DE number 3948242 (Why is no real title available?)
• scientific article; zbMATH DE number 3528212 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• Infinite regular Thue systems
• Monadic Thue systems
• The Church-Rosser property and special Thue systems
• The Knuth-Bendix Completion Procedure and Thue Systems
• The undecidability of the preperfectness of Thue systems
• Une généralisation des ensembles de Dyck

Cited in

(6)

• A regularity test for dual bordered OS systems
• Preperfectness is undecidable for Thue systems containing only length- reducing rules and a single commutation rule
• Elements of finite order for finite weight-reducing and confluent Thue systems
• The uniform conjugacy problem for finite church—Rosser thue systems is NP-complete
• A new lower bound construction for commutative Thue systems with applications
• Some decision problems about controlled rewriting systems

This page was built for publication: On the regular equivalence problem for regular Thue systems

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