Semigroups and Languages

Preface

Contents

A new topological representation for free profinite -trivial semigroups in terms of spaces of vertex-labeled complete binary trees is obtained. Such a tree may be naturally folded into a finite automaton if and only if the element it represents is an ω-term. The variety of ω-semigroups generated by all finite -trivial semigroups, with the usual interpretation of the ω-power, is then studied. A simple infinite basis of identities is exhibited and a linear-time solution of the word problem for relatively free ω-semigroups is presented. This work is also compared with recent work of Bloom and Choffrut on transfinite words.

It is known that several problems related to the longstanding Černý conjecture on synchronizing automata can be conveniently thought of as questions about various types of transformation semigroups. Within this framework, we consider such “Černý type problems” for semigroups of order preserving or order reversing transformations of a finite chain as well as semigroups of orientation preserving or orientation reversing transformations of a finite cycle.

A transformation semigroup over a set X with N elements is said to be a near permutation semigroup if it is generated by a group of permutations on N elements and by a set of transformations of rank N – 1. In this paper we make a summary of the author’s thesis, in which are exhibited ways of checking whether those specific transformation semigroups belong to various structural classes of semigroups, just by analysis of the generators and without first having to generate them.

In this paper we describe how independence algebras could have been discovered and how υ*-algebras probably were discovered. We also provide a set of equivalent definitions for independence algebras (and hence for υ*-algebras) and mention some of the uses of these algebras in semigroup theory.

The notion of abelian kernel of a finite monoid extends the notion of derived subgroup of a finite group. Extensions to finite monoids of the notions of solvable group and derived length of a solvable group appear then naturally. In this paper we study these notions for some classes of finite monoids.

What is the untangling effect on a braid if one is allowed to snip a string, or if two specified strings are allowed to pass through each other, or even allowed to merge and part as newly reconstituted strings? To calculate the effects, one works in an appropriate factorizable inverse monoid, some aspects of a general theory of which are discussed in this paper. The coset monoid of a group arises, and turns out to have a universal property within a certain class of factorizable inverse monoids. This theory is dual to the classical construction of fundamental inverse semigroups from semilattices. In our braid examples, we will focus mainly on the “merge and part” alternative, and introduce a monoid which is a natural preimage of the largest factorizable inverse submonoid of the dual symmetric inverse monoid on a finite set, and prove that it embeds in the coset monoid of the braid group.

We begin with a brief introduction to the theory of word hyperbolic groups. We then consider four possible conditions which might reasonably be used as definitions or partial definitions of hyperbolicity in semigroups: having a hyperbolic Cayley graph; having hyperbolic Schützenberger graphs; having a context-free multiplication table; or having word hyperbolic maximal subgroups. Our main result is that these conditions coincide in the case of finitely generated completely simple semigroups.

Thirty years ago, in 1972, H.E. Scheiblich published the first usable description of the free inverse semigroup on a set. This led to a flowering of research on inverse semigroups, including the structure of E-unitary inverse semigroups. In a similar fashion, the publication of the book “Inverse semigroups: the theory of partial symmetry” by Mark V. Lawson, and, in particular, the chapters on applications of inverse semigroups to tilings have led to another flowering of research; this time into the theory of E*-unitary inverse semigroups. This talk will give an introduction to the later theory in the light of the earlier perspective that grew from Scheiblich’s result.

Let 𝔅_n be an aperiodic Brandt semigroup where G is the trivial group, n ∈ ℕ and P = (a_ij)_n×n with a_ij = 1_G if i = j and a_ij = 0 otherwise. The maximum size of an independent set in 𝔅_n is known to be [n²/4] + n, where [n²/4] denotes the largest integer not greater than n²/4. We reprove this result using Turán’s famous graph theorem. Moreover, we give a characterization of all independent sets in 𝔅_n with size [n²/4] + n.

We provide an exposition of the approach to the structure theory of semigroups through semilattice decompositons. This approach was introduced by A. H. Clifford, extended by T. Tamura and others including M. Petrich, and, in particular, by the members of the Niš school of semigroup theory, headed by S. Bogdanović. An emphasis is placed on the author’s results some published in various articles, and some appearing for the first time in print in her book “Semilattices of Archimedean Semigroups”.

No abstract received.

There has been much work done recently on the action of semigroups on sets with some important applications to, for example, the theory and structure of semigroup amalgams. It seems natural to consider the actions of semigroups on sets ‘with structure’ and in particular on graphs and trees. The theory of group actions has proved a powerful tool in combinatorial group theory and it is reasonable to expect that useful techniques in semigroup theory may be obtained by trying to ‘port’ the Bass-Serre theory to a semigroup context. Given the importance of transitivity in the group case, we believe that this can only reasonably be achieved by restricting our attention to the class of inverse semigroups. However, it very soon becomes apparent that there are some fundamental differences with inverse semigroup actions and even such basic notions such as free actions have to be treated carefully. We make a start on this topic in this paper by first of all recasting some of Schein’s work on representations by partial homomorphisms in terms of actions and then trying to ‘mimic’ some of the basic ideas from the group theory case. We hope to expand on this in a future paper [5].

We give a modern proof of Stiffler’s classical results describing the pseudovarieties of -trivial semigroups and locally -trivial semigroups as the wreath product closures of semilattices, respectively semilattices and right zero semigroups. Our proof uses the derived category of a functor developed by the author with B. Tilson. We prove a more general result describing functors between finite categories which are injective on coterminal -equivalent elements.