Search

This paper provides an abstract characterization of the monoids that appear as monoids of subalgebras of the square of finite minimal algebras admitting a majority term. As a tool, a matrix construction similar to the one introduced in [A characterization of the inverse monoid of bi-congruences of certain algebras, Int. J. Algebra Comput.6 (2009) 791–808] is used.

We continue our program of extending key techniques from geometric group theory to semigroup theory, by studying monoids acting by isometric embeddings on spaces equipped with asymmetric, partially defined distance functions. The canonical example of such an action is a cancellative monoid acting by translation on its Cayley graph. Our main result is an extension of the Švarc–Milnor lemma to this setting.

We generalize the word problem for groups, the formal language of all words in the generators that represent the identity, to inverse monoids. In particular, we introduce the idempotent problem, the formal language of all words representing idempotents, and investigate how the properties of an inverse monoid are related to the formal language properties of its idempotent problem. We show that if an inverse monoid is either E-unitary or has a finite set of idempotents, then its idempotent problem is regular if and only if the inverse monoid is finite. We also give examples of inverse monoids with context-free idempotent problems, including all Bruck–Reilly extensions of finite groups.

This is the first of two articles studying the structure of left adequate and, more generally, of left Ehresmann monoids. Motivated by a careful analysis of normal forms, we introduce here a concept of proper for a left adequate monoid M. In fact, our notion is that of T-proper, where T is a submonoid of M. We show that any left adequate monoid M has an X*-proper cover for some set X, that is, there is a left adequate monoid [Formula: see text] that is X*-proper, and an idempotent separating surjective morphism [Formula: see text] of the appropriate type. Given this result, we may deduce that the free left adequate monoid on any set X is X*-proper. In a subsequent paper, we show how to construct T-proper left adequate monoids from any monoid T acting via order-preserving maps on a semilattice with identity, and prove that the free left adequate monoid is of this form. An alternative description of the free left adequate monoid will appear in a paper of Kambites. We show how to obtain the labeled trees appearing in his result from our structure theorem. Our results apply to the wider class of left Ehresmann monoids, and we give them in full generality. We also indicate how to obtain some of the analogous results in the two-sided case. This paper and its sequel, and the two of Kambites on free (left) adequate semigroups, demonstrate the rich but accessible structure of (left) adequate semigroups and monoids, introduced with startling insight by Fountain some 30 years ago.

We study the singular part of the partition monoid [Formula: see text]; that is, the ideal [Formula: see text], where [Formula: see text] is the symmetric group. Our main results are presentations in terms of generators and relations. We also show that [Formula: see text] is idempotent generated, and that its rank and idempotent-rank are both equal to [Formula: see text]. One of our presentations uses an idempotent generating set of this minimal cardinality.

This paper studies rr-, ℓr-, rℓ-, and ℓℓ-automatic structures for finitely generated submonoids of monoids presented by confluent rewriting system that are either finite and special or regular and monadic. A new technique is developed that uses an automaton to "translate" between words in the original rewriting system and words over the generators for the submonoid. This is applied to show that the submonoid inherits any notion of automatism possessed by the original monoid. Generalizations of results of Otto and Ruškuc are thus obtained: every finitely generated submonoid of a monoid presented by a confluent finite special rewriting system admits an automatic structure that is simultaneously rr-, ℓr-, rℓ-, and ℓℓ-automatic; and every finitely generated submonoid of a monoid presented by a confluent regular monadic rewriting system admits an automatic structure that is simultaneously rr- and ℓℓ-automatic. These structures are shown to be effectively computable. An algorithm is given to decide whether the monoid presented by a confluent monadic finite rewriting system is ℓr- or rℓ-automatic. Finally, these results are applied to yield answers to some hitherto open questions and to recover and generalize established results.

This paper provides an abstract characterization of the inverse monoids that appear as monoids of bi-congruences of finite minimal algebras generating arithmetical varieties. As a tool, a matrix construction is introduced which might be of independent interest in inverse semigroup theory. Using this construction as well as Ramsey's theorem, we embed a certain kind of inverse monoid into a factorizable monoid of the same kind. As noticed by M. Lawson, this embedding entails that the embedded finite monoids have finite F-unitary cover.

