@article {CGM14, title = {On finite complete rewriting systems, finite derivation type, and automaticity for homogeneous monoids}, journal = {Information and Computation}, volume = {255}, year = {2017}, note = {

Submitted

}, pages = {68-93}, abstract = {

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).

}, url = {https://doi.org/10.1016/j.ic.2017.05.003}, author = {Cain, A.J. and R.D. {Gray} and Malheiro, A.} } @article {zbMATH06000141, title = {On finite complete presentations and exact decompositions of semigroups.}, journal = {Commun. Algebra}, volume = {39}, number = {10}, year = {2011}, note = {

n/a

}, pages = {3866{\textendash}3878}, publisher = {Taylor \& Francis, Philadelphia, PA}, abstract = {

We prove that given a finite (zero) exact right decomposition (M, T) of a semigroup S, if M is defined by a finite complete presentation, then S is also defined by a finite complete presentation. Exact right decompositions are natural generalizations to semigroups of coset decompositions in groups. As a consequence, we deduce that any Zappa{\textendash}Sz{\'e}p extension of a monoid defined by a finite complete presentation, by a finite monoid, is also defined by such a presentation.

It is also proved that a semigroup M^0[A; I, J; P], where A and P satisfy some very general conditions, is also defined by a finite complete presentation.

}, issn = {0092-7872; 1532-4125/e}, doi = {10.1080/00927872.2010.514314}, url = {http://dx.doi.org/10.1080/00927872.2010.514314}, author = {J. Ara{\'u}jo and Malheiro, A.} } @article {zbMATH05925504, title = {On properties not inherited by monoids from their Sch{\"u}tzenberger groups.}, journal = {Inf. Comput.}, volume = {209}, number = {7}, year = {2011}, note = {

n/a

}, pages = {1120{\textendash}1134}, publisher = {Elsevier (Academic Press), San Diego, CA}, abstract = {

We give an example of a monoid with finitely many left and right ideals, all of whose Sch{\"u}tzenberger groups are presentable by finite complete rewriting systems, and so each have finite derivation type, but such that the monoid itself does not have finite derivation type, and therefore does not admit a presentation by a finite complete rewriting system. The example also serves as a counterexample to several other natural questions regarding complete rewriting systems and finite derivation type. Specifically it allows us to construct two finitely generated monoids M and N with isometric Cayley graphs, where N has finite derivation type (respectively, admits a presentation by a finite complete rewriting system) but M does not. This contrasts with the case of finitely generated groups for which finite derivation type is known to be a quasi-isometry invariant. The same example is also used to show that neither of these two properties is preserved under finite Green index extensions.

}, issn = {0890-5401}, doi = {10.1016/j.ic.2011.03.004}, url = {http://dx.doi.org/10.1016/j.ic.2011.03.004}, author = {R.D. {Gray} and Malheiro, A. and S.J. {Pride}} } @conference {DBLP:conf/tmfcs/Malheiro08, title = {On Finite Semigroup Cross-Sections and Complete Rewriting Systems}, booktitle = {International Conference on Theoretical and Mathematical Foundations of Computer Science, TMFCS-08, Orlando, Florida, USA, July 7-10, 2008}, year = {2008}, note = {

n/a

}, pages = {59{\textendash}63}, abstract = {

In this paper we obtain a [finite] complete rewriting system defining a semigroup/monoid S, from a given finite
right cross-section of a subsemigroup/submonoid defined by a [finite] complete presentation. In the semigroup case the subsemigroup must have a right identity element which must also be part of the cross-section. In the monoid case the submonoid and the cross-section must include the identity of the semigroup. The result on semigroups allow us to show that if G is a group defined by a [finite] complete rewriting system then the completely simple semigroup M[G; I, J; P] is also defined by a [finite] complete rewriting system.

}, author = {Malheiro, A.} } @proceedings {zbMATH05218140, title = {On trivializers and subsemigroups.}, journal = {Semigroups and formal languages. Proceedings of the international conference in honour of the 65th birthday of Donald B. McAlister}, year = {2007}, note = {

n/a

}, pages = {188{\textendash}204}, publisher = {Hackensack, NJ: World Scientific}, address = {Lisboa, Portugal, July 12{\textendash}15, 2005.}, abstract = {

The aim of this paper is to develop the calculus of trivializers for subsemigroups. Given a finite presentation defining a semigroup S and a trivializer of the Squier complex of , we obtain an infinite trivializer of the Squier complex of a finite presentation defining a subsemigroup of S. Also, we give a method to find finite trivializers for special subsemigroups and hence to show that those subsemigroups have finite derivation type (FDT). An application of this method is given: we prove that if is a band of monoids having FDT, then so does Sα, for any α ∈Y.

}, isbn = {978-981-270-738-3/hbk}, url = {http://dx.doi.org/10.1142/9789812708700_0013}, author = {Malheiro, A.} }