• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Compatibility Relations on Codes and Free Monoids

Tomi Kärki, Compatibility Relations on Codes and Free Monoids. In: Proceedings of the 11th Mons Days of Theoretical Computer Science, 237-243, 2006.

Abstract:

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 theorem 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.

BibTeX entry:

@INPROCEEDINGS{inpKarki06a,
  title = {Compatibility Relations on Codes and Free Monoids},
  booktitle = {Proceedings of the 11th Mons Days of Theoretical Computer Science},
  author = {Kärki, Tomi},
  pages = {237-243},
  year = {2006},
  keywords = {compatibility relation, partial word, code, defect theorem},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication