Compatibility relations on codes and free monoids
Kärki, Tomi
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008), p. 539-552 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

A compatibility relation on letters induces a reflexive and symmetric relation on words of equal length. We consider these word relations with respect to the theory of variable length codes and free monoids. We define an (R,S)-code and an (R,S)-free monoid for arbitrary word relations R and S. Modified Sardinas-Patterson algorithm is presented for testing whether finite sets of words are (R,S)-codes. Coding capabilities of relational codes are measured algorithmically by finding minimal and maximal relations. We generalize the stability criterion of Schützenberger and Tilson’s closure result for (R,S)-free monoids. The (R,S)-free hull of a set of words is introduced and we show how it can be computed. We prove a defect theorem for (R,S)-free hulls. In addition, a defect theorem of partial words is proved as a corollary.

Publié le : 2008-01-01
DOI : https://doi.org/10.1051/ita:2008016
Classification:  68R15 
@article{ITA_2008__42_3_539_0,
     author = {K\"arki, Tomi},
     title = {Compatibility relations on codes and free monoids},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {42},
     year = {2008},
     pages = {539-552},
     doi = {10.1051/ita:2008016},
     mrnumber = {2434034},
     zbl = {1149.68069},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2008__42_3_539_0}
}

Kärki, Tomi. Compatibility relations on codes and free monoids. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) pp. 539-552. doi : 10.1051/ita:2008016. http://gdmltest.u-ga.fr/item/ITA_2008__42_3_539_0/

[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] J. Berstel and D. Perrin, Theory of Codes. Academic press, New York (1985). | MR 797069 | Zbl 0587.68066

[3] J. Berstel, D. Perrin, J.F. Perrot and A. Restivo, Sur le théorème du défaut. J. Algebra 60 (1979) 169-180. | MR 549103 | Zbl 0421.20027

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

[5] F. Blanchet-Sadri and M. Moorefield, Pcodes of partial words, manuscript. http://www.uncg.edu/mat/pcode (2005).

[6] M. Crochemore and W. Rytter, Jewels of Stringology. World Scientific Publishing (2002). | MR 2012571 | Zbl 1078.68151

[7] A. Ehrenfeucht and G. Rozenberg, Elementary homomorphisms and a solution of the D0L sequence equivalence problem. Theoret. Comput. Sci. 7 (1978) 169-183. | MR 509015 | Zbl 0407.68085

[8] M.R. Garey and D.S. Johnson, Computer and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979). | MR 519066 | Zbl 0411.68039

[9] V. Halava, T. Harju and T. Kärki, Relational codes of words. Theoret. Comput. Sci. 389 (2007) 237-249. | MR 2363375 | Zbl 1143.68036

[10] V. Halava, T. Harju and T. Kärki, Defect theorems with compatibility relation. Semigroup Forum (to appear, available online). | MR 2367152 | Zbl 1146.20036

[11] T. Harju and J. Karhumäki, Many aspects of defect theorems. Theoret. Comput. Sci. 324 (2004) 35-54. | MR 2083927 | Zbl 1078.68083

[12] P. Leupold, Partial words for DNA coding. Lect. Notes Comput. Sci. 3384 (2005) 224-234. | MR 2179040 | Zbl 1116.68462

[13] M. Linna, The decidability of the D0L prefix problem. Int. J. Comput. Math. 6 (1977) 127-142. | MR 471462 | Zbl 0358.68114

[14] A.A. Sardinas and G.W. Patterson, A necessary and sufficient condition for the unique decomposition of coded messages. IRE Internat. Conv. Rec. 8 (1953) 104-108.

[15] J.C. Spehner, Présentation et présentations simplifiables d'un monoïd simplifiable. Semigroup Forum 14 (1977) 295-329. | MR 466363 | Zbl 0477.20037

[16] B. Tilson, The intersection of free submonoids of free monoids is free. Semigroup Forum 4 (1972) 345-350. | MR 311807 | Zbl 0261.20060