Hedrlín and Pultr proved that for any monoid M there exists a graph G with endomorphism monoid isomorphic to M. In a previous paper, we give a construction G(M) for a graph with prescribed endomorphism monoid M known as a [Formula: see text]-graph. Using this construction, we derived bounds on the minimum number of vertices and edges required to produce a graph with a given endomorphism monoid for various classes of finite monoids. In this paper, we generalize the [Formula: see text]-graph construction and derive several new bounds for monoid classes not handled by our first paper. Among these are the so called "strong semilattices of C-semigroups" where C is one of the following: Groups, Abelian Groups, Rectangular Groups, and completely simple semigroups.

We show that the free weakly E-ample monoid on a set X is a full submonoid of the free inverse monoid FIM(X) on X. Consequently, it is ample, and so coincides with both the free weakly ample and the free ample monoid FAM(X) on X. We introduce the notion of a semidirect product Y*T of a monoid T acting doubly on a semilattice Y with identity. We argue that the free monoid X* acts doubly on the semilattice [Formula: see text] of idempotents of FIM(X) and that FAM(X) is embedded in [Formula: see text]. Finally we show that every weakly E-ample monoid has a proper ample cover.

In this paper, we concern representations of symplectic rook monoids R. First, an algebraic description of R as a submonoid of a rook monoid is obtained. Second, we determine irreducible representations of R in terms of the irreducible representations of certain symmetric groups and those of the symplectic Weyl group W. We then give the character formula of R using the character of W and that of the symmetric groups. A practical algorithm is provided to make the formula user-friendly. At last we show that the Munn character table of R is a block upper triangular matrix.

In linear algebraic monoid theory, the Renner monoids play the role of the Weyl groups in linear algebraic group theory. It is well known that Weyl groups are Coxeter groups, and that we can associate a Hecke algebra and an Artin–Tits group to each Coxeter group. The question of the existence of a Hecke algebra associated with each Renner monoid has been positively answered. In this paper we discuss the question of the existence of an equivalent of the Artin–Tits groups in the framework of Renner monoids. We consider the seminal case of the rook monoid and introduce a new length function.

The dual symmetric inverse monoid [Formula: see text] is the inverse monoid of all isomorphisms between quotients of an n-set. We give a monoid presentation of [Formula: see text] and, along the way, establish criteria for a monoid to be inverse when it is generated by completely regular elements.

We determine the closure of a parabolic subgroup of a reductive group in a reductive monoid. This allows us to define parabolic submonoids of a finite monoid of Lie type. These are analogues of the monoid of block upper triangular matrices. We determine the structure of [Formula: see text]-class of a finite parabolic monoid and show that such a monoid is generated by its unit group and diagonal idempotents.

We introduce a finite semigroup associated with a conjugacy class of a word in the free monoid over a finite alphabet. Using properties of this semigroup we derive results on combinatorics on words.

There is a well-known correspondence between varieties of algebras and fully invariant congruences on the appropriate term algebra. A special class of varieties are those which are balanced, meaning they can be described by equations in which the same variables appear on each side. In this paper, we prove that the above correspondence, restricted to balanced varieties, leads to a correspondence between balanced varieties and inverse monoids. In the case of unary algebras, we recover the theorem of Meakin and Sapir that establishes a bijection between congruences on the free monoid with n generators and wide, positively self-conjugate inverse submonoids of the polycyclic monoid on n generators. In the case of varieties generated by linear equations, meaning those equations where each variable occurs exactly once on each side, we can replace the clause monoid above by the linear clause monoid. In the case of algebras with a single operation of arity n, we prove that the linear clause monoid is isomorphic to the inverse monoid of right ideal isomorphisms between the finitely generated essential right ideals of the free monoid on n letters, a monoid previously studied by Birget in the course of work on the Thompson group V and its analogues. We show that Dehornoy's geometry monoid of a balanced variety is a special kind of inverse submonoid of ours. Finally, we construct groups from the inverse monoids associated with a balanced variety and examine some conditions under which they still reflect the structure of the underlying variety. Both free groups and Thompson's groups Vn,1 arise in this way.

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.

