Equations on partial words

Francine Blanchet-Sadri; D. Dakota Blair; Rebeca V. Lewis

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2009)

  • Volume: 43, Issue: 1, page 23-39
  • ISSN: 0988-3754

Abstract

top
It is well-known that some of the most basic properties of words, like the commutativity ( x y = y x ) and the conjugacy ( x z = z y ), can be expressed as solutions of word equations. An important problem is to decide whether or not a given equation on words has a solution. For instance, the equation x m y n = z p has only periodic solutions in a free monoid, that is, if x m y n = z p holds with integers m , n , p ≥ 2 , then there exists a word w such that x , y , z are powers of w . This result, which received a lot of attention, was first proved by Lyndon and Schützenberger for free groups. In this paper, we investigate equations on partial words. Partial words are sequences over a finite alphabet that may contain a number of “do not know” symbols. When we speak about equations on partial words, we replace the notion of equality ( = ) with compatibility ( ↑ ). Among other equations, we solve x y ↑ y x , x z ↑ z y , and special cases of x m y n ↑ z p for integers m , n , p ≥ 2 .

How to cite

top

Blanchet-Sadri, Francine, Blair, D. Dakota, and Lewis, Rebeca V.. "Equations on partial words." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 43.1 (2009): 23-39. <http://eudml.org/doc/245315>.

