Geodesic
On maximal chains of systems of word equations
Trudy Matematicheskogo Instituta imeni V.A. Steklova, Algorithmic aspects of algebra and logic, Tome 274 (2011), pp. 130-136.

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider systems of word equations and their solution sets. We discuss some fascinating properties of those, namely the size of a maximal independent set of word equations, and proper chains of solution sets of those. We recall the basic results, extend some known results and formulate several fundamental problems of the topic. 
@article{TM_2011_274_a7,
     author = {Juhani Karhum\"aki and Aleksi Saarela},
     title = {On maximal chains of systems of word equations},
     journal = {Trudy Matematicheskogo Instituta imeni V.A. Steklova},
     pages = {130--136},
     publisher = {mathdoc},
     volume = {274},
     year = {2011},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/TM_2011_274_a7/}
}
TY  - JOUR
AU  - Juhani Karhumäki
AU  - Aleksi Saarela
TI  - On maximal chains of systems of word equations
JO  - Trudy Matematicheskogo Instituta imeni V.A. Steklova
PY  - 2011
SP  - 130
EP  - 136
VL  - 274
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TM_2011_274_a7/
LA  - en
ID  - TM_2011_274_a7
ER  - 
%0 Journal Article
%A Juhani Karhumäki
%A Aleksi Saarela
%T On maximal chains of systems of word equations
%J Trudy Matematicheskogo Instituta imeni V.A. Steklova
%D 2011
%P 130-136
%V 274
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TM_2011_274_a7/
%G en
%F TM_2011_274_a7
Juhani Karhumäki; Aleksi Saarela. On maximal chains of systems of word equations. Trudy Matematicheskogo Instituta imeni V.A. Steklova, Algorithmic aspects of algebra and logic, Tome 274 (2011), pp. 130-136. http://geodesic.mathdoc.fr/item/TM_2011_274_a7/

[1] Albert M.H., Lawrence J., “A proof of Ehrenfeucht's conjecture”, Theor. Comput. Sci., 41:1 (1985), 121–123 | DOI | MR | Zbl

[2] Culik K., II, Karhumäki J., “Systems of equations over a free monoid and Ehrenfeucht's conjecture”, Discr. Math., 43:2–3 (1983), 139–153 | DOI | MR | Zbl

[3] Czeizler E., “Multiple constraints on three and four words”, Theor. Comput. Sci., 391:1–2 (2008), 14–19 | DOI | MR | Zbl

[4] Czeizler E., Karhumäki J., “On non-periodic solutions of independent systems of word equations over three unknowns”, Intern. J. Found. Comput. Sci., 18:4 (2007), 873–897 | DOI | MR | Zbl

[5] Czeizler E., Plandowski W., “On systems of word equations over three unknowns with at most six occurrences of one of the unknowns”, Theor. Comput. Sci., 410:30–32 (2009), 2889–2909 | DOI | MR | Zbl

[6] Guba V.S., “Ekvivalentnost beskonechnykh sistem uravnenii v svobodnykh gruppakh i polugruppakh konechnykh podsistem”, Mat. zametki, 40:3 (1986), 321–324 | MR | Zbl

[7] Harju T., Karhumäki J., “Many aspects of defect theorems”, Theor. Comput. Sci., 324:1 (2004), 35–54 | DOI | MR | Zbl

[8] Harju T., Karhumäki J., Plandowski W., “Independent systems of equations”: Lothaire M., Algebraic combinatorics on words, Ch. 13, Cambridge Univ. Press, Cambridge, 2002, 443–472 | MR

[9] Harju T., Nowotka D., “On the independence of equations in three variables”, Theor. Comput. Sci., 307:1 (2003), 139–172 | DOI | MR | Zbl

[10] Khmelevskii Yu.I., Uravneniya v svobodnoi polugruppe, Tr. MIAN, 107, Nauka, M., 1971

[11] Holub Š., “Local and global cyclicity in free semigroups”, Theor. Comput. Sci., 262:1–2 (2001), 25–36 | DOI | MR | Zbl

[12] Karhumäki J., Plandowski W., “On the size of independent systems of equations in semigroups”, Theor. Comput. Sci., 168:1 (1996), 105–119 | DOI | MR | Zbl

[13] Karhumäki J., Saarela A., “An analysis and a reproof of Hmelevskii's theorem”, Developments in language theory, Proc. 12th Intern. Conf. DLT 2008, Kyoto, Sept. 16–19, 2008, Lect. Notes Comput. Sci., 5257, Springer, Berlin, 2008, 467–478 | DOI | MR | Zbl

[14] Makanin G.S., “Problema razreshimosti uravnenii v svobodnoi polugruppe”, Mat. sb., 103:2 (1977), 147–236 | MR | Zbl

[15] Matiyasevich Yu.V., “Diofantovost perechislimykh mnozhestv”, DAN SSSR, 191:2 (1970), 279–282 | Zbl

[16] Plandowski W., “Test sets for large families of languages”, Developments in language theory, Proc. 7th Intern. Conf. DLT 2003, Szeged (Hungary), July 7–11, 2003, Lect. Notes Comput. Sci., 2710, Springer, Berlin, 2003, 75–94 | DOI | MR | Zbl

[17] Plandowski W., “Satisfiability of word equations with constants is in PSPACE”, J. ACM, 51:3 (2004), 483–496 | DOI | MR | Zbl

[18] Saarela A., “On the complexity of Hmelevskii's theorem and satisfiability of three unknown equations”, Developments in language theor, Proc. 13th Intern. Conf. DLT 2009, Stuttgart, June 30–July 3, 2009, Lect. Notes Comput. Sci., 5583, Springer, Berlin, 2009, 443–453 | DOI | MR | Zbl