Equations on partial words

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

doi:10.1051/ita:2007041

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

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009) no. 1, pp. 23-39.

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$ .

MR Zbl | 1 citation dans Numdam

DOI : 10.1051/ita:2007041

Classification : 68R15
Mots clés : equations on words, equations on partial words, commutativity, conjugacy, free monoid

@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},
     pages = {23--39},
     publisher = {EDP-Sciences},
     volume = {43},
     number = {1},
     year = {2009},
     doi = {10.1051/ita:2007041},
     mrnumber = {2483443},
     zbl = {1170.68032},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita:2007041/}
}

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
SP  - 23
EP  - 39
VL  - 43
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2007041/
DO  - 10.1051/ita:2007041
LA  - en
ID  - ITA_2009__43_1_23_0
ER  -

%0 Journal Article
%A Blanchet-Sadri, Francine
%A Blair, D. Dakota
%A Lewis, Rebeca V.
%T Equations on partial words
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2009
%P 23-39
%V 43
%N 1
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita:2007041/
%R 10.1051/ita:2007041
%G en
%F 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) no. 1, pp. 23-39. doi : 10.1051/ita:2007041. http://www.numdam.org/articles/10.1051/ita:2007041/

Bibliographie
Cité par

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

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

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

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

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

[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 | Zbl

[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 | Zbl

[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 | Zbl

[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 | Zbl

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

[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 | Zbl

[12] Y. Césari and M. Vincent, Une caractérisation des mots périodiques. C.R. Acad. Sci. Paris 268 (1978) 1175-1177. | Zbl

[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

[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 | Zbl

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

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

[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 | Zbl

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

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

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

[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 | Zbl

[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 | Zbl

[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 | Zbl

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

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

[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 | Zbl

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

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

[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 | Zbl

[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

[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

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

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

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

Cité par Sources :