On the defect theorem and simplifiability (Q1090421): Difference between revisions

It is well known that if a set of n words in a free semigroup satisfies a nontrivial relation then these words can be written as products of at most n-1 words, i.e. the set is simplifiable. A particularly sharp form is given in the defect theorem: if a finitely generated subsemigroup S of a free semigroup is not free then the smallest free subsemigroup containing S (the free envelope of S) has rank less than that of S. The authors generalize this result in some directions. They give some basic properties of F-semigroups (that is, finitely generated subsemigroups of free semigroups). Using the recently proved Ehrenfeucht conjecture [see \textit{M. H. Albert}, \textit{J. Lawrence}, Theor. Comput. Sci. 41, 121-123 (1985; Zbl 0602.68066)] the authors show that the congruences induced by endomorphisms of an F-semigroup S satisfy the maximal condition, and that all sequences of noninjective epimorphisms between F-semigroups are finite. The authors introduce also the unique factorization extension of an F-semigroup S by specifying it as the smallest F-semigroup, which contains S and in which the elements of S can be factored in a unique way. Then it is proved that this extension possesses the defect property, that is, its rank is less than that of S, if S is not free. The authors show also that if the F-semigroup S satisfies k ''different'' nontrivial relations then the free envelope and the unique factorization extension of S are generated by at most rank(S)-k words. This result is applied to systems of equations over a free semigroup and gives a general condition to ensure that all the solutions are periodic.