Some polynomial-time algorithms for finite monadic Church-Rosser Thue systems

DOI10.1016/0304-3975(89)90167-9MaRDI QIDQ1123619zbMATH OpenOpenAlexFDO

Authors Paliath Narendran, Friedrich Otto

Publication date 1989

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

Full work available at URL https://doi.org/10.1016/0304-3975(89)90167-9

zbMATH Keywords

finite monadic Church-Rosser Thue systemsrewriting systemsuniform conjugacy problemuniform decision problems

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Thue and Post systems, etc. (03D03) Analysis of algorithms and problem complexity (68Q25) Abstract data types; algebraic specification (68Q65) Artificial intelligence (68T99)

Recommendations

• scientific article; zbMATH DE number 3948242
• Complexity of certain decision problems about congruential languages
• Elements of Finite Order for Finite Monadic Church-Rosser Thue Systems
• Some undecidability results for non-monadic Church-Rosser Thue systems
• An \(O(| T| ^ 3)\) algorithm for testing the Church-Rosser property of Thue systems

Cites work

• Cancellativity in finitely presented semigroups
• Complexity results on the conjugacy problem for monoids
• Confluent and Other Types of Thue Systems
• Conjugacy in monoids with a special Church-Rosser presentation is decidable
• Decidable sentences of Church-Rosser congruences
• Elements of Finite Order for Finite Monadic Church-Rosser Thue Systems
• Elements of finite order for finite weight-reducing and confluent Thue systems
• scientific article; zbMATH DE number 3898258 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• On two problems related to cancellativity
• Presentations of groups and monoids
• The equation \(a_ M=b^ Nc^ P\) in a free group
• The Knuth-Bendix Completion Procedure and Thue Systems
• The problems of cyclic equality and conjugacy for finite complete rewriting systems
• The uniform conjugacy problem for finite church—Rosser thue systems is NP-complete
• Thue systems as rewriting systems

Cited in

(9)

• An \(O(| T| ^ 3)\) algorithm for testing the Church-Rosser property of Thue systems
• Complexity of certain decision problems about congruential languages
• A polynomial algorithm testing partial confluence of basic semi-Thue systems
• Elements of Finite Order for Finite Monadic Church-Rosser Thue Systems
• The uniform conjugacy problem for finite church—Rosser thue systems is NP-complete
• Dehn's Algorithm and the Complexity of Word Problems
• scientific article; zbMATH DE number 4109028 (Why is no real title available?)
• Restrictions of congruences generated by finite canonical string-rewriting systems
• Decision problems for finite special string-rewriting systems that are confluent on some congruence class

This page was built for publication: Some polynomial-time algorithms for finite monadic Church-Rosser Thue systems

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