On finite complete rewriting systems, finite derivation type, and automaticity for homogeneous monoids
Malheiro, António; Gray, Robert; Cain, Alan J.


The class of finitely presented monoids defined by homogeneous (length-preserving) relations is considered. The properties of admitting a finite complete rewriting system, having finite derivation type, being automatic, and being biautomatic, are investigated for monoids in this class. The first main result shows that for any possible combination of these properties and their negations there is a homoegenous monoid with exactly this combination of properties. We then extend this result to show that the same statement holds even if one restricts attention to the class of n-ary multihomogeneous monoids (meaning every side of every relation has fixed length n, and all relations are also content preserving).

FCT - Fundação para a Ciência e a Tecnologia