# Two-variable word equations

Lucian Ilie; Wojciech Plandowski

RAIRO - Theoretical Informatics and Applications (2010)

- Volume: 34, Issue: 6, page 467-501
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topIlie, Lucian, and Plandowski, Wojciech. "Two-variable word equations." RAIRO - Theoretical Informatics and Applications 34.6 (2010): 467-501. <http://eudml.org/doc/222085>.

@article{Ilie2010,

abstract = {
We consider languages expressed by word equations in two variables and give a complete
characterization for their complexity functions, that is, the functions that give the number of
words of the same length. Specifically, we prove that there are only five types of complexities:
constant, linear, exponential, and two in between constant and linear. For the latter two, we
give precise characterizations in terms of the number of solutions of Diophantine equations of
certain types. In particular, we show that the linear upper bound on the non-exponential
complexities by Karhumäki et al. in [9], is tight. There are several consequences of our study.
First, we derive that both of the sets of all finite Sturmian words and of all finite Standard
words are expressible by word equations. Second, we characterize the languages of non-exponential
complexity which are expressible by two-variable word equations as finite unions of several
simple parametric formulae and solutions of a two-variable word equation with a finite graph.
Third, we find optimal upper bounds on the solutions of (solvable) two-variable word equations,
namely, linear bound for one variable and quadratric for the other. From this, we obtain an
$\mathcal\{O\}(n^6)$ algorithm for testing the solvability of two-variable word equations, improving thus very
much Charatonik and Pacholski's $\mathcal\{O\}(n^100)$ algorithm from [3].
},

author = {Ilie, Lucian, Plandowski, Wojciech},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Word equation; expressible language; complexity function; minimal solution;
solvability.; word equations; Sturmian words},

language = {eng},

month = {3},

number = {6},

pages = {467-501},

publisher = {EDP Sciences},

title = {Two-variable word equations},

url = {http://eudml.org/doc/222085},

volume = {34},

year = {2010},

}

TY - JOUR

AU - Ilie, Lucian

AU - Plandowski, Wojciech

TI - Two-variable word equations

JO - RAIRO - Theoretical Informatics and Applications

DA - 2010/3//

PB - EDP Sciences

VL - 34

IS - 6

SP - 467

EP - 501

AB -
We consider languages expressed by word equations in two variables and give a complete
characterization for their complexity functions, that is, the functions that give the number of
words of the same length. Specifically, we prove that there are only five types of complexities:
constant, linear, exponential, and two in between constant and linear. For the latter two, we
give precise characterizations in terms of the number of solutions of Diophantine equations of
certain types. In particular, we show that the linear upper bound on the non-exponential
complexities by Karhumäki et al. in [9], is tight. There are several consequences of our study.
First, we derive that both of the sets of all finite Sturmian words and of all finite Standard
words are expressible by word equations. Second, we characterize the languages of non-exponential
complexity which are expressible by two-variable word equations as finite unions of several
simple parametric formulae and solutions of a two-variable word equation with a finite graph.
Third, we find optimal upper bounds on the solutions of (solvable) two-variable word equations,
namely, linear bound for one variable and quadratric for the other. From this, we obtain an
$\mathcal{O}(n^6)$ algorithm for testing the solvability of two-variable word equations, improving thus very
much Charatonik and Pacholski's $\mathcal{O}(n^100)$ algorithm from [3].

LA - eng

KW - Word equation; expressible language; complexity function; minimal solution;
solvability.; word equations; Sturmian words

UR - http://eudml.org/doc/222085

ER -

## References

top- D. Angluin, Finding patterns common to a set of strings. J. Comput. System Sci.21 (1980) 46-62.
- 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.
- W. Charatonik and L. Pacholski, Word equations with two variables, in Proc. of IWWERT'91, edited by H. Abdulrab and J.P. Pecuchet. Springer, Berlin, Lecture Notes in Comput. Sci.667 (1991) 43-57.
- 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.
- A. de Luca and F. Mignosi, Some combinatorial properties of sturmian words. Theoret. Comput. Sci.136 (1994) 361-385.
- 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.
- Yu.I. Hmelevskii, Equations in free semigroups. Trudy Mat. Inst. Steklov107 (1971). English transl. Proc Steklov Inst. of Mathematics107 (1971). Amer. Math. Soc. (1976).
- T. Jiang, A. Salomaa, K. Salomaa and S. Yu, Decision problems for patterns. J. Comput. System Sci.50 (1995) 53-63.
- 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.
- A. Koscielski and L. Pacholski, Complexity of Makanin's algorithm. J. ACM43 (1996) 670-684.
- M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, MA (1983).
- 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).
- 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).
- A. Razborov, On systems of equations in a free group. Math. USSR Izvestija25 (1985) 115-162.
- A. Razborov, On systems of equations in a free group. Ph.D. Thesis, Moscow State University (1987).
- W. Sierpinski, Elementary Theory of Numbers. Elseviers Science Publishers B.V., Amsterdam, and PWN - Polish Scientific Publishers, Warszawa (1988).

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.