Two-variable word equations

Lucian Ilie; Wojciech Plandowski

RAIRO - Theoretical Informatics and Applications (2010)

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

Abstract

top
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 𝒪 ( n 6 ) algorithm for testing the solvability of two-variable word equations, improving thus very much Charatonik and Pacholski's 𝒪 ( n 1 00 ) algorithm from [3].

How to cite

top

Ilie, 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
  1. D. Angluin, Finding patterns common to a set of strings. J. Comput. System Sci.21 (1980) 46-62.  
  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.  
  3. 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.  
  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.  
  5. A. de Luca and F. Mignosi, Some combinatorial properties of sturmian words. Theoret. Comput. Sci.136 (1994) 361-385.  
  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.  
  7. Yu.I. Hmelevskii, Equations in free semigroups. Trudy Mat. Inst. Steklov107 (1971). English transl. Proc Steklov Inst. of Mathematics107 (1971). Amer. Math. Soc. (1976).  
  8. T. Jiang, A. Salomaa, K. Salomaa and S. Yu, Decision problems for patterns. J. Comput. System Sci.50 (1995) 53-63.  
  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.  
  10. A. Koscielski and L. Pacholski, Complexity of Makanin's algorithm. J. ACM43 (1996) 670-684.  
  11. M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, MA (1983).  
  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).  
  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).  
  14. A. Razborov, On systems of equations in a free group. Math. USSR Izvestija25 (1985) 115-162.  
  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).  

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.