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 -