Publications

Export 37 results:
Sort by: Author Title Type [ Year  (Desc)]
2013
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.

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

2011
Gray, R. D., and A. Malheiro. "Finite complete rewriting systems for regular semigroups." Theor. Comput. Sci.. 412 (2011): 654-661. AbstractWebsite

It is proved that, given a (von Neumann) regular semigroup with finitely many left and right ideals, if every maximal subgroup is presentable by a finite complete rewriting system, then so is the semigroup. To achieve this, the following two results are proved: the property of being defined by a finite complete rewriting system is preserved when taking an ideal extension by a semigroup defined by a finite complete rewriting system; a completely 0-simple semigroup with finitely many left and right ideals admits a presentation by a finite complete rewriting system provided all of its maximal subgroups do.

Araújo, J., and A. Malheiro. "On finite complete presentations and exact decompositions of semigroups." Commun. Algebra. 39 (2011): 3866-3878. AbstractWebsite

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–Szé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.

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.

2009
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].

2008
Malheiro, A. "On Finite Semigroup Cross-Sections and Complete Rewriting Systems." International Conference on Theoretical and Mathematical Foundations of Computer Science, TMFCS-08, Orlando, Florida, USA, July 7-10, 2008. 2008. 59-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.

2007
Malheiro, A. On trivializers and subsemigroups.. Semigroups and formal languages. Proceedings of the international conference in honour of the 65th birthday of Donald B. McAlister. Lisboa, Portugal, July 12–15, 2005.: Hackensack, NJ: World Scientific, 2007. 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.

2006
Malheiro, A. "Finite derivation type for Rees matrix semigroups." Theor. Comput. Sci.. 355 (2006): 274-290. AbstractWebsite

This paper introduces the topological finiteness condition finite derivation type (FDT) on the class of semigroups. This notion is naturally extended from the monoid case. With this new concept we are able to prove that if a Rees matrix semigroup M[S;I,J;P] has FDT then the semigroup S also has FDT. Given a monoid S and a finitely presented Rees matrix semigroup M[S;I,J;P] we prove that if the ideal of S generated by the entries of P has FDT, then so does M[S;I,J;P]. In particular, we show that, for a finitely presented completely simple semigroup M, the Rees matrix semigroup M=M[S;I,J;P] has FDT if and only if the group S has FDT.

Malheiro, A. Finiteness conditions of semigroup presentations.. Eds. G. M. S. Gomes. University of Lisbon. Lisbon: University of Lisbon, 2006.
2005
Malheiro, A. "Complete rewriting systems for codified submonoids." Int. J. Algebra Comput.. 15 (2005): 207-216. AbstractWebsite

Given a complete rewriting system R on X and a subset X0 of X+ satisfying certain conditions, we present a complete rewriting system for the submonoid of M(X;R) generated by X0. The obtained result will be applied to the group of units of a monoid satisfying H1 = D1. On the other hand we prove that all maximal subgroups of a monoid defined by a special rewriting system are isomorphic.

2001
Malheiro, A. Presentations and complete rewriting systems for semigroups. (in Portuguese). Eds. G. M. S. Gomes. Faculty of Sciences of the University of Lisbon. Lisbon: University of Lisbon, 2001.