Semigroup Theory Splinter Group and Satellite Seminar

at the 60th British Mathematical Colloquium, University of York, 25-28 March 2008

A large splinter group and satellite seminar on Semigroup Theory was held as part of the 60th British Mathematical Colloquium, at the University of York from 25th-28th March 2008. It was organised by Vicky Gould, Mark Kambites and Mark Lawson, and consisted of half-hour research talks by 16 speakers from 12 universities in 7 countries. This page contains abstracts for all the talks, and slides and other supporting material where available. For general information about the BMC please see the main BMC website.

Programme

Splinter Group on Wednesday 26th March 2008 (chair: Nik Ruskuc)
14:00John Fountain (York) - Reflection monoids (slides in PDF format)
14:30 Des FitzGerald (Tasmania) - Representing inverse semigroups by block permutations (slides in Powerpoint format)
15:00 Chris Hollings (Lisbon) - Partial actions of inverse monoids on K-rings (slides in PDF format)
15:30 Mark Kambites (Manchester) - The word problem is not so hard after all (slides in PDF format)
16:00Tea / Coffee
16:30 Claas Röver (NUI Galway) - Syntactic monoids of context-free languages and groups
17:00 Alexei Vernitski (Essex) - A problem in a free group related to the Andrews-Curtis conjecture
17:30Close

Splinter Group on Thursday 27th March 2008 (chair: Stuart Margolis)
14:00 Nik Ruskuc (St Andrews) - Diagonal acts and applications (slides in PDF format)
14:30 Alan Cain (St Andrews) - Automatic presentations for semigroups (slides in PDF format)
15:00 James Mitchell (St Andrews) - The Bergman property for semigroups (slides in PDF format)
15:30 Victor Maltcev (St Andrews) - Existentially closed semigroups with Bergman's property (slides in PDF format)
16:00Tea / Coffee
16:30 Elaine Render (Manchester / Mons-Hainaut) - Polycyclic and bicyclic monoid automata (slides in PDF format)
17:00 Chrystopher Nehaniv (Hertfordshire) - Analogues of the decimal expansion for all groups and monoids
17:30Close

Satellite Seminar on Friday 28th March 2008 (chair: John Fountain)
14:00 Stuart Margolis (Bar Ilan) - Subgroups of free idempotent generated semigroups need not be free (accompanying note in PDF format)
14:30 Valdis Laan (Tartu) - Morita equivalence of partially ordered monoids (slides in PDF format)
15:00 Robert Gray (St Andrews) - Approaching cosets using Green's relations and Schutzenberger groups (slides in PDF format)
15:30 Mark Lawson (Heriot-Watt) - Primitive partial permutation representations of the polycyclic monoids (slides in PDF format)
16:00Tea / Coffee / Close

Abstracts


Alan J. Cain Automatic presentations for semigroups

An automatic presentation is a description of a relational structures using regular languages. Informally, an automatic presentation consists of a regular language of abstract representatives for the elements of the structure, such that each relation (of arity n, say) can be recognized by a synchronous n-tape automaton. The concept, which arose from computer scientists' need to extend finite model theory to infinite structures, has only recently been applied to algebraic stuctures. This talk will introduce and survey automatic presentations for semigroups. In particular, it will discuss: (1) classifications of those semigroups of certain species that admit automatic presentations; (2) the interaction of automatic presentations and various semigroup constructions; and (3) decision problems.


Des FitzGerald. Representing inverse semigroups by block permutations

The symmetric inverse monoid has a counterpart in the category dual to the category of sets, the monoid of block permutations. Although the two share some common features as extensions of the symmetric group and vehicles for representations of inverse semigroups, the monoid of block permutations presently lacks a theory of representation comparable with Schein's theory for partial permutations. I shall explain the problems, and examine what can be done.


John Fountain. Reflection monoids

The inverse monoid of all partial isomorphisms of a vector space V is denoted by ML(V). A partial reflection is defined to be the restriction of a reflection of V to a subspace of V, and a reflection monoid is a factorisable inverse submonoid of ML(V) generated by partial reflections. A reflection monoid can be characterised by two pieces of data: a reflection group W acting on V and a collection of subspaces of V that forms a W-invariant semilattice and contains V itself. In the talk we will outline the basic properties of reflection monoids and give some examples. We also mention connections with Renner monoids.


