An embedding of semigroups into regular semigroups that preserves structure and finiteness

For any semigroup S a regular semigroup is described here that embeds S and is such that its non-trivial maximal subgroups are isomorphic to the Schützenberger groups of S, its Green’s relations restrict to the corresponding Green’s relations on S and it is finite when S is finite.     

Amalgams of finite inverse semigroups and deterministic context-free languages

Let S be the amalgamated free product of two finite inverse semigroups. We prove that the Schützenberger graph of an element of S with respect to a standard presentation of S is a context-free graph in the sense of Müller and Schupp (Theor. Comput. Sci. 37:51?C75, 1985), showing that the language L recognized by the Schützenberger automaton is context-free. Moreover we construct the grammar generating L proving that L is a deterministic context-free language and we use this fact for solving some algorithmic problems.     

Presentations of Schützenberger groups of minimal subshifts

In previous work, the first author established a natural bijection between minimal subshifts and maximal regular J -classes of free profinite semigroups. In this paper, the Schützenberger groups of such J -classes are investigated, in particular in respect to a conjecture proposed by the first author concerning their profinite presentation. The conjecture is established for all non-periodic minimal subshifts associated with substitutions. It entails that it is decidable whether a finite group is a quotient of such a profinite group. As a further application, the Schützenberger group of the J -class corresponding to the Prouhet-Thue-Morse subshift is shown to admit a somewhat simpler presentation, from which it follows that it has rank three, and that it is non-free relatively to any pseudovariety of groups.     

Fundamental groups,inverse schützenberger automata,and monoid presentations

This paper gives decidable conditions for when a finitely generated subgroup of a free group is the fundamental group of a Schützenberger automaton corresponding to a monoid presentation of an inverse monoid. Also, generalizations are given to specific types of inverse monoids as well as to monoids which are "nearly inverse." This result has applications to computing membership for inverse monoids in a Mal'cev product of the pseudovariety of semilattices with a pseudovariety of groups.

This paper also shows that there is a bijection between strongly connected inverse automata and subgroups of a free group, generated by positive words. Hence, we also obtain that it is decidable whether a finite strongly connected inverse automaton is a Schützenberger automaton corresponding to a monoid presentation of an inverse monoid. Again, we have generalizations to other types of inverse monoids and to "nearly inverse" monoids. We show that it is undecidable whether a finite strongly connected inverse automaton is a Schützenberger automaton of a monoid presentation of anE-unitary inverse monoid.     

Largest subsemigroups of the full transformation monoid

In this paper we are concerned with the following question: for a semigroup S, what is the largest size of a subsemigroup T?S where T has a given property? The semigroups S that we consider are the full transformation semigroups; all mappings from a finite set to itself under composition of mappings. The subsemigroups T that we consider are of one of the following types: left zero, right zero, completely simple, or inverse. Furthermore, we find the largest size of such subsemigroups U where the least rank of an element in U is specified. Numerous examples are given.     

Constructions and presentations for monoids

Presentations are found for the wreath product of two monoids, the Schützenberger product of two monoids, the Bruck-Reilly extension of a monoid, strong semilattices of monoids and Rees matrix semigroups of monoids.     

The word problem for some classes of Adian inverse semigroups

We show that all of the Schützenberger complexes of an Adian inverse semigroup are finite if the Schützenberger complex of every positive word is finite. This enables us to solve the word problem for certain classes of Adian inverse semigroups (and hence for the corresponding Adian semigroups and Adian groups).     

On Schützenberger monoids in transformations semigroups

K. D. Magill and S. Subbiah [4] have studied the semigroup of continuous selfmaps of a topological space. They have shown that the Schützenberger group of theH containing a selfmap a is in a close relation to the group of homeomorphic selfmaps of the range of a. There arose a naturalproblem to find a generalization of the Schützenberger group, which is in the similar relation to the semigroup of continuous selfmaps of the range of a. C. E. Clark and J. H. Carruth [1] introduced a notion of a Schützenberger monoid. In this paper Schützenberger monoids in an arbitrary semigroup of transformations are studied and it is shown that this notion is the generalization we were looking for.     

Decidability of the word problem in Yamamura’s HNN extensions of finite inverse semigroups

We prove that the word problem is decidable in Yamamura’s HNN extensions of finite inverse semigroups, by providing an iterative construction of approximate automata of the Schützenberger automata of words relative to the standard presentation of Yamamura’s HNN-extensions. This work was done in the framework of the group GNSAGA of INDAM, the PRIN “Automi e Linguaggi Formali: aspetti matematici e applicativi” and the ESF project Automatha.     

Semigroup actions, covering spaces and Schützenberger groups

We associate a 2-complex to the following data: a presentation of a semigroup S and a transitive action of S on a set V by partial transformations. The automorphism group of the action acts properly discontinuously on this 2-complex. A sufficient condition is given for the 2-complex to be simply connected. As a consequence we obtain simple topological proofs of results on presentations of Schützenberger groups. We also give a geometric proof that a finitely generated regular semigroup with finitely many idempotents has polynomial growth if and only if all its maximal subgroups are virtually nilpotent.     

On Finite Presentability of Direct Products of Semigroups

A finite semigroup S is said to preserve finite generation (resp., presentability) in direct products, provided that, for every infinite semigroup T, the direct product S × T is finitely generated (resp., finitely presented) if and only if T is finitely generated (resp., finitely presented). The main result of this paper is a constructive necessary and sufficient condition for S to preserve both finite generation and presentability in direct products. The condition is that certain graphs, (s), one for each s S, are all connected. The main result is illustrated in three examples, one of which exhibits a 4-element semigroup that preserves finite generation but not finite presentability in direct products.1991 Mathematics Subject Classification: 20M05, 05C25The first author is financially supported by the Sub-Programa Ciência e Tecnologia do 2° Quadro Comunitário de Apoio (grant number BD/ 15623/98). The author also acknowledges the support of the Centro de Álgebra da Universidade de Lisboa and of the Projecto Praxis 2/2.1/MAT/73/94. The second author acknowledges partial financial support from the Nuffield Foundation.     