@article{Blanchet2009,
abstract = {It is well-known that some of the most basic properties of words, like the commutativity ($xy = yx$) and the conjugacy ($xz = zy$), can be expressed as solutions of word equations. An important problem is to decide whether or not a given equation on words has a solution. For instance, the equation $x^m y^n = z^p$ has only periodic solutions in a free monoid, that is, if $x^m y^n = z^p$ holds with integers $m, n, p \ge 2$, then there exists a word $w$ such that $x, y, z$ are powers of $w$. This result, which received a lot of attention, was first proved by Lyndon and Schützenberger for free groups. In this paper, we investigate equations on partial words. Partial words are sequences over a finite alphabet that may contain a number of “do not know” symbols. When we speak about equations on partial words, we replace the notion of equality ($=$) with compatibility ($\uparrow $). Among other equations, we solve $xy \uparrow yx$, $xz \uparrow zy$, and special cases of $x^m y^n \uparrow z^p$ for integers $m, n, p \ge 2$.},
author = {Blanchet-Sadri, Francine, Blair, D. Dakota, Lewis, Rebeca V.},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {equations on words; equations on partial words; commutativity; conjugacy; free monoid},
language = {eng},
number = {1},
pages = {23-39},
publisher = {EDP-Sciences},
title = {Equations on partial words},
url = {http://eudml.org/doc/245315},
volume = {43},
year = {2009},
}

TY - JOUR
AU - Blanchet-Sadri, Francine
AU - Blair, D. Dakota
AU - Lewis, Rebeca V.
TI - Equations on partial words
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2009
PB - EDP-Sciences
VL - 43
IS - 1
SP - 23
EP - 39
AB - It is well-known that some of the most basic properties of words, like the commutativity ($xy = yx$) and the conjugacy ($xz = zy$), can be expressed as solutions of word equations. An important problem is to decide whether or not a given equation on words has a solution. For instance, the equation $x^m y^n = z^p$ has only periodic solutions in a free monoid, that is, if $x^m y^n = z^p$ holds with integers $m, n, p \ge 2$, then there exists a word $w$ such that $x, y, z$ are powers of $w$. This result, which received a lot of attention, was first proved by Lyndon and Schützenberger for free groups. In this paper, we investigate equations on partial words. Partial words are sequences over a finite alphabet that may contain a number of “do not know” symbols. When we speak about equations on partial words, we replace the notion of equality ($=$) with compatibility ($\uparrow $). Among other equations, we solve $xy \uparrow yx$, $xz \uparrow zy$, and special cases of $x^m y^n \uparrow z^p$ for integers $m, n, p \ge 2$.
LA - eng
KW - equations on words; equations on partial words; commutativity; conjugacy; free monoid
UR - http://eudml.org/doc/245315
ER -

References

top
  1. [1] J. Berstel and L. Boasson, Partial words and a theorem of Fine and Wilf. Theoret. Comput. Sci. 218 (1999) 135–141. Zbl0916.68120MR1687780
  2. [2] F. Blanchet-Sadri, Periodicity on partial words. Comput. Math. Appl. 47 (2004) 71–82. Zbl1068.68110MR2062726
  3. [3] F. Blanchet-Sadri, Codes, orderings, and partial words. Theoret. Comput. Sci. 329 (2004) 177–202. Zbl1086.68108MR2103647
  4. [4] F. Blanchet-Sadri, Primitive partial words. Discrete Appl. Math. 48 (2005) 195–213. Zbl1101.68643MR2147791
  5. [5] F. Blanchet-Sadri and Arundhati R. Anavekar, Testing primitivity on partial words. Discrete Appl. Math. 155 (2007) 179–287. Zbl1108.68093MR2303152
  6. [6] F. Blanchet-Sadri, D. Dakota Blair, and R.V. Lewis, Equations on partial words, MFCS 2006 31st International Symposium on Mathematical Foundations of Computer Science. Lect. Notes Comput. Sci. 3053 (2006) 611–622. Zbl1132.68513MR2298175
  7. [7] F. Blanchet-Sadri and Ajay Chriscoe, Local periods and binary partial words: an algorithm. Theoret. Comput. Sci. 314 (2004) 189–216. http://www.uncg.edu/mat/AlgBin/ Zbl1070.68061MR2033749
  8. [8] F. Blanchet-Sadri and S. Duncan, Partial words and the critical factorization theorem. J. Comb. Theory A 109 (2005) 221–245. http://www.uncg.edu/mat/cft/ Zbl1073.68067MR2121025
  9. [9] F. Blanchet-Sadri and R.A. Hegstrom, Partial words and a theorem of Fine and Wilf revisited. Theoret. Comput. Sci. 270 (2002) 401–419. Zbl0988.68142MR1871078
  10. [10] F. Blanchet-Sadri and D.K. Luhmann, Conjugacy on partial words. Theoret. Comput. Sci. 289 (2002) 297–312. Zbl1061.68123MR1932900
  11. [11] F. Blanchet-Sadri and N.D. Wetzler, Partial words and the critical factorization theorem revisited. Theoret. Comput. Sci. 385 (2007) 179–192. http://www.uncg.edu/mat/research/cft2/ Zbl1124.68086MR2356251
  12. [12] Y. Césari and M. Vincent, Une caractérisation des mots périodiques. C.R. Acad. Sci. Paris 268 (1978) 1175–1177. Zbl0392.20039
  13. [13] C. Choffrut and J. Karhumäki, Combinatorics of Words, in Handbook of Formal Languages, Vol. 1, Ch. 6, edited by G. Rozenberg and A. Salomaa, Springer-Verlag, Berlin (1997) 329–438. MR1469998
  14. [14] D.D. Chu and H.S. Town, Another proof on a theorem of Lyndon and Schützenberger in a free monoid. Soochow J. Math. 4 (1978) 143–146. Zbl0412.20053MR530548
  15. [15] M. Crochemore and W. Rytter, Text Algorithms. Oxford University Press, New York, NY (1994). Zbl0844.68101MR1307378
  16. [16] M. Crochemore and W. Rytter, Jewels of Stringology. World Scientific, NJ (2003). Zbl1078.68151MR2012571
  17. [17] E. Czeizler, The non-parametrizability of the word equation x y z = z v x : A short proof. Theoret. Comput. Sci. 345 (2005) 296–303. Zbl1079.68081MR2171615
  18. [18] N.J. Fine and H.S. Wilf, Uniqueness theorems for periodic functions. Proc. Amer. Math. Soc. 16 (1965) 109–114. Zbl0131.30203MR174934
  19. [19] L.J. Guibas and A.M. Odlyzko, Periods in strings. J. Comb. Theory A 30 (1981) 19–42. Zbl0464.68070MR607037
  20. [20] V. Halava, T. Harju and L. Ilie, Periods and binary words. J. Comb. Theory A 89 (2000) 298–303. Zbl0943.68128MR1741010
  21. [21] T. Harju and D. Nowotka, The equation x i = y j z k in a free semigroup. Semigroup Forum 68 (2004) 488–490. Zbl1052.20044MR2050904
  22. [22] J.I. Hmelevskii, Equations in free semigroups. Proceedings of the Steklov Institute of Mathematics 107 (1971) 1–270 (American Mathematical Society, Providence, RI (1976)). Zbl0326.02032MR393284
  23. [23] P. Leupold, Partial words: results and perspectives. GRLMC, Tarragona (2003). Zbl1040.68082
  24. [24] M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, MA (1983). Cambridge University Press, Cambridge (1997). Zbl0514.20045MR1475463
  25. [25] M. Lothaire, Algebraic Combinatorics on Words. Cambridge University Press, Cambridge (2002). Zbl1001.68093MR1905123
  26. [26] M. Lothaire, Applied Combinatorics on Words. Cambridge University Press, Cambridge (2005). Zbl1133.68067MR2165687
  27. [27] R.C. Lyndon and M.P. Schützenberger, The equation a m = b n c p in a free group. Michigan Math. J. 9 (1962) 289–298. Zbl0106.02204MR162838
  28. [28] G.S. Makanin, The problem of solvability of equations in a free semigroup. Math. USSR Sbornik 32 (1977) 129–198. Zbl0396.20037MR486227
  29. [29] A.A. Markov, The theory of algorithms. Trudy Mat. Inst. Steklov 42 (1954). Zbl0058.00501MR77473
  30. [30] G. Păun, N. Santean, G. Thierrin and S. Yu, On the robustness of primitive words. Discrete Appl. Math. 117 (2002) 239–252. Zbl1004.68127MR1881279
  31. [31] W. Plandowski, Satisfiability of word equations with constants is in NEXPTIME. Proceedings of the Annual ACM Symposium on Theory of Computing (1999) 721–725. MR1798096
  32. [32] W. Plandowski, Satisfiability of word equations with constants is in PSPACE. Proceedings of the 40th Annual Symposium on Foundations of Computer Science (1999) 495–500. MR1917589
  33. [33] E. Rivals and S. Rahmann, Combinatorics of periods in strings. J. Comb. Theory A 104 (2003) 95–113. Zbl1073.68706MR2018422
  34. [34] H.J. Shyr, Free Monoids and Languages. Hon Min Book Company, Taichung, Taiwan (1991). Zbl0746.20050MR1090325
  35. [35] H.J. Shyr and G. Thierrin, Disjunctive languages and codes. Lect. Notes Comput. Sci. 56 (1977) 171–176. Zbl0366.68049MR478794

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.