It is well-known that some of the most basic properties of words, like the commutativity () and the conjugacy (), 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 has only periodic solutions in a free monoid, that is, if holds with integers , then there exists a word such that are powers of . 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 , , and special cases of for integers .
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://archive.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://archive.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://archive.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://archive.numdam.org/articles/10.1051/ita:2007041/
[1] Partial words and a theorem of Fine and Wilf. Theoret. Comput. Sci. 218 (1999) 135-141. | MR | Zbl
and ,[2] Periodicity on partial words. Comput. Math. Appl. 47 (2004) 71-82. | MR | Zbl
,[3] Codes, orderings, and partial words. Theoret. Comput. Sci. 329 (2004) 177-202. | MR | Zbl
,[4] Primitive partial words. Discrete Appl. Math. 48 (2005) 195-213. | MR | Zbl
,[5] Testing primitivity on partial words. Discrete Appl. Math. 155 (2007) 179-287. | MR | Zbl
and ,[6] 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
, , and ,[7] Local periods and binary partial words: an algorithm. Theoret. Comput. Sci. 314 (2004) 189-216. http://www.uncg.edu/mat/AlgBin/ | MR | Zbl
and ,[8] Partial words and the critical factorization theorem. J. Comb. Theory A 109 (2005) 221-245. http://www.uncg.edu/mat/cft/ | MR | Zbl
and ,[9] Partial words and a theorem of Fine and Wilf revisited. Theoret. Comput. Sci. 270 (2002) 401-419. | MR | Zbl
and ,[10] Conjugacy on partial words. Theoret. Comput. Sci. 289 (2002) 297-312. | MR | Zbl
and ,[11] Partial words and the critical factorization theorem revisited. Theoret. Comput. Sci. 385 (2007) 179-192. http://www.uncg.edu/mat/research/cft2/ | MR | Zbl
and ,[12] Une caractérisation des mots périodiques. C.R. Acad. Sci. Paris 268 (1978) 1175-1177. | Zbl
and ,[13] 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
and ,[14] Another proof on a theorem of Lyndon and Schützenberger in a free monoid. Soochow J. Math. 4 (1978) 143-146. | MR | Zbl
and ,[15] Text Algorithms. Oxford University Press, New York, NY (1994). | MR | Zbl
and ,[16] Jewels of Stringology. World Scientific, NJ (2003). | MR | Zbl
and ,[17] The non-parametrizability of the word equation : A short proof. Theoret. Comput. Sci. 345 (2005) 296-303. | MR | Zbl
,[18] Uniqueness theorems for periodic functions. Proc. Amer. Math. Soc. 16 (1965) 109-114. | MR | Zbl
and ,[19] Periods in strings. J. Comb. Theory A 30 (1981) 19-42. | MR | Zbl
and ,[20] Periods and binary words. J. Comb. Theory A 89 (2000) 298-303. | MR | Zbl
, and ,[21] The equation in a free semigroup. Semigroup Forum 68 (2004) 488-490. | MR | Zbl
and ,[22] Equations in free semigroups. Proceedings of the Steklov Institute of Mathematics 107 (1971) 1-270 (American Mathematical Society, Providence, RI (1976)). | MR | Zbl
,[23] Partial words: results and perspectives. GRLMC, Tarragona (2003).
,[24] Combinatorics on Words. Addison-Wesley, Reading, MA (1983). Cambridge University Press, Cambridge (1997). | MR | Zbl
,[25] Algebraic Combinatorics on Words. Cambridge University Press, Cambridge (2002). | MR | Zbl
,[26] Applied Combinatorics on Words. Cambridge University Press, Cambridge (2005). | MR | Zbl
,[27] The equation in a free group. Michigan Math. J. 9 (1962) 289-298. | MR | Zbl
and ,[28] The problem of solvability of equations in a free semigroup. Math. USSR Sbornik 32 (1977) 129-198. | MR | Zbl
,[29] The theory of algorithms. Trudy Mat. Inst. Steklov 42 (1954). | MR | Zbl
,[30] On the robustness of primitive words. Discrete Appl. Math. 117 (2002) 239-252. | MR | Zbl
, , and ,[31] Satisfiability of word equations with constants is in NEXPTIME. Proceedings of the Annual ACM Symposium on Theory of Computing (1999) 721-725. | MR
,[32] 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] Combinatorics of periods in strings. J. Comb. Theory A 104 (2003) 95-113. | MR | Zbl
and ,[34] Free Monoids and Languages. Hon Min Book Company, Taichung, Taiwan (1991). | MR | Zbl
,[35] Disjunctive languages and codes. Lect. Notes Comput. Sci. 56 (1977) 171-176. | MR | Zbl
and ,Cité par Sources :