no. 3
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

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.

DOI : 10.1051/ita:2008016
Classification : 68R15
Keywords: 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},
     year = {2008},
     publisher = {EDP Sciences},
     volume = {42},
     number = {3},
     doi = {10.1051/ita:2008016},
     mrnumber = {2434034},
     zbl = {1149.68069},
     language = {en},
     url = {https://www.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  - https://www.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 https://www.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

[1] J. Berstel and L. Boasson, Partial words and a theorem of Fine and Wilf. Theoret. Comput. Sci. 218 (1999) 135-141. | Zbl | MR

[2] J. Berstel and D. Perrin, Theory of Codes. Academic press, New York (1985). | Zbl | MR

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

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

[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). | Zbl | MR

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

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

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

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

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

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

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

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

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

Cité par Sources :