Two-variable word equations
Ilie, Lucian ; Plandowski, Wojciech
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 34 (2000), p. 467-501 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 2000-01-01
@article{ITA_2000__34_6_467_0,
     author = {Ilie, Lucian and Plandowski, Wojciech},
     title = {Two-variable word equations},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {34},
     year = {2000},
     pages = {467-501},
     mrnumber = {1844714},
     zbl = {0977.68070},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2000__34_6_467_0}
}

Ilie, Lucian; Plandowski, Wojciech. Two-variable word equations. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 34 (2000) pp. 467-501. http://gdmltest.u-ga.fr/item/ITA_2000__34_6_467_0/

[1] D. Angluin, Finding patterns common to a set of strings. J. Comput. System Sci. 21 (1980) 46-62. | MR 589803 | Zbl 0454.68108

[2] J. Berstel, Recent results in Sturmian words, edited by J. Dassow, G. Rozenberg and A. Salomaa, Developments in Language Theory II, World Sci. Publishing (1996) 13-24. | MR 1466181 | Zbl 1096.68689

[3] W. Charatonik and L. Pacholski, Word equations with two variables, in Proc. of IWW-ERT'91, edited by H. Abdulrab and J. P. Pecuchet. Springer, Berlin, Lecture Notes in Comput Sci. 667 (1991) 43-57. | MR 1254274 | Zbl 0925.20082

[4] C. Choffrut and J. Karhumäki, Combinatorics of words, edited by G. Rozenberg and A. Salomaa, Handbook of Formal Languages. Springer, Berlin (1997) 329-438. | MR 1469998

[5] A. De Luca and F. Mignosi, Some combinatorial properties of sturmian words. Theoret. Comput. Sci. 136 (1994) 361-385. | MR 1311214 | Zbl 0874.68245

[6] S. Eyono Obono, P. Goralcik and M. Maksimenko, Efficient solving of the word equations in one variable, in Proc. of MFCS'94. Springer, Berlin, Lecture Notes in Comput. Sci. 841 (1994) 336-341. | MR 1319834

[7] Yu. I. Hmelevskii, Equations in free semigroups. Trudy Mat. Inst. Steklov 107 (1971). English transl. Proc Steklov Inst. of Mathematics 107 (1971). Amer. Math. Soc. (1976). | MR 393284 | Zbl 0326.02032

[8] T. Jiang, A. Salomaa, K. Salomaa and S. Yu, Decision problems for patterns. J. Comput. System Sci. 50 (1995) 53-63. | MR 1322633 | Zbl 0827.68066

[9] J. Karhumäki, F. Mignosi and W. Plandowski, The expressibility of languages and relations by word equations, in Proc. of ICALP'97. Springer, Berlin, Lecture Notes in Comput. Sci. 1256 (1997) 98-109. | MR 1616177

[10] A. Koscielski and L. Pacholski, Complexity of Makanin's algorithm. J. A CM 43 (1996) 670-684. | MR 1409214 | Zbl 0882.68073

[11] M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, MA (1983. | MR 675953 | Zbl 0514.20045

[12] G. S. Makanin, The problem of solvability of equations in a free semigroup. Mat. Sb. 103 (1977) 147-233. English transl, in Math. U.S.S.R. Sb. 32 (1977). | MR 470107 | Zbl 0396.20037

[13] G. Rauzy, Mots infinis en arithmetique, edited by M. Nivat and D. Perrin, Automata on infinite words. Springer, Berlin, Lecture Notes in Comput. Sci. 192 (1984). | MR 814741 | Zbl 0613.10044

[14] A. Razborov, On Systems of equations in a free group. Math. USSR Izvestija 25 (1985) 115-162. | MR 755958 | Zbl 0579.20019

[15] A. Razborov, On Systems of equations in a free group. Ph. D. Thesis, Moscow State University (1987).

[16] W. Sierpinski, Elementary Theory of Numbers. Elseviers Science Publishers B.V., Amsterdam, and PWN - Polish Scientific Publishers, Warszawa (1988). | MR 930670 | Zbl 0638.10001