Garreta, Albert and Gray, Robert (2021) On equations and first-order theory of one-relator monoids. Information and Computation, 281. ISSN 0890-5401
Preview |
PDF (GarretaGrayIandCPaperFinal5April2021)
- Accepted Version
Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (523kB) | Preview |
Abstract
We investigate systems of equations and the first-order theory of one-relator monoids. We describe a family F of one-relator monoids of the form 〈A|w=1〉 where for each monoid M in F, the longstanding open problem of decidability of word equations with length constraints reduces to the Diophantine problem (i.e. decidability of systems of equations) in M. We achieve this result by finding an interpretation in M of a free monoid, using only systems of equations together with length relations. It follows that each monoid in F has undecidable positive AE-theory, hence in particular it has undecidable first-order theory. The family F includes many one-relator monoids with torsion 〈A|w n=1〉 (n>1). In contrast, all one-relator groups with torsion are hyperbolic, and all hyperbolic groups are known to have decidable Diophantine problem. We further describe a different class of one-relator monoids with decidable Diophantine problem.
Item Type: | Article |
---|---|
Uncontrolled Keywords: | diophantine problem,first-order theory,one-relator monoids,word equations with length constraints,theoretical computer science,information systems,computer science applications,computational theory and mathematics ,/dk/atira/pure/subjectarea/asjc/2600/2614 |
Faculty \ School: | Faculty of Science > School of Mathematics (former - to 2024) |
UEA Research Groups: | Faculty of Science > Research Groups > Algebra and Combinatorics Faculty of Science > Research Groups > Logic |
Related URLs: | |
Depositing User: | LivePure Connector |
Date Deposited: | 15 Apr 2021 23:51 |
Last Modified: | 25 Sep 2024 15:32 |
URI: | https://ueaeprints.uea.ac.uk/id/eprint/79796 |
DOI: | 10.1016/j.ic.2021.104745 |
Downloads
Downloads per month over past year
Actions (login required)
View Item |