Subdirect products of free semigroups and monoids

Abstract

Subdirect products are special types of subalgebras of direct products. The purpose of this thesis is to initiate a study of combinatorial properties of subdirect products and fiber products of semigroups and monoids, motivated by the previous work on free groups, and some recent advances in general algebra.

In Chapter 1, we outline the necessary preliminary definitions and results, including elements of algebraic semigroup theory, formal language theory, automata theory and universal algebra.

In Chapter 2, we consider the number of subsemigroups and subdirect products of ℕ헑ℕ up to isomorphism. We obtain uncountably many such objects, and characterise the finite semigroups 혚 for which ℕ헑혚 has uncountable many subsemigroups and subdirect products up to isomorphism.

In Chapter 3, we consider particular finite generating sets for subdirect products of free semigroups introduced as "sets of letter pairs". We classify and count these sets which generate subdirect and fiber products, and discuss their abundance.

In Chapter 4, we consider finite generation and presentation for fiber products of free semigroups and monoids over finite fibers. We give a characterisation for finite generation of the fiber product of two free monoids over a finite fiber, and show that this implies finite presentation. We show that the fiber product of two free semigroups over a finite fiber is never finitely generated, and obtain necessary conditions on an infinite fiber for finite generation.

In Chapter 5, we consider the problem of finite generation for fiber products of free semigroups and monoids over a free fiber. We construct two-tape automata which we use to determine the language of indecomposable elements of the fiber product, which algorithmically decides when they are finitely generated.

Finally in Chapter 6, we summarise our findings, providing some further questions based on the results of the thesis.

Date of Award	1 Dec 2021
Original language	English
Awarding Institution	University of St Andrews
Supervisor	Nik Ruskuc (Supervisor)