Equations on partial words

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

RAIRO - Theoretical Informatics and Applications (2007)

  • 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 (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 xMyN = zP has only periodic solutions in a free monoid, that is, if xMyN = zP 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 xy ↑ yx, xz ↑ zy, and special cases of xmyn ↑ zp for integers m,n,p ≥ 2. 


How to cite

top

Blanchet-Sadri, Francine, Dakota Blair, D., and Lewis, Rebeca V.. "Equations on partial words." RAIRO - Theoretical Informatics and Applications 43.1 (2007): 23-39. <http://eudml.org/doc/92906>.

@article{Blanchet2007,
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 xMyN = zP has only periodic solutions in a free monoid, that is, if xMyN = zP 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 xy ↑ yx, xz ↑ zy, and special cases of xmyn ↑ zp for integers m,n,p ≥ 2. 
},
author = {Blanchet-Sadri, Francine, Dakota Blair, D., Lewis, Rebeca V.},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Equations on words; equations on partial words; commutativity; conjugacy; free monoid.; equations on words; commutativity; free monoid},
language = {eng},
month = {12},
number = {1},
pages = {23-39},
publisher = {EDP Sciences},
title = {Equations on partial words},
url = {http://eudml.org/doc/92906},
volume = {43},
year = {2007},
}

TY - JOUR
AU - Blanchet-Sadri, Francine
AU - Dakota Blair, D.
AU - Lewis, Rebeca V.
TI - Equations on partial words
JO - RAIRO - Theoretical Informatics and Applications
DA - 2007/12//
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 xMyN = zP has only periodic solutions in a free monoid, that is, if xMyN = zP 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 xy ↑ yx, xz ↑ zy, and special cases of xmyn ↑ zp for integers m,n,p ≥ 2. 

LA - eng
KW - Equations on words; equations on partial words; commutativity; conjugacy; free monoid.; equations on words; commutativity; free monoid
UR - http://eudml.org/doc/92906
ER -

References

top
  1. J. Berstel and L. Boasson, Partial words and a theorem of Fine and Wilf. Theoret. Comput. Sci.218 (1999) 135–141.  
  2. F. Blanchet-Sadri, Periodicity on partial words. Comput. Math. Appl.47 (2004) 71–82.  
  3. F. Blanchet-Sadri, Codes, orderings, and partial words. Theoret. Comput. Sci.329 (2004) 177–202.  
  4. F. Blanchet-Sadri, Primitive partial words. Discrete Appl. Math.48 (2005) 195–213.  
  5. F. Blanchet-Sadri and Arundhati R. Anavekar, Testing primitivity on partial words. Discrete Appl. Math.155 (2007) 179–287.  
  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.  
  7. F. Blanchet-Sadri and Ajay Chriscoe, Local periods and binary partial words: an algorithm. Theoret. Comput. Sci.314 (2004) 189–216.  URIhttp://www.uncg.edu/mat/AlgBin/
  8. F. Blanchet-Sadri and S. Duncan, Partial words and the critical factorization theorem. J. Comb. Theory A109 (2005) 221–245.  URIhttp://www.uncg.edu/mat/cft/
  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.  
  10. F. Blanchet-Sadri and D.K. Luhmann, Conjugacy on partial words. Theoret. Comput. Sci.289 (2002) 297–312.  
  11. F. Blanchet-Sadri and N.D. Wetzler, Partial words and the critical factorization theorem revisited. Theoret. Comput. Sci.385 (2007) 179–192.  URIhttp://www.uncg.edu/mat/research/cft2/
  12. Y. Césari and M. Vincent, Une caractérisation des mots périodiques. C.R. Acad. Sci. Paris268 (1978) 1175–1177.  
  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.  
  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.  
  15. M. Crochemore and W. Rytter, Text Algorithms. Oxford University Press, New York, NY (1994).  
  16. M. Crochemore and W. Rytter, Jewels of Stringology. World Scientific, NJ (2003).  
  17. E. Czeizler, The non-parametrizability of the word equation xyz = zvw : A short proof. Theoret. Comput. Sci.345 (2005) 296–303.  
  18. N.J. Fine and H.S. Wilf, Uniqueness theorems for periodic functions. Proc. Amer. Math. Soc.16 (1965) 109–114.  
  19. L.J. Guibas and A.M. Odlyzko, Periods in strings. J. Comb. Theory A30 (1981) 19–42.  
  20. V. Halava, T. Harju and L. Ilie, Periods and binary words. J. Comb. Theory A89 (2000) 298–303.  
  21. T. Harju and D. Nowotka, The equation xi = yjzk in a free semigroup. Semigroup Forum68 (2004) 488–490.  
  22. J.I. Hmelevskii, Equations in free semigroups. Proceedings of the Steklov Institute of Mathematics107 (1971) 1–270 (American Mathematical Society, Providence, RI (1976)).  
  23. P. Leupold, Partial words: results and perspectives. GRLMC, Tarragona (2003).  
  24. M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, MA (1983). Cambridge University Press, Cambridge (1997).  
  25. M. Lothaire, Algebraic Combinatorics on Words. Cambridge University Press, Cambridge (2002).  
  26. M. Lothaire, Applied Combinatorics on Words. Cambridge University Press, Cambridge (2005).  
  27. R.C. Lyndon and M.P. Schützenberger, The equation am = bncp in a free group. Michigan Math. J.9 (1962) 289–298.  
  28. G.S. Makanin, The problem of solvability of equations in a free semigroup. Math. USSR Sbornik32 (1977) 129–198.  
  29. A.A. Markov, The theory of algorithms. Trudy Mat. Inst. Steklov42 (1954).  
  30. G. Păun, N. Santean, G. Thierrin and S. Yu, On the robustness of primitive words. Discrete Appl. Math.117 (2002) 239–252.  
  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.  
  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.  
  33. E. Rivals and S. Rahmann, Combinatorics of periods in strings. J. Comb. Theory A104 (2003) 95–113.  
  34. H.J. Shyr, Free Monoids and Languages. Hon Min Book Company, Taichung, Taiwan (1991).  
  35. H.J. Shyr and G. Thierrin, Disjunctive languages and codes. Lect. Notes Comput. Sci.56 (1977) 171–176.  

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.