A variation of first-order logic with variables for exponents is developed to solve some problems in the setting of recognizable languages on the free monoid, accommodating operators such as product, bounded shuffle and reversion. Restricting the operators to powers and product, analogous results are obtained for recognizable languages of an arbitrary finitely generated monoid M, in particular for a free inverse monoid of finite rank. As a consequence, it is shown to be decidable whether or not a recognizable subset of M is pure or p-pure.

In this paper, we discuss the different notions of local topological density for subsets of the free monoid A*. We introduce the notion of weak completeness for a set X, relatively to an arbitrary submonoid M of A*. For the so-called strongly M-thin codes, we establish that weak completeness is equivalent to maximality in M. This constitutes a new generalization of a famous result due to Schützenberger.

In 1987, Squier defined the notion of finite derivation type for a finitely presented monoid. To do this, he associated a 2-complex to the presentation. The monoid then has finite derivation type if, modulo the action of the free monoid ring, the 1-dimensional homotopy of this complex is finitely generated. Cremanns and Otto showed that finite derivation type implies the homological finiteness condition left FP3, and when the monoid is a group, these two properties are equivalent. In this paper we define a new version of finite derivation type, based on homological information, together with an extension of this finite derivation type to higher dimensions, and show connections to homological type FPnfor both monoids and groups.

In this paper we explicitly determine the Renner monoid ℛ and the cross section lattice Λ of the symplectic algebraic monoid MSpn in terms of the Weyl group and the concept of admissible sets; it turns out that ℛ is a submonoid of ℛn, the Renner monoid of the whole matrix monoid Mn, and that Λ is a sublattice of Λn, the cross section lattice of Mn. Cell decompositions in algebraic geometry are usually obtained by the method of [1]. We give a more direct definition of cells for MSpn in terms of the B × B-orbits, where B is a Borel subgroup of the unit group G of MSpn. Each cell turns out to be the intersection of MSpn with a cell of Mn. We also show how to obtain these cells using a carefully chosen one parameter subgroup.

We consider properties of a 2-complex associated by Squier to a monoid presentation. We show that the fundamental groupoid admits a monoid structure, and we establish a relationship between its group completion and the fundamental group of the 2-complex. We also treat a modified complex, due to Pride, for monoid presentations of groups, and compute the structure of the fundamental groupoid in this setting.

Let M be a finite monoid with unit group G. We consider a refinement, [Formula: see text] of the Green’s relation [Formula: see text]. The [Formula: see text]-classes, denoted [Formula: see text] are the G×G orbits, GHG, of the ℋ-classes, H, of M. With an orbit [Formula: see text] we associate a local monoid [Formula: see text] and determine the structure of these local monoids. The theory is applied to the full transformation semigroup [Formula: see text] and we see that the number of orbits [Formula: see text] in [Formula: see text] is equal to the number of partitions of n.

A one-relator monoid has nontrivial elements of finite order if and only if its presentation has the form (A; (PQ)mP=(PQ)nP), where PQ is a primitive word and m>n≥0. The (left-)conjugacy problem for such a monoid is shown to be reducible to the same problem for its left monoid. In particular, the (left-)conjugacy problem is decidable for the monoids M(A;(PQ)mP=(PQ)nP), where m+n≥2.

The aim of this note is to emphasize the connection between the idempotent word problem for inverse monoid presentations and certain left closed subsets of the free group. The wide use of automata and languages throughout the paper justifies our choice of considering the free group as a subset of the free monoid. Automata theory is used to provide a decidability result concerning rational languages. As a consequence, an alternative proof to the theorem of Meakin and Margolis on idempotent-pure presentations [7] is obtained, and some new cases are established. Moreover, an example of a finitely presented inverse monoid with undecidable idempotent word problem is given.

In this paper, we study the complexity of deciding code and monoid properties for regular sets specified by deterministic or nondeterministic finite automata. The results are as follows. The code problem for regular sets specified by deterministic or nondeterministic finite automata is NL-complete under NC(1) reducibilities. The problems of determining whether a regular set given by a deterministic finite automaton is a monoid or a free monoid or a finitely generated monoid are all NL-complete under NC(1) reducibilities. These monoid problems become PSPACE-complete if the regular sets are specified by nondeterministic finite automata instead. The maximal code problem for deterministic finite automata is shown to be in DET and NL-hard, while a PSPACE upper bound and NP-hardness lower bound hold for the case of nondeterministic finite automata.