×

On the defect theorem and simplifiability. (English) Zbl 0621.20033

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 M. H. Albert, 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.
Reviewer: L.Potemkin

MSC:

20M05 Free semigroups, generators and relations, word problems
20M10 General structure theory for semigroups

Citations:

Zbl 0602.68066
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] Albert, M.H., Lawrence, J.,A proof of Ehrenfeucht’s Conjecture, Theoret. Comput. Sci., to appear. · Zbl 0602.68066
[2] Almeida, J.,Some algorithms on the star operation applied to finite languages, Semigroup Forum 28 (1984), 187–197. · Zbl 0541.20044 · doi:10.1007/BF02572484
[3] Berstel, J., Perrin, D., Perrot, J.F., Restivo, A.,Sur le théorème du défaut, J. Algebra 60 (1979), 169–180. · Zbl 0421.20027 · doi:10.1016/0021-8693(79)90113-3
[4] Culik II, K., Karhumäki, J.,On test sets and the Ehrenfeucht Conjecture, Springer Lecture Notes in Computer Science 140 (1982), 128–140. · Zbl 0485.68070 · doi:10.1007/BFb0012763
[5] Culik II, K., Karhumäki, J.,Systems of equations over a free monoid and Ehrenfeucht’s Conjecture, Discrete Math. 43 (1983) 139–153. · Zbl 0528.68057 · doi:10.1016/0012-365X(83)90152-8
[6] Dubreil, P.,Sur le demi-groupe des endomorphismes d’une algèbre abstraite, Lincei-Rend. Sc. fis. mat. e nat., Vol XLVI (1969), 149–153. · Zbl 0174.30001
[7] Ehrenfeucht, A., Rozenberg, G.,Elementary homomorphisms and a solution of the DOL sequence equivalence problem, Theoret. Comput. Sci. 7 (1978), 169–183. · Zbl 0407.68085 · doi:10.1016/0304-3975(78)90047-6
[8] Guba, V.S., Personal communication (1985).
[9] Karhumäki, J.,A note on intersections of free submonoids of a free monoid, Semigroup Forum 29 (1984), 183–205. · Zbl 0555.20037 · doi:10.1007/BF02573324
[10] Lallement, G.,Semigroups and Combinatorial Applications, J. Wiley and Sons, New York, 1979.
[11] Lothaire, M.,Combinatorics on Words, Addison-Wesley, Reading, Mass., 1983. · Zbl 0514.20045
[12] Linna, M.,On the decidability of the DOL prefix problem, Internat. J. Comput. Math. A6 (1977), 127–142. · Zbl 0358.68114 · doi:10.1080/00207167708803132
[13] Markov, Al.A.,On finitely generated subsemigroups of a free semigroup, Semigroup Forum 3 (1971), 251–258. · Zbl 0225.20034 · doi:10.1007/BF02572962
[14] Perrin, D.,On the solution of Ehrenfeucht’s conjecture, Bulletin of the EATCS 27 (1985), 68–70.
[15] Salomaa, A.,The Ehrenfeucht Conjecture: a proof for language theorists, Bulletin of the EATCS 27 (1985), 71–82.
[16] Schützenberger, M.P.,Une théorie algébrique du codage, Seminaire Dubreil-Pisot, 1955/56.
[17] Skordev, D., Sendov, Bl.,On equations in words, Z. Math. Logic Grundlagen Math. 7 (1961), 289–297, (Russian). · Zbl 0119.01304 · doi:10.1002/malq.19610071902
[18] Spehner, J.C.,Quelques constructions et algorithmes relatifs aux sous-monoides d’un monoide libre, Semigroup Forum 9 (1975), 334–353. · Zbl 0298.20046 · doi:10.1007/BF02194863
[19] Spehner, J.C.,Présentations et présentations simplifiables d’un monoïde simplifiable, Semigroup Forum 14 (1977), 295–329. · Zbl 0477.20037 · doi:10.1007/BF02194675
[20] Tilson, B.,The intersection of free submonoids of free monoids is free, Semigroup Forum 4 (1972), 345–350. · Zbl 0261.20060 · doi:10.1007/BF02570808
[21] Varlet, J.,Remarks on fully invariant congruences, Colloquia Mathematica Soc. János Bolyai 17, Contributions to Universal Algebra, 515–554, North-Holland, 1977. · Zbl 0367.08004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.