Compatibility relations on codes and free monoids
Tomi Kärki (2008)
RAIRO - Theoretical Informatics and Applications
Similarity:
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....