TY - JOUR

T1 - Decidability and independence of conjugacy problems in finitely presented monoids

AU - Araújo, João

AU - Kinyon, Michael

AU - Konieczny, Janusz

AU - Malheiro, António

N1 - Partially supported by the Fundacao para a Ciencia e a Tecnologia (Portuguese Foundation for Science and Technology) through the project CEMAT-CIENCIAS UID/Multi/04621/2013.
Partially supported by the Fundacao para a Ciencia e a Tecnologia (Portuguese Foundation for Science and Technology) through the project "Hilbert's 24th problem" PTDC/MHC-FIL/2583/2014.
Partially supported by Simons Foundation Collaboration Grant 359872.
Supported by the 2011-12 University of Mary Washington Faculty Research Grant.
Partially supported by the Fundacao para a Ciencia e a Tecnologia (Portuguese Foundation for Science and Technology) through the project UID/MAT/00297/2013 (Centro de Matematica e Aplicacoes).

PY - 2018/6/30

Y1 - 2018/6/30

N2 - There have been several attempts to extend the notion of conjugacy from groups to monoids. The aim of this paper is study the decidability and independence of conjugacy problems for three of these notions (which we will denote by ∼p, ∼o, and ∼c) in certain classes of finitely presented monoids. We will show that in the class of polycyclic monoids, p-conjugacy is “almost” transitive, ∼c is strictly included in ∼p, and the p- and c-conjugacy problems are decidable with linear complexity on a two-tape Turing Machine. For other classes of monoids, the situation is more complicated. We show that there exists a monoid M defined by a finite complete presentation such that the c-conjugacy problem for M is undecidable, and that for finitely presented monoids, the c-conjugacy problem and the word problem are independent, as are the c-conjugacy and p-conjugacy problems. On other hand, we show that for finitely presented monoids, the o-conjugacy problem is reducible to the c-conjugacy problem.

AB - There have been several attempts to extend the notion of conjugacy from groups to monoids. The aim of this paper is study the decidability and independence of conjugacy problems for three of these notions (which we will denote by ∼p, ∼o, and ∼c) in certain classes of finitely presented monoids. We will show that in the class of polycyclic monoids, p-conjugacy is “almost” transitive, ∼c is strictly included in ∼p, and the p- and c-conjugacy problems are decidable with linear complexity on a two-tape Turing Machine. For other classes of monoids, the situation is more complicated. We show that there exists a monoid M defined by a finite complete presentation such that the c-conjugacy problem for M is undecidable, and that for finitely presented monoids, the c-conjugacy problem and the word problem are independent, as are the c-conjugacy and p-conjugacy problems. On other hand, we show that for finitely presented monoids, the o-conjugacy problem is reducible to the c-conjugacy problem.

KW - Complexity

KW - Conjugacy

KW - Decidability

KW - Decision problem

KW - Finitely presented monoids

KW - Independence

KW - Polycyclic monoids

UR - http://www.scopus.com/inward/record.url?scp=85045938126&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2018.04.002

DO - 10.1016/j.tcs.2018.04.002

M3 - Article

AN - SCOPUS:85045938126

VL - 731

SP - 88

EP - 98

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -