Complexity results on the conjugacy problem for monoids

DOI10.1016/0304-3975(85)90016-7zbMath0588.03022OpenAlexW1999125908MaRDI QIDQ1073015

Friedrich Otto, Paliath Narendran

Publication date: 1985

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

Full work available at URL: https://doi.org/10.1016/0304-3975(85)90016-7

zbMATH Keywords

Church-Rosser propertyThue system

Mathematics Subject Classification ID

Free semigroups, generators and relations, word problems (20M05) Complexity of computation (including implicit computational complexity) (03D15) Word problems, etc. in computability and recursion theory (03D40) Other degrees and reducibilities in computability and recursion theory (03D30) Thue and Post systems, etc. (03D03)

Related Items (11)

The problems of cyclic equality and conjugacy for finite complete rewriting systems ⋮ Decidability and independence of conjugacy problems in finitely presented monoids ⋮ Thue systems as rewriting systems ⋮ 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 ⋮ On equations and first-order theory of one-relator monoids ⋮ On two problems related to cancellativity ⋮ On deciding whether a monoid is a free monoid or is a group

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• The Church-Rosser property and special Thue systems
• Monadic Thue systems
• Infinite regular Thue systems
• Recursively enumerable degress and the conjugacy problem
• Relationships between nondeterministic and deterministic tape complexities
• On the computational power of pushdown automata
• Confluent and Other Types of Thue Systems
• Recursive Unsolvability of a problem of Thue

This page was built for publication: Complexity results on the conjugacy problem for monoids