Cain, Alan J., Gray, Robert D. and Malheiro, António (2017) On finite complete rewriting systems, finite derivation type, and automaticity for homogeneous monoids. Information and Computation, 255 (1). pp. 68-93. ISSN 0890-5401
Preview |
PDF (Accepted manuscript)
- Accepted Version
Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (465kB) | Preview |
Abstract
This paper investigates the class of finitely presented monoids defined by homogeneous (length-preserving) relations from a computational perspective. The properties of admitting a finite complete rewriting system, having finite derivation type, being automatic, and being biautomatic are investigated for this class of monoids. The first main result shows that for any consistent combination of these properties and their negations, there is a homogeneous monoid with exactly this combination of properties. We then introduce the new concept of abstract Rees-commensurability (an analogue of the notion of abstract commensurability for groups) in order to extend this result to show that the same statement holds even if one restricts attention to the class of n-ary homogeneous monoids (where every side of every relation has fixed length n). We then introduce a new encoding technique that allows us to extend the result partially to the class of n-ary multihomogenous monoids.
Item Type: | Article |
---|---|
Uncontrolled Keywords: | homogeneous monoid,presentation,rewriting system,homotopy,finite derivation type,automatic,biautomatic |
Faculty \ School: | Faculty of Science > School of Mathematics (former - to 2024) |
UEA Research Groups: | Faculty of Science > Research Groups > Algebra and Combinatorics |
Depositing User: | Pure Connector |
Date Deposited: | 31 May 2017 08:31 |
Last Modified: | 25 Sep 2024 12:46 |
URI: | https://ueaeprints.uea.ac.uk/id/eprint/63619 |
DOI: | 10.1016/j.ic.2017.05.003 |
Downloads
Downloads per month over past year
Actions (login required)
View Item |