Two-variable word equations

 Access to full text

 Full (PDF)

1. [1] D. Angluin, Finding patterns common to a set of strings. J. Comput. System Sci. 21 (1980) 46-62. Zbl0454.68108MR589803
2. [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. Zbl1096.68689MR1466181
3. [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. Zbl0925.20082MR1254274
4. [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. MR1469998
5. [5] A. de Luca and F. Mignosi, Some combinatorial properties of sturmian words. Theoret. Comput. Sci. 136 (1994) 361-385. Zbl0874.68245MR1311214
6. [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. MR1319834
7. [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). Zbl0326.02032MR393284
8. [8] T. Jiang, A. Salomaa, K. Salomaa and S. Yu, Decision problems for patterns. J. Comput. System Sci. 50 (1995) 53-63. Zbl0827.68066MR1322633
9. [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. MR1616177
10. [10] A. Koscielski and L. Pacholski, Complexity of Makanin's algorithm. J. A CM 43 (1996) 670-684. Zbl0882.68073MR1409214
11. [11] M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, MA (1983. Zbl0514.20045MR675953
12. [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). Zbl0396.20037MR470107
13. [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). Zbl0613.10044MR814741
14. [14] A. Razborov, On Systems of equations in a free group. Math. USSR Izvestija 25 (1985) 115-162. Zbl0579.20019MR755958
15. [15] A. Razborov, On Systems of equations in a free group. Ph. D. Thesis, Moscow State University (1987). Zbl0632.94030
16. [16] W. Sierpinski, Elementary Theory of Numbers. Elseviers Science Publishers B.V., Amsterdam, and PWN - Polish Scientific Publishers, Warszawa (1988). Zbl0638.10001MR930670