Equations on partial words
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 ($↑$). Among other equations, we solve $xy↑yx$, $xz↑zy$, and special cases of ${x}^{m}{y}^{n}↑{z}^{p}$ for integers $m,n,p\ge 2$.

DOI : https://doi.org/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},
zbl = {1170.68032},
mrnumber = {2483443},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ita:2007041/}
}
TY  - JOUR
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
DA  - 2009///
SP  - 23
EP  - 39
VL  - 43
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2007041/
UR  - https://zbmath.org/?q=an%3A1170.68032
UR  - https://www.ams.org/mathscinet-getitem?mr=2483443
UR  - https://doi.org/10.1051/ita:2007041
DO  - 10.1051/ita:2007041
LA  - en
ID  - ITA_2009__43_1_23_0
ER  -
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/

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

Cité par Sources :