Two-variable word equations
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 34 (2000) no. 6, pp. 467-501.
@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},
     pages = {467--501},
     publisher = {EDP-Sciences},
     volume = {34},
     number = {6},
     year = {2000},
     mrnumber = {1844714},
     zbl = {0977.68070},
     language = {en},
     url = {http://archive.numdam.org/item/ITA_2000__34_6_467_0/}
}
TY  - JOUR
AU  - Ilie, Lucian
AU  - Plandowski, Wojciech
TI  - Two-variable word equations
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2000
SP  - 467
EP  - 501
VL  - 34
IS  - 6
PB  - EDP-Sciences
UR  - http://archive.numdam.org/item/ITA_2000__34_6_467_0/
LA  - en
ID  - ITA_2000__34_6_467_0
ER  - 
%0 Journal Article
%A Ilie, Lucian
%A Plandowski, Wojciech
%T Two-variable word equations
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2000
%P 467-501
%V 34
%N 6
%I EDP-Sciences
%U http://archive.numdam.org/item/ITA_2000__34_6_467_0/
%G en
%F 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) no. 6, pp. 467-501. http://archive.numdam.org/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 | Zbl

[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 | Zbl

[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 | Zbl

[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

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

[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

[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 | Zbl

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

[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

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

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

[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 | Zbl

[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 | Zbl

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

[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 | Zbl