Solutions principales et rang d’un système d’équations avec constantes dans le monoide libre. (French) Zbl 0545.20046

In order to give a far-reaching common generalization of Lentin’s and Makanin’s results concerning equations without and with constants, the author defines a system of equations over a finite alphabet \(E\cup C (E\cap C=\emptyset)\) to be a set of quadruples \((e_ i,e'\!_ i,E,C)\), \(e_ i,e'\!_ i\in(E\cup C)^*\), and a solution of this system to be a morphism \(\alpha:(E\cup C)^*\to(A\cup C)^*\) where A is arbitrary finite such that \(A\cap C=\emptyset\), \(\alpha\) acts identically on C, and \(\alpha e_ i=\alpha e'\!_ i\). All essential results carry over to this case. In particular, every solution can be derived from a unique principal solution, and the calculation of the latter ones is equivalent (at least in the case of a finite system) to finding the principal solutions of some single equation of the same rank. Thus, the rank of a system can be determined, too.
Reviewer: G.Pollák


20M05 Free semigroups, generators and relations, word problems
20M35 Semigroups in automata theory, linguistics, etc.
Full Text: DOI


[1] Angluin, D, Finding patterns common to a set of strings, J. comput. syst. sci., 21, 46-62, (1980) · Zbl 0454.68108
[2] Berstel; Perrin; Perrot; Restivo, Sur le théorème du défaut, J. algebra, 60, 1, (1979) · Zbl 0421.20027
[3] Cohn, P.M, Free rings and their relations, (1971), Academic Press New-York/London · Zbl 0232.16003
[4] Albert, J; Culik, K, Test sets for homomorphisms equivalence on context free languages, () · Zbl 0443.68069
[5] Hmelevskii, Tu.I; Hmelevskii, Tu.I; Hmelevskii, Tu.I, Equations in free semi groups, (), 107, (1971), Engl. transl. · Zbl 0326.02032
[6] Huet, G, Equations and rewrite rules: A survey, SRI, tech. rep. CSL-III, (1980)
[7] Lentin, A, Equations dans LES monoïdes libres, (1972), Gauthier-Villars paris · Zbl 0258.20058
[8] Lentin, A, Equations in free monoïds, (), 67-85 · Zbl 0269.20057
[9] Lentin, A; Schützenberger, M.P, A combinatorial problem in the theory of free monoïds, (), 128-144 · Zbl 0221.20076
[10] Lothaire, Combinatorics on words, (1982), Addison Wesley Reading, MA · Zbl 1001.68093
[11] Lyndon, R.C, Equations in free groups, Trans. amer. math. soc., 96, 445-457, (1960) · Zbl 0108.02301
[12] Lyndon, R.C; Schupp, P.E, Combinatorial group theory, (1977), Springer Berlin · Zbl 0368.20023
[13] Makanin, G.S; Makanin, G.S, The problem of solvability of equations in a free semigroup, Math. USSR sbornik, Am. math. soc., 32, 2, (1978) · Zbl 0417.20050
[14] Makanin, G.S, Algorithmic decidability of the rank of constant free equations in a free semigroup, Dokl. akad. nauk. SSSR, 243, (1978) · Zbl 0417.20050
[15] Pécuchet, J.P, Sur la détermination du rang d’une équation dans le monoïde libre, Theor. comput. sci., 16, 337-340, (1981) · Zbl 0481.20035
[16] Pécuchet, J.P, Equations avec constantes et algorithme de makanin, Thèse de 3-ième cycle, (1981), Rouen
[17] Rozenberg, G; Salomaa, A, The mathematical theory of {\scl} systems, (1980), Academic Press New-York/London
[18] Makanin, G.S; Makanin, G.S, On the rank of equations in four unknowns in a free semigroup, Mat. sb., Math. USSR sb., 29, 257-280, (1977), English translation: · Zbl 0376.20035
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.