Combinatorial and decidability questions in semigroups of words

Edmund Robertson

Abstract

Let A be a finite alphabet and let F(A) be the set of all words in A. F(A) becomes a semigroup by defining multiplication as concatenation of words. F(A) is called the free semigroup on A. Given a finite subset B of F(A), let T be the smallest subset of F(A) containing B which is closed under multiplication. We show that T need not be a free semigroup and examine questions relating to how close T is to being free. A general T may be free or may not be finitely presented. By way of contrast, if T is an ideal of S then T is never free but is always finitely presented.