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

undecidabilitydecision procedurealmost- confluent Thue systemspreperfect Thue systems

Mathematics Subject Classification ID

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

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

• 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?)
• Confluent and Other Types of Thue Systems
• Homogeneous Thue systems and the Church-Rosser property
• 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
• The uniform conjugacy problem for finite church—Rosser thue systems is NP-complete
• Some decision problems about controlled rewriting systems
• Elements of finite order for finite weight-reducing and confluent Thue systems
• A new lower bound construction for commutative Thue systems with applications
• Preperfectness is undecidable for Thue systems containing only length- reducing rules and a single commutation rule

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)