Robert Gray. Approaching cosets using Green's relations and Schutzenberger groups

One of the most fundamental concepts in combinatorial group theory is the notion of index. The index of a subgroup is found by counting its right (or left) cosets. It may be thought of as providing a way of measuring the difference between a group and a subgroup. In this sense, we can think of finite index subgroups as only differing from their parent group by a finite amount. Many finiteness conditions are known to be preserved under taking finite index subgroups and extensions, including: finite generation / presentability, periodicity, local finiteness, residual finiteness, and having a soluble word problem. Over the past decade or so, several attempts have been made to develop an analogous theory of index for semigroups. In my talk I shall discuss two such approaches (and some recent results relating to them) which arise from two different ways of thinking about what coset should mean for semigroups. The first approach is to think of cosets as being right translates of the substructure under the action of the semigroup on subsets. This approach is restricted in the sense that it only applies usefully to subgroups of semigroups (and not arbitrary subsemigroups). The second approach is a notion of index (which is called the Green index) that arises from a generalised form of Green's relations, where Green's relations are taken relative to a given subsemigroup. This approach has the advantage that it applies to arbitrary subsemigroups. In both cases, theorems exist relating the properties of the semigroup, its subsemigroups, and certain Schutzenberger groups.


Christopher Hollings. Partial Actions of Inverse Monoids on K-Rings

The partial actions of groups on K-rings (a.k.a. associative K-algebras) have been studied by Dokuchaev and Exel (2005), as a purely algebraic version of earlier work on the partial actions of groups on C*-algebras. In particular, Dokuchaev and Exel address the perennial problem of constructing an action from a partial action, which in this case is termed the 'enveloping action' of the given partial action. In this talk, I will set up appropriate definitions for the partial actions of inverse monoids on K-rings and describe the construction of enveloping actions for such partial actions.


Mark Kambites. The word problem is not so hard after all

It is well-known that one can construct finitely presented monoids for which the word problem is arbitrarily hard. But how hard is the word problem for a typical finitely presented monoid? It transpires that a randomly chosen finite presentation will with high probability satisfy certain small overlap conditions of the kind introduced by J.H.Remmers. We introduce a new, combinatorial approach to the study of small overlap presentations, which allows us to show amongst other things that the corresponding word problems are solvable in linear time.


Valdis Laan. Morita equivalence of partially ordered monoids

We say that partially ordered monoids (pomonoids) S and T are Morita equivalent if the categories of right S-posets and right T-posets are equivalent as categories enriched over the category of partially ordered sets. The classical theory of Morita equivalence deals with rings and modules. In the beginning of 1970's, Knauer initiated the study of Morita equivalent monoids. It turns out that several classical results have their analogues also in the case of pomonoids.

Mark V Lawson. Primitive partial permutation representations of the polycyclic monoids

We generalise the group theoretic notion of a primitive permutation representation to inverse monoids. Such representations are shown to be determined by the proper maximal closed inverse submonoids. We characterise all such submonoids of the polycyclic monoids and relate our results to the work of Kawamura on certain kinds of representations of the Cuntz C*-algebras, and to the branching function systems of Bratteli and Jorgensen.


Victor Maltcev. Existentially closed semigroups with Bergman's property

In this talk we will discuss existentially closed semigroups. A semigroup S is existentially closed if every countable collection of equations and inequations that is soluble in a semigroup containing S is soluble in S. Analogous notions are used widely in many different branches of mathematics, for example, the random graph is an existentially closed structure. The existence of such semigroups will be considered. For example, answering a question of Cornulier, we will show that assuming the continuum hypothesis there is only one existentially closed group with order the least uncountable cardinal. We will also see that in the varieties of semigroups, groups, and inverse semigroups every existentially closed semigroup has Bergman's property.


Stuart W Margolis. Subgroups of Free Idempotent Generated Semigroups Need Not Be Free

As part of his deep theory of biordered sets and inductive groupoids, Nambooripad described the structure of the free regular idempotent generated semigroup RIG(E) on a biordered set E. In this talk we describe topological methods for computing the maximal subgroups of RIG(E) by associating a 2-complex with E whose fundamental groups are indeed the maximal subgroups. The one-skeleton of our 2-complex is a graph associated to completely 0-semigroups that was discovered independently by Graham and Houghton. It turns out that the 2-complexes are all squared complexes, that is all 2-cells have boundaries of length 4. Such complexes have been extensively studied in recent years in topology. We give the first examples of biordered sets E such that RIG(E)has non-free subgroups. One example arises from a certain geometric configuration over a finite dimensional vector space over the field of order two corresponding (somewhat mysteriously) to the embedding of a square complex on the surface of a torus and in which we find a maximal subgroup isomorphic to the fundamental group of the torus, namely, the free Abelian group of rank 2. Another example looks at the biordered set of the multiplicative monoid of 3-by-3 matrices over a field F in which we find a maximal subgroup isomorphic to the multiplicative group of the field. This is joint work with Mark Brittenham and John Meakin of the University of Nebraska, Lincoln


James Mitchell. The Bergman property for semigroups

In this talk, we will discuss the Bergman property for semigroups and the associated notions of cofinality and strong confinality. An uncountably infinite semigroup S is said to have the Bergman property if for all generating sets U there exists a number n so that every element of S is a product of at most n elements of U. We will see that the semigroup of all mappings on an infinite set has the Bergman property but that its finitary power semigroup does not; the symmetric inverse semigroup on an infinite set and its finitary power semigroup have the Bergman property; the Baer-Levi semigroup does not have the Bergman property.


Chrystopher L Nehaniv. Analogues of the Decimal Expansion for All Groups and Monoids

We explain how Krohn-Rhodes Theory for finite semigroups and automata and Frobenius-Lagrange embeddings for finite groups can viewed as providing *coordinate systems* for understanding and manipulating these structures. These, and analogues of these theorems proved for all, possibly infinite, semigroups and groups, can be considered analogues of the decimal expansion in which coordinates correspond to a sequence of divisors of the original structure. These are related to level-transitive spherically homogeneous actions on order-theoretic rooted trees. In the case of countably generated monoids and groups the existence of such an action on a finitely branching rooted tree of depth with order type of the natural numbers is equivalent to residual finiteness. Moreover, every group arises in such coordinates where the coordinates lie in simple groups.


Elaine Render. Polycyclic and bicyclic monoid automata

We study the classes of languages defined by valence automata with rational target sets (or equivalently, regular valence grammars with rational target sets), where the valence monoid is drawn from the important class of polycyclic monoids. We show that for polycyclic monoids of rank 2 or more, such automata accept exactly the context-free languages. For the polycyclic monoid of rank 1 (that is, the bicyclic monoid), they accept a class of languages strictly including the partially blind one-counter languages. Key to the proof is a description of the rational subsets of polycyclic and bicyclic monoids, other consequences of which include the decidability of the rational subset membership problem for these monoids, and the closure of the class of rational subsets under intersection and complement. This is joint work with Mark Kambites.


Claas Roever. Syntactic Monoids of Context-Free Languages and Groups

During the study of word and co-word problems of groups syntactic monoids emerged as the unifying object which led me to study the question of which groups can occur as syntactic monoids of a given class of languages. I will give some classifications in the case of deterministic context-free languages and report on interesting examples that occur in the case of context-free languages.


Nik Ruskuc. Diagonal Acts and Applications

The diagonal act of a semigroup S is the set SxS with an action of S defined by (x,y)s=(xs,ys). Diagonal acts were introduced by S. Bulman-Fleming in an Amer. Math. Monthly problem. I encountered them first in connection with finite generation of wreath products of semigroups. Since then, they proved to play a role in combinatorial questions concerning power semigroups, Schutzenberger products, and, most recently, ranks of direct powers of monoids.


Alexei Vernitski. A problem in a free group related to the Andrews-Curtis conjecture

Let us consider an n-tuple of elements of a free group, say, (u_1, ..., u_n). A left Nielsen transformation consists of replacing the i-th element u_i of the n-tuple by either u_j u_i or u_j^{-1} u_i for some j \neq i. I have found an algorithm solving the following problem. Problem. Given two n-tuples of elements of a free group, find out whether one of them can be tranformed into the other using left Nielsen transformations.