The shifted plactic monoid

We introduce a shifted analog of the plactic monoid of Lascoux and Schützenberger, the shifted plactic monoid. It can be defined in two different ways: via the shifted Knuth relations, or using Haiman’s mixed insertion. Applications include: a new combinatorial derivation (and a new version of) the shifted Littlewood–Richardson Rule; similar results for the coefficients in the Schur expansion of a Schur P-function; a shifted counterpart of the Lascoux–Schützenberger theory of noncommutative Schur functions in plactic variables; a characterization of shifted tableau words; and more.     

On character amenability of semigroup algebras

We study the character amenability of semigroup algebras. We work on general semigroups and certain semigroups such as inverse semigroups with a finite number of idempotents, inverse semigroups with uniformly locally finite idempotent set, Brandt and Rees semigroup and study the character amenability of the semigroup algebra l¹(S) in relation to the structures of the semigroup S. In particular, we show that for any semigroup S, if ?¹(S) is character amenable, then S is amenable and regular. We also show that the left character amenability of the semigroup algebra ?¹(S) on a Brandt semigroup S over a group G with index set J is equivalent to the amenability of G and J being finite. Finally, we show that for a Rees semigroup S with a zero over the group G, the left character amenability of ?¹(S) is equivalent to its amenability, this is in turn equivalent to G being amenable.     

On some properties of symplectic Grothendieck polynomials

Grothendieck polynomials, introduced by Lascoux and Schützenberger, are certain K-theory representatives for Schubert varieties. Symplectic Grothendieck polynomials, described more recently by Wyser and Yong, represent the K-theory classes of orbit closures for the complex symplectic group acting on the complete flag variety. We prove a transition formula for symplectic Grothendieck polynomials and study their stable limits. We show that each of the K-theoretic Schur P-functions of Ikeda and Naruse arises from a limiting procedure applied to symplectic Grothendieck polynomials representing certain “Grassmannian” orbit closures.     

A class of unary semigroups admitting a Rees matrix representation

In Billhardt et al. (Semigroup Forum 79:101–118, 2009) the authors introduced the notion of an associate inverse subsemigroup of a regular semigroup, extending the concept of an associate subgroup of a regular semigroup, first presented in Blyth et al. (Glasgow Math. J. 36:163–171, 1994). The main result of the present paper, Theorem 2.15, establishes that a regular semigroup S with an associate inverse subsemigroup S ^? satisfies three simple identities if and only if it is isomorphic to a generalised Rees matrix semigroup M(T;A,B;P), where T is a Clifford semigroup, A and B are bands, with common associate inverse subsemigroup E(T) satisfying the referred identities, and P is a sandwich matrix satisfying some natural conditions. If T is a group and A, B are left and right zero semigroups, respectively, then the structure described provides a usual Rees matrix semigroup with normalised sandwich matrix, thus generalising the Rees matrix representation for completely simple semigroups.     

A Structure Preserving Embedding of Semigroups Into Regular Semigroups

For any semigroup S a regular semigroup 𝒞(S) that embeds S can be constructed as the direct limit of a sequence of semigroups each of which contains a copy of its predecessor as a subsemigroup whose elements are regular. The construction is modified here to obtain an embedding of S into a regular semigroup R such that the nontrivial maximal subgroups of R are isomorphic to the Schützenberger groups of S and such that the restriction to S of any of Green's relations on R is the corresponding Green's relation on S.     

On the structure of some group codes

In this paper, we study the following problem: Which characteristics does a codeC possess when the syntactic monoidsyn(C ^*) of the star closureC ^* ofC is a group? For a codeC, if the syntactic monoidsyn(C ^*) is a group, then we callC a group code. This definition of a group code is different from the one in [1] (see [1], 46–47). Schützenberger had characterized the structure of finite group codes and had proved thatC is a finite group code if and only ifC is a full uniform code (see [5], [8]). Fork-prefix andk-suffix codes withk≥2,k-infix,k-outfix,p-infix,s-infix, right semaphore codes and left semaphore codes, etc., we obtain similar results. It is proved that the above mentioned codes are group codes if and only if they are uniform codes.     

The automorphism group of the graph of anR class

IfS is anX generated semigroup andm∈S, then one can represent theR class ofm by a labeled digraph, called theR graph ofm. We show that the Schützenberger group of theH class ofm embeds in the automorphism group of theR graph ofm, and that the embedding is an isomorphism ifm is a regular element.     

The regular part of a semigroup of transformations with restricted range

Let T(X) be the full transformation semigroup on the set X and let T(X,Y) be the semigroup consisting of all total transformations from X into a fixed subset Y of X. It is known that $$F(X, Y)=\{\alpha\in T(X, Y): X\alpha\subseteq Y\alpha\},$$ is the largest regular subsemigroup of T(X,Y) and determines Green??s relations on T(X,Y). In this paper, we show that F(X,Y)?T(Z) if and only if X=Y and |Y|=|Z|; or |Y|=1=|Z|, and prove that every regular semigroup S can be embedded in F(S ¹,S). Then we describe Green??s relations and ideals of F(X,Y) and apply these results to get all of its maximal regular subsemigroups when Y is a nonempty finite subset of X.     

McAlister's P-Theorem via Schützenberger Graphs

Abstract

We give a short proof, using Schützenberger graphs, of McAlister's P-theorem. The proof, when restricted to free inverse semigroups, turns into Munn's geometric multiplication of Munn trees.