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 -code and an -free monoid for arbitrary word relations and . Modified Sardinas-Patterson algorithm is presented for testing whether finite sets of words are -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 -free monoids. The -free hull of a set of words is introduced and we show how it can be computed. We prove a defect theorem for -free hulls. In addition, a defect theorem of partial words is proved as a corollary.
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/
[1] Partial words and a theorem of Fine and Wilf. Theoret. Comput. Sci. 218 (1999) 135-141. | MR | Zbl
and ,[2] Theory of Codes. Academic press, New York (1985). | MR | Zbl
and ,[3] Sur le théorème du défaut. J. Algebra 60 (1979) 169-180. | MR | Zbl
, , and ,[4] Codes, orderings, and partial words. Theoret. Comput. Sci. 329 (2004) 177-202. | MR | Zbl
,[5] Pcodes of partial words, manuscript. http://www.uncg.edu/mat/pcode (2005).
and ,[6] Jewels of Stringology. World Scientific Publishing (2002). | MR | Zbl
and ,[7] Elementary homomorphisms and a solution of the D0L sequence equivalence problem. Theoret. Comput. Sci. 7 (1978) 169-183. | MR | Zbl
and ,[8] Computer and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979). | MR | Zbl
and ,[9] Relational codes of words. Theoret. Comput. Sci. 389 (2007) 237-249. | MR | Zbl
, and ,[10] Defect theorems with compatibility relation. Semigroup Forum (to appear, available online). | MR | Zbl
, and ,[11] Many aspects of defect theorems. Theoret. Comput. Sci. 324 (2004) 35-54. | MR | Zbl
and ,[12] Partial words for DNA coding. Lect. Notes Comput. Sci. 3384 (2005) 224-234. | MR | Zbl
,[13] The decidability of the D0L prefix problem. Int. J. Comput. Math. 6 (1977) 127-142. | MR | Zbl
,[14] A necessary and sufficient condition for the unique decomposition of coded messages. IRE Internat. Conv. Rec. 8 (1953) 104-108.
and ,[15] Présentation et présentations simplifiables d'un monoïd simplifiable. Semigroup Forum 14 (1977) 295-329. | MR | Zbl
,[16] The intersection of free submonoids of free monoids is free. Semigroup Forum 4 (1972) 345-350. | MR | Zbl
,Cité par Sources :