Semigroups and Formal Languages

Preface.

Conference sponsors.

Contents.

Let ε = {E₁,…,E_k} be a set of regular languages over a finite alphabet Σ. Consider morphism where Δ⁺ is the semigroup over a finite set Δ and is the finitely generated semigroup with ε as the set of generators and language concatenation as a product. We prove that the membership problem of the semigroup , the set [u] = {v ∈ Δ₊ | φ (v) = φ(u)}, is a regular language over Δ, while the set Ker(φ) = {(u,v) | u, v ∈ Δ⁺ φ(u) = φ (v)} need not to be regular. It is conjectured however that every semigroup of regular languages is automatic.

The notion of reducibility for a pseudovariety has been introduced as an abstract property which may be used to prove decidability results for various pseudovariety constructions. This paper is a survey of recent results establishing this and the stronger property of complete reducibility for specific pseudovarieties.

A P-semigroup is a semigroup construction that characterizes E-unitary inverse semigroups. We say that a P-semigroup P(G, X, Y) has almost G-invariant idempotents if X\Y is finite. In this paper we give necessary and sufficient conditions for a P-semigroup with almost G-invariant idempotents to be finitely generated. We also show that the same conditions, although necessary, are not sufficient for an arbitrary P-semigroup to be finitely generated.

Operations on regular languages have been studied for fifty years, but several major problems remain wide open. This paper surveys the semigroup approach to these problems. We consider successively the star-height problem, the Straubing-Thérien's concatenation hierarchy and the shuffle operation. On the algebraic side, we present Eilenberg's variety theory and its successive improvements, including the recent notion of -variety.

Based on an algorithm to solve systems of equations modulo proper pseudovarieties of abelian groups given in this paper, we prove that decidable pseudovarieties of abelian groups are (completely) hyperdecidable. However these pseudovarieties are shown not to be reducible for the canonical signature.

Krohn-Rhodes theory gives us a way of understanding structures described as semigroups or automata by hierarchical coordinate systems. Here we use our computational implementation of the holonomy method for the hierarchical algebraic decomposition of finite automata to study finite residue class rings R_n of integers modulo n. This computational exploration leads to allowing us to rigorously describe the detailed structure of the holonomy decomposition of R_n for all n > 0.

McAlister's P-theorem for E–unitary inverse semigroups is one of the most significant components of the structure theory for inverse semigroups: since its first appearance in 1974 several different proofs have been given and the scope of the theorem has been extended to strongly E*–unitary and strongly categorical inverse semigroups. In this paper, we prove a P–theorem for the wider class of incompressible ordered groupoids, which encompasses previous versions of the P–theorem and offers a unified proof. Moreover, the class of incompressible ordered groupoids may be of interest in its own right, and we look at examples related to Bass-Serre theory for groups.

We obtain a description of identities holding in the monoids of extensive, partial extensive and partial order-preserving extensive transformations of a finite chain. Using the description, we partially solve the finite basis problem for the monoids. Namely, we show that "almost all" these monoids are nonfinitely based.

In this work we define Magnus subsemigroups of one-relator groups as a generalisation of Magnus subgroups. In contrast with Magnus subgroups which by the Dehn-Magnus Freiheitssatz are freely generated, Magnus subsemigroups are not necessarily free. We give a necessary and sufficient condition for a Magnus subsemigroup to be free in terms of the combinatorial structure of the defining relator R, provided that the given presentation satisfies the small cancellation condition C(6)&T(4) and R is not exceptional. We use word combinatorics with analysis of van Kampen diagrams, as developed in [1].

We consider wreath product decompositions for semigroups of triangular matrices. We exhibit an explicit wreath product decomposition for the semigroup of all n × n upper triangular matrices over a given field k, in terms of aperiodic semigroups and affine groups over k. In the case that k is finite this decomposition is optimal, in the sense that the number of group terms is equal to the group complexity of the semigroup. We also obtain some decompositions for semigroups of triangular matrices over more general rings and semirings.

The work of Don McAlister has been an inspiration to all of us interested in semigroups. In 1974, Don published two papers which had a decisive impact on the subsequent development of semigroup theory. In these papers, two major theorems were proved: the 'covering theorem' and the 'P-theorem'. In this paper, we shall take the latter as the starting point for some excursions through our own and others' work.

We present several recent results on the structure of the lattice of combinatorial Rees–Sushkevich varieties. In particular, we study a natural decomposition of the lattice into a disjoint union of intervals and describe the sublattice generated by the extreme points of these intervals.

The aim of this paper is to develop the calculus of trivializers for subsemigroups. Given a finite presentation defining a semigroup S and a trivializer of the Squier complex of , we obtain an infinite trivializer of the Squier complex of a finite presentation defining a subsemigroup of S. Also, we give a method to find finite trivializers for special subsemigroups and hence to show that those subsemigroups have finite derivation type (FDT). An application of this method is given: we prove that if is a band of monoids having FDT, then so does S_α, for any α ∈Y.

In this expository talk we give some recent results on the structure of inverse semigroups endowed with a compatible semilattice ordering. In addition we consider some open questions regarding these semigroups.

Many people have studied the problem of describing all isomorphisms between transformation semigroups defined on sets and between linear transformation semigroups defined on vector spaces. In this paper, we summarise some of that work, as well as recent work showing that Baer-Levi semigroups defined on sets are never isomorphic to their linear analogue, despite all appearances to the contrary.

The first part of this paper is devoted to an account of a certain inverse monoid with zero that is a Rees quotient of a free inverse monoid; the second part describes some recent results on its contracted semigroup algebra over a field.

The notion of finite derivation type (FDT) is carried over to relative monoid presentations of the form , where is a group, T is a finite alphabet, and R is a set of rules over the free product satisfying |l|_T, |r|_T > 0 for each rule (ℓ → r) ∈ R. As an application we derive an algebraic characterization of the property FDT for monoids that are given through certain relative monoid presentations.

We initiate a systematic study of the lattices of literal varieties and pseudovarieties of homomorphisms onto monoids. The case of abelian groups is completely solved.

McAlister's P-theorem on E-unitary inverse semigroups and his theorem on E-unitary covers are among the most beautiful results in semigroup theory. They have motivated research in a lot of directions. In this paper, we present the recent attempts in generalizing the notion of almost factorizability for orthodox and for weakly ample semigroups, respectively, and summarize the results obtained.