Semigroups, Algorithms, Automata and Languages

The following sections are included:

• Preface

• Contents

There are some remarkable similarities between the approaches to the calculation of Mal'cev and semidirect products of pseudovarieties of semigroups using relatively free profinite semigroups and pseudoidentities. These lecture notes serve to extract a common framework to deal with such operators on pseudovarieties as well as to introduce the non-specialist reader to the techniques and most important results in the area. Central to the main results is a new very general compactness theorem which extends and unifies several such results. As a new application of these results a decidability theorem for pseudovarieties of the form U^-1W is also presented.

This article presents a summary of (the main parts of) the lectures on existence varieties of regular semigroups given by the author at the Thematic Term on Semigroups, Algorithms, Automata and Languages in Coimbra, July 2001. The selection of the presented topics very much reflects the author's personal taste under the constraint of the limited time he was given. So this is by no means an attempt to give a complete overview over the field. The main emphasis is on the development of the "bi-equational" approach to orthodox, locally inverse and E-solid e-varieties. This is then applied to the study and comparison of two kinds of semidirect product operators *_r and *_rr. For other topics, the reader may consult the survey papers by Jones [19] and Trotter [36].

In this article we give an overview of the algebraic theory of recognizable languages, namely Eilenberg's variety theory and its analogue for ordered monoids due to Pin. It also includes the descriptions of varieties of finite (ordered) monoids in terms of identities and some results on the power operator and Schützenberger and Malcev products, including their interpretation in terms of languages.

This is a brief presentation of the rich topic introduced in the late eighties of discrete groups for which the product can be performed by finite automata. We focus on the simplest family of such groups, the so-called automatic groups and mention briefly the further extensions. We report at the end a few still open issues.

Let T be a subsemigroup of a semigroup S. A T-cover of S is a semigroup with a subsemigroup such that is an extension of by a group, and there is a surjective homomorphism θ from onto S which restricts to an isomorphism from onto T. Of particular interest is the case when both and S have a least group congruence, and T and can be taken to be the kernels of these congruences. This is the case when S is E-dense.

In this expository account, we consider under what conditions covers exist, and describe several constructions for covers. The special cases of E-dense, inverse and orthodox semigroups are described in some detail. The use of covers is illustrated in a proof of Reilly's structure theorem for bisimple inverse ω-semigroups, and by giving an account of McAlister's criterion for a finite orthodox semigroup to be a member of the join of the pseudovariety of aperiodic semigroups and the pseudovariety of all finite groups.

With each inverse monoid with zero S we associate a category C(S) which is a slight modification of the category Leech associated with an inverse monoid and a special case of the author's 'category action approach' to inverse semigroups. Using this category, we obtain characterisations of E*-unitary, strongly E*-unitary and E-unitary inverse monoids. Specifically, S is E*-unitary if and and only if C(S) is cancellative; S is strongly E*-unitary if and only if C(S) can be embedded in a groupoid; and, finally, S is E-unitary (with a zero adjoined) if and only if C(S) has a groupoid of fractions. We also introduce the 'universal group of an inverse semigroup' and show how this group can be used to characterise strongly E*-unitary semigroups.

A survey is given of some results on semigroup-graded rings concerning the properties of semiprimitivity (Jacobson semisimplicity) and primitivity. Emphasis is placed on rings graded by inverse semigroups and new material in this area is incorporated.

This article is based on lectures given at the Thematic Term 2001 on Algorithmic Aspects of the Theory of Semigroups and Automata in Coimbra in May of 2001, and at the Università di L'Aquila in June of 2001. It is a self contained introduction to the theory of profinite groups and profinite graphs with emphasis on algorithms on subgroups of abstract free groups.

Iteration of implicit operators on profinite algebras provides an easy way of producing interesting implicit operations which in turn can be used to construct useful pseudoidentities. This paper reviews this method of producing implicit operations and explores its usage to obtain pseudoidentity characterizations of various pseudovarieties of groups and semigroups. In particular, the Plotkin conjecture for solvable groups and characterizations of finite nilpotent groups are discussed.

In this paper we assemble some facts about radical rings which arise by sandwich multiplication using a Jacobson radical element. We find a group presentation for the Munn ring consisting of n × n matrices over ℤ_p^k, where p is prime, which employs a scalar sandwich matrix where the scalar is from pℤ_p^k, regarded as a group with respect to the circle operation.

The Constraint Satisfaction Problem provides a framework in which a wide variety of combinatorial problems can be expressed in a natural way. In the present paper, after defining the general Constraint Satisfaction Problem and giving several concrete examples, we briefly survey a recent approach to studying constraint satisfaction problems which is based on characterizing the complexity of problem classes via finite algebras and their pseudovarieties. Then we investigate the case when the finite algebra assigned to a subclass of the constraint satisfaction problem with a finite set of values turns out to be a semigroup. Here we show that the subclass is tractable if and only if the assigned semigroup is a block group; otherwise it always contains an NP-complete problem.

Let S be a finite simple semigroup represented as a Rees matrix semigroup over a group G. We show that if G is efficient (i.e. if it can be defined by a presentation 〈A | R〉 with |R| - |A| = rank(H₂(G))) then S is also efficient. We also show how to find a minimal presentation for S in this case.

In this paper, we present some computations of joins of the form where is the pseudovariety of locally trivial semigroups, H is a pseudovariety of groups, and V is a pseudovariety of semigroups satisfying some pseudoidentities. Similar results are obtained for the pseudovarieties K, of semigroups in which idempotents are left zeros, and its dual D, in place of .

This note gives an overview of the links between the study of the profinite topology of free groups and the techniques of extension of partial isomorphisms and partial actions of groups. A few open problems are also included.

We survey some known nice presentations of several monoids of partial transformations on a finite chain: we consider the monoids of all order preserving partial transformations, of all order preserving full transformations and of all order preserving injective partial transformations and also some of its natural extensions.

Automatic and hyperbolic groups are well-studied classes. They share the property that the multiplication can be described in terms of computing devices. The theory of automatic groups has been extended to automatic monoids. In this paper we consider also hyperbolic, asynchronously automatic and rational monoids. We consider the independence of the definitions from the generating set, some closure properties of the classes of asynchronously automatic and of hyperbolic monoids, the complexity of the word problem, and we describe the relation between these classes of monoids.

The consideration of ordered monoids refines the study of classes of regular languages in terms of pseudovarieties of monoids. Here we propose the ordered alternative to the power operator widely discussed for monoids.

Automata and machines in an arbitrary category of autonomous algebras are investigated by using the theory of Ω-rings. These automata include sequential (ordinary) automata and linear automata (dynamical systems). The recognizable subsets of free monoid Ω-rings are investigated. They are defined using Ω-automata as recognizers. For a subset of a free monoid Ω-ring, we define the Myhill and Nerode congruences and prove a generalization of the well-known Myhill-Nerode Theorem.

Generalizing the usual construction for group presentations, we introduce the standard 2-complex for an inverse semigroup presentation. This complex is a useful tool for understanding both the structure of the maximal subgroups and of the trace product groupoid of the inverse semigroup. Similarly, an inverse semigroup theoretic analog of the Cayley complex of a group presentation is given. Applications are given to the study of certain amalgams of inverse semigroups. Also a Reidemeister-Schreier type theorem is proved for maximal subgroups of inverse semigroups. Quasiconvexity is considered, as well.

We survey the application of finite semigroups to the description of regular languages in first-order logic and generalized first-order logic. The emphasis is on recent results, including formulas with a bounded number of variables, and contacts with computational complexity and universal algebra.

We survey different characterizations (algebraic, combinatorial, automata-theoretic, logical) of the variety DA, the class of monoids whose regular -classes form aperiodic semigroups. We study the interconnections of such characterizations and outline the importance of this variety in various computational complexity issues.

This article begins with a brief description of the beginnings of the study of decision problems. There follows a discussion of important decision problems for semigroups. Attention is then restricted to finite semigroups and in particular to the membership problem for classes of finite semigroups.