Compatibility relations on codes and free monoids

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.

Détail

DOI : 10.1051/ita:2008016

Classification : 68R15
Keywords: compatibility relation, free monoid, stability, defect theorem, partial word