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

DOI10.1016/0304-3975(89)90167-9zbMath0677.68050OpenAlexW1979249711MaRDI QIDQ1123619

Friedrich Otto, Paliath Narendran

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

rewriting systemsfinite monadic Church-Rosser Thue systemsuniform conjugacy problemuniform decision problems

Mathematics Subject Classification ID

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

Related Items (2)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Decidable sentences of Church-Rosser congruences
• The equation \(a_ M=b^ Nc^ P\) in a free group
• Conjugacy in monoids with a special Church-Rosser presentation is decidable
• On two problems related to cancellativity
• Complexity results on the conjugacy problem for monoids
• The problems of cyclic equality and conjugacy for finite complete rewriting systems
• Thue systems as rewriting systems
• Elements of finite order for finite weight-reducing and confluent Thue systems
• Presentations of groups and monoids
• Cancellativity in finitely presented semigroups
• The Knuth-Bendix Completion Procedure and 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
• Confluent and Other Types of Thue Systems

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