Compatibility relations on codes and free monoids

Kärki, Tomi

doi:10.1051/ita:2008016

Kärki, Tomi

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) no. 3, pp. 539-552.

Résumé

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.

MR Zbl

DOI : 10.1051/ita:2008016

Classification : 68R15
Mots clés : compatibility relation, free monoid, stability, defect theorem, partial word

@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},
     pages = {539--552},
     publisher = {EDP-Sciences},
     volume = {42},
     number = {3},
     year = {2008},
     doi = {10.1051/ita:2008016},
     mrnumber = {2434034},
     zbl = {1149.68069},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ita:2008016/}
}

TY  - JOUR
AU  - Kärki, Tomi
TI  - Compatibility relations on codes and free monoids
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2008
SP  - 539
EP  - 552
VL  - 42
IS  - 3
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ita:2008016/
DO  - 10.1051/ita:2008016
LA  - en
ID  - ITA_2008__42_3_539_0
ER  -

%0 Journal Article
%A Kärki, Tomi
%T Compatibility relations on codes and free monoids
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2008
%P 539-552
%V 42
%N 3
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ita:2008016/
%R 10.1051/ita:2008016
%G en
%F 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) no. 3, pp. 539-552. doi : 10.1051/ita:2008016. http://archive.numdam.org/articles/10.1051/ita:2008016/

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

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

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

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

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

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

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

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

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

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

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

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

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

Cité par Sources :