# 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

## Access Full Article

top## Abstract

top## How to cite

topBlanchet-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] J. Berstel and L. Boasson, Partial words and a theorem of Fine and Wilf. Theoret. Comput. Sci. 218 (1999) 135–141. Zbl0916.68120MR1687780
- [2] F. Blanchet-Sadri, Periodicity on partial words. Comput. Math. Appl. 47 (2004) 71–82. Zbl1068.68110MR2062726
- [3] F. Blanchet-Sadri, Codes, orderings, and partial words. Theoret. Comput. Sci. 329 (2004) 177–202. Zbl1086.68108MR2103647
- [4] F. Blanchet-Sadri, Primitive partial words. Discrete Appl. Math. 48 (2005) 195–213. Zbl1101.68643MR2147791
- [5] F. Blanchet-Sadri and Arundhati R. Anavekar, Testing primitivity on partial words. Discrete Appl. Math. 155 (2007) 179–287. Zbl1108.68093MR2303152
- [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] 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] 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] 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] F. Blanchet-Sadri and D.K. Luhmann, Conjugacy on partial words. Theoret. Comput. Sci. 289 (2002) 297–312. Zbl1061.68123MR1932900
- [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] 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] 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] 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] M. Crochemore and W. Rytter, Text Algorithms. Oxford University Press, New York, NY (1994). Zbl0844.68101MR1307378
- [16] M. Crochemore and W. Rytter, Jewels of Stringology. World Scientific, NJ (2003). Zbl1078.68151MR2012571
- [17] E. Czeizler, The non-parametrizability of the word equation $xyz=zvx$: A short proof. Theoret. Comput. Sci. 345 (2005) 296–303. Zbl1079.68081MR2171615
- [18] N.J. Fine and H.S. Wilf, Uniqueness theorems for periodic functions. Proc. Amer. Math. Soc. 16 (1965) 109–114. Zbl0131.30203MR174934
- [19] L.J. Guibas and A.M. Odlyzko, Periods in strings. J. Comb. Theory A 30 (1981) 19–42. Zbl0464.68070MR607037
- [20] V. Halava, T. Harju and L. Ilie, Periods and binary words. J. Comb. Theory A 89 (2000) 298–303. Zbl0943.68128MR1741010
- [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] 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] P. Leupold, Partial words: results and perspectives. GRLMC, Tarragona (2003). Zbl1040.68082
- [24] M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, MA (1983). Cambridge University Press, Cambridge (1997). Zbl0514.20045MR1475463
- [25] M. Lothaire, Algebraic Combinatorics on Words. Cambridge University Press, Cambridge (2002). Zbl1001.68093MR1905123
- [26] M. Lothaire, Applied Combinatorics on Words. Cambridge University Press, Cambridge (2005). Zbl1133.68067MR2165687
- [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] G.S. Makanin, The problem of solvability of equations in a free semigroup. Math. USSR Sbornik 32 (1977) 129–198. Zbl0396.20037MR486227
- [29] A.A. Markov, The theory of algorithms. Trudy Mat. Inst. Steklov 42 (1954). Zbl0058.00501MR77473
- [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] 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] 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] E. Rivals and S. Rahmann, Combinatorics of periods in strings. J. Comb. Theory A 104 (2003) 95–113. Zbl1073.68706MR2018422
- [34] H.J. Shyr, Free Monoids and Languages. Hon Min Book Company, Taichung, Taiwan (1991). Zbl0746.20050MR1090325
- [35] H.J. Shyr and G. Thierrin, Disjunctive languages and codes. Lect. Notes Comput. Sci. 56 (1977) 171–176. Zbl0366.68049MR478794

## Citations in EuDML Documents

top## NotesEmbed ?

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