# Semigroup and Automata Theory

### The relationship between the local and global structure of semigroups

#### Summary:

The main aim of this thesis is to generalise McAlister's theory of locally inverse regular semigroups to the class of semigroups with local units in which the local submonoids have commuting idempotents. We prove that if such a semigroup has what we call a McAlister sandwich function then the semigroup can be covered by means of a Rees matrix semigroup over a semigroup with commuting idempotents. Examples of such semigroups are easily constructed. Indeed, if T is a semigroup with local units having an idempotent e such that T = TeT, and eTe has commuting idempotents, then all the local submonoids of T have commuting idempotents and T is equipped with a McAlister sandwich function. We prove that the semigroups with local units having local submonoids with commuting idempotents S which can be embedded in such a semigroup T in such a way that S = STS are precisely the ones having a McAlister sandwich function.
Finally, in a different direction, we study variants of semigroups concentrating on the relationship between the local structure of a semigroup and the global structure of its variants.

#### Published in:

U.W. Bangor, Ph. D. thesis (2001).

gzipped postscript of the thesis: khan.ps.gz

### A characterisation of a class of semigroups with locally commuting idempotents

#### Abstract:

McAlister proved that a necessary and sufficient condition for a regular semigroup S to be locally inverse is that it can be embedded as a quasi-ideal in a semigroup T which satisfies the following two conditions:
(1) T = TeT, for some idempotent e; and
(2) eTe is inverse.
We generalise this result to the class of semigroups with local units in which all local submonoids have commuting idempotents.

#### Published in:

Periodica Mathematica Hungarica 40 (2000) 85-107.

### A categorical approach to Kleene's theorem

#### Abstract:

The aim of this paper is to make an analogy between propositions/proofs, and formal languages/finite state machines. In particular, we consider similarities between the connectives of linear logic, as represented in the Geometry of Interaction, and the closure properties of the languages recognised by finite state automata. Although a formal correspondence is not given, the categorical structures produced by an analysis of Kleene's theorem provide good supporting evidence for such a correspondence.

An important part of this procedure is to abstract the essential features required by the monoid of relations in order to give the closure of the regular languages under the operations described by Kleene's theorem. This opens the way to the construction of analogues of Kleene's theorem in other monoids.

#### Published in:

gzipped postscript file: 00_20.ps.gz

### The categorical theory of self-similarity

#### Abstract:

We demonstrate how the identity $N\otimes N \cong N$ in a monoidal category allows us to construct a functor from the full subcategory generated by N and \otimes to the endomorphism monoid of the object N. This provides a categorical foundation for one-object analogues of the symmetric monoidal categories used by J.-Y. Girard in his Geometry of Interaction series of papers, and explicitly described in terms of inverse semigroup theory.

This functor also allows the construction of one-object analogues of other categorical structures. We give the example of one-object analogues of the categorical trace, and compact closedness. Finally, we demonstrate how the categorical theory of self-similarity can be related to the algebraic theory, and Girard's dynamical algebra, by considering one-object analogues of projections and inclusions.

#### Published in:

Theory and Applications of Categories 6 (2001) 33-46.