finite derivation type

Cain, A. J., R. D. Gray, and A. Malheiro. "On finite complete rewriting systems, finite derivation type, and automaticity for homogeneous monoids." Information and Computation. 255 (2017): 68-93. AbstractWebsite

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

Malheiro, A. "Finite derivation type for large ideals." Semigroup Forum. 78 (2009): 450-485. AbstractWebsite

n this paper we give a partial answer to the following question: does a large subsemigroup of a semigroup S with the finite combinatorial property finite derivation type (FDT) also have the same property? A positive answer is given for large ideals. As a consequence of this statement we prove that, given a finitely presented Rees matrix semigroup M[S;I,J;P], the semigroup S has FDT if and only if so does M[S;I,J;P].

Gray, R. D., A. Malheiro, and S. J. Pride. "On properties not inherited by monoids from their Schützenberger groups." Inf. Comput.. 209 (2011): 1120-1134. AbstractWebsite

We give an example of a monoid with finitely many left and right ideals, all of whose Schü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.

Malheiro, A. "Finite derivation type for semilattices of semigroups." Semigroup Forum. 84 (2012): 515-526. AbstractWebsite

In this paper we investigate how the combinatorial property finite derivation type (FDT) is preserved in a semilattice of semigroups. We prove that if S=S[Y,S_α] is a semilattice of semigroups such that Y is finite and each S_α (α∈Y) has FDT, then S has FDT. As a consequence we can show that a strong semilattice of semigroups S[Y,S_α,λ_{α,β}] has FDT if and only if Y is finite and every semigroup S α (α∈Y) has FDT.

Gray, R. D., A. Malheiro, and S. J. Pride. "Homotopy bases and finite derivation type for Schützenberger groups of monoids." J. Symb. Comput.. 50 (2013): 50-78. AbstractWebsite

Given a finitely presented monoid and a homotopy base for the monoid, and given an arbitrary Schutzenberger group of the monoid, the main result of this paper gives a homotopy base, and presentation, for the Schutzenberger group. In the case that the R-class R' of the Schutzenberger group G(H) has only finitely many H-classes, and there is an element s of the multiplicative right pointwise stabilizer of H, such that under the left action of the monoid on its R-classes the intersection of the orbit of the R-class of s with the inverse orbit of R' is finite, then finiteness of the presentation and of the homotopy base is preserved.

Gray, R. D., and A. Malheiro. "Homotopy bases and finite derivation type for subgroups of monoids." J. Algebra. 410 (2014): 53-84. AbstractWebsite

Given a monoid defined by a presentation, and a homotopy base for the derivation graph associated to the presentation, and given an arbitrary subgroup of the monoid, we give a homotopy base (and presentation) for the subgroup. If the monoid has finite derivation type (FDT), and if under the action of the monoid on its subsets by right multiplication the strong orbit of the subgroup is finite, then we obtain a finite homotopy base for the subgroup, and hence the subgroup has FDT. As an application we prove that a regular monoid with finitely many left and right ideals has FDT if and only if all of its maximal subgroups have FDT. We use this to show that a finitely presented regular monoid with finitely many left and right ideals satisfies the homological finiteness condition FP3 if all of its maximal subgroups satisfy the condition FP_3.