Equations on partial words

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

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

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009), p. 23-39 / Harvested from Numdam

Access to full text
Full (PDF)
Full (DJVU)

Résumé

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 \geq 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 \geq 2$ .

Publié le : 2009-01-01

MR 2483443 | Zbl 1170.68032 | 1 citation dans Numdam

DOI : https://doi.org/10.1051/ita:2007041
Classification: 68R15

@article{ITA_2009__43_1_23_0,
     author = {Blanchet-Sadri, Francine and Blair, D. Dakota and Lewis, Rebeca V.},
     title = {Equations on partial words},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {43},
     year = {2009},
     pages = {23-39},
     doi = {10.1051/ita:2007041},
     mrnumber = {2483443},
     zbl = {1170.68032},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2009__43_1_23_0}
}

Blanchet-Sadri, Francine; Blair, D. Dakota; Lewis, Rebeca V. Equations on partial words. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009) pp. 23-39. doi : 10.1051/ita:2007041. http://gdmltest.u-ga.fr/item/ITA_2009__43_1_23_0/

Bibliographie

[1] J. Berstel and L. Boasson, Partial words and a theorem of Fine and Wilf. Theoret. Comput. Sci. 218 (1999) 135-141. | MR 1687780 | Zbl 0916.68120

[2] F. Blanchet-Sadri, Periodicity on partial words. Comput. Math. Appl. 47 (2004) 71-82. | MR 2062726 | Zbl 1068.68110

[3] F. Blanchet-Sadri, Codes, orderings, and partial words. Theoret. Comput. Sci. 329 (2004) 177-202. | MR 2103647 | Zbl 1086.68108

[4] F. Blanchet-Sadri, Primitive partial words. Discrete Appl. Math. 48 (2005) 195-213. | MR 2147791 | Zbl 1101.68643

[5] F. Blanchet-Sadri and Arundhati R. Anavekar, Testing primitivity on partial words. Discrete Appl. Math. 155 (2007) 179-287. | MR 2303152 | Zbl 1108.68093

[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. | MR 2298175 | Zbl 1132.68513

[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/ | MR 2033749 | Zbl 1070.68061

[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/ | MR 2121025 | Zbl 1073.68067

[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. | MR 1871078 | Zbl 0988.68142

[10] F. Blanchet-Sadri and D.K. Luhmann, Conjugacy on partial words. Theoret. Comput. Sci. 289 (2002) 297-312. | MR 1932900 | Zbl 1061.68123

[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/ | MR 2356251 | Zbl 1124.68086

[12] Y. Césari and M. Vincent, Une caractérisation des mots périodiques. C.R. Acad. Sci. Paris 268 (1978) 1175-1177. | Zbl 0392.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. | MR 1469998

[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. | MR 530548 | Zbl 0412.20053

[15] M. Crochemore and W. Rytter, Text Algorithms. Oxford University Press, New York, NY (1994). | MR 1307378 | Zbl 0844.68101

[16] M. Crochemore and W. Rytter, Jewels of Stringology. World Scientific, NJ (2003). | MR 2012571 | Zbl 1078.68151

[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. | MR 2171615 | Zbl 1079.68081

[18] N.J. Fine and H.S. Wilf, Uniqueness theorems for periodic functions. Proc. Amer. Math. Soc. 16 (1965) 109-114. | MR 174934 | Zbl 0131.30203

[19] L.J. Guibas and A.M. Odlyzko, Periods in strings. J. Comb. Theory A 30 (1981) 19-42. | MR 607037 | Zbl 0464.68070

[20] V. Halava, T. Harju and L. Ilie, Periods and binary words. J. Comb. Theory A 89 (2000) 298-303. | MR 1741010 | Zbl 0943.68128

[21] T. Harju and D. Nowotka, The equation $x^{i} = y^{j} z^{k}$ in a free semigroup. Semigroup Forum 68 (2004) 488-490. | MR 2050904 | Zbl 1052.20044

[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)). | MR 393284 | Zbl 0326.02032

[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). | MR 1475463 | Zbl 0514.20045

[25] M. Lothaire, Algebraic Combinatorics on Words. Cambridge University Press, Cambridge (2002). | MR 1905123 | Zbl 1001.68093

[26] M. Lothaire, Applied Combinatorics on Words. Cambridge University Press, Cambridge (2005). | MR 2165687 | Zbl 1133.68067

[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. | MR 162838 | Zbl 0106.02204

[28] G.S. Makanin, The problem of solvability of equations in a free semigroup. Math. USSR Sbornik 32 (1977) 129-198. | MR 486227 | Zbl 0396.20037

[29] A.A. Markov, The theory of algorithms. Trudy Mat. Inst. Steklov 42 (1954). | MR 77473 | Zbl 0058.00501

[30] G. Păun, N. Santean, G. Thierrin and S. Yu, On the robustness of primitive words. Discrete Appl. Math. 117 (2002) 239-252. | MR 1881279 | Zbl 1004.68127

[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. | MR 1798096

[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. | MR 1917589

[33] E. Rivals and S. Rahmann, Combinatorics of periods in strings. J. Comb. Theory A 104 (2003) 95-113. | MR 2018422 | Zbl 1073.68706

[34] H.J. Shyr, Free Monoids and Languages. Hon Min Book Company, Taichung, Taiwan (1991). | MR 1090325 | Zbl 0746.20050

[35] H.J. Shyr and G. Thierrin, Disjunctive languages and codes. Lect. Notes Comput. Sci. 56 (1977) 171-176. | MR 478794 | Zbl 0366.68049