Equations on partial words

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.

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

[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 $xyz=zvx$: 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