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
complexityindependenceconjugacydecidabilitydecision problemfinitely presented monoidspolycyclic monoids
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)
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