Decidability and independence of conjugacy problems in finitely presented monoids

DOI10.1016/j.tcs.2018.04.002zbMath1435.20064arXiv1703.00027OpenAlexW2952062796WikidataQ129979718 ScholiaQ129979718MaRDI QIDQ1637219

João Araújo, Janusz Konieczny, António Malheiro, Michael K. Kinyon

Publication date: 7 June 2018

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

Full work available at URL: https://arxiv.org/abs/1703.00027

zbMATH Keywords

complexityindependenceconjugacydecidabilitydecision problemfinitely presented monoidspolycyclic monoids

Mathematics Subject Classification ID

Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35) Word problems, etc. in computability and recursion theory (03D40)

Related Items (3)

Normal subsemigroups of finite transformation semigroups ⋮ On equations and first-order theory of one-relator monoids ⋮ The transitivity of primary conjugacy in regular \(\omega\)-semigroups

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The equation \(a_ M=b^ Nc^ P\) in a free group
• Conjugacy in monoids with a special Church-Rosser presentation is decidable
• On three approaches to conjugacy in semigroups.
• Primitive partial permutation representations of the polycyclic monoids and branching function systems.
• Complexity results on the conjugacy problem for monoids
• The problems of cyclic equality and conjugacy for finite complete rewriting systems
• Conjugacy in special monoids
• Simple \(C^*\)-algebras generated by isometries
• An application of polycyclic monoids to rings
• Conjugation in semigroups.
• Strong representations of the polycyclic inverse monoids: cycles and atoms.
• Recursively enumerable degress and the conjugacy problem
• On Finite Complete Presentations and Exact Decompositions of Semigroups
• CONJUGACY IN FREE INVERSE MONOIDS
• On the algorithmic insolvability of the word problem in group theory
• THE SEMIGROUP OF CONJUGATES OF A WORD
• DECISION PROBLEMS FOR FINITELY PRESENTED AND ONE-RELATION SEMIGROUPS AND MONOIDS
• Confluent and Other Types of Thue Systems
• ON THE CONJUGACY PROBLEM FOR ONE-RELATOR MONOIDS WITH ELEMENTS OF FINITE ORDER
• Four notions of conjugacy for abstract semigroups
• Semigroup and Group Presentations
• Recursive Unsolvability of a problem of Thue

This page was built for publication: Decidability and independence of conjugacy problems in finitely presented monoids