The problems of cyclic equality and conjugacy for finite complete rewriting systems

DOI10.1016/0304-3975(86)90131-3zbMath0619.68033OpenAlexW2021390843MaRDI QIDQ1089798

Friedrich Otto, 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)90131-3

zbMATH Keywords

finite complete rewriting systemcyclic equalityleft-conjugacy problem

Mathematics Subject Classification ID

Abstract data types; algebraic specification (68Q65) Thue and Post systems, etc. (03D03)

Related Items (8)

Decidability and independence of conjugacy problems in finitely presented monoids ⋮ Some polynomial-time algorithms for finite monadic Church-Rosser Thue systems ⋮ Deciding conjugacy in sylvester monoids and other homogeneous monoids ⋮ The Knuth-Bendix algorithm and the conjugacy problem in monoids. ⋮ About the descriptive power of certain classes of finite string-rewriting systems ⋮ Decision problems for finite special string-rewriting systems that are confluent on some congruence class ⋮ Trace monoids with some invertible generators: Two decision problems ⋮ On two problems related to cancellativity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The equation \(a_ M=b^ Nc^ P\) in a free group
• Finite complete rewriting systems and the complexity of word problem
• Conjugacy in monoids with a special Church-Rosser presentation is decidable
• Some undecidability results for non-monadic Church-Rosser Thue systems
• Complexity results on the conjugacy problem for monoids
• Infinite regular Thue systems
• On theories with a combinatorial definition of 'equivalence'
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems

This page was built for publication: The problems of cyclic equality and conjugacy for finite complete rewriting systems