# Compatibility relations on codes and free monoids

RAIRO - Theoretical Informatics and Applications (2008)

- Volume: 42, Issue: 3, page 539-552
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topKärki, Tomi. "Compatibility relations on codes and free monoids." RAIRO - Theoretical Informatics and Applications 42.3 (2008): 539-552. <http://eudml.org/doc/250337>.

@article{Kärki2008,

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 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.
},

author = {Kärki, Tomi},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Compatibility relation; free monoid; stability; defect
theorem; partial word.; Sardinas-Patterson algorithm},

language = {eng},

month = {6},

number = {3},

pages = {539-552},

publisher = {EDP Sciences},

title = {Compatibility relations on codes and free monoids},

url = {http://eudml.org/doc/250337},

volume = {42},

year = {2008},

}

TY - JOUR

AU - Kärki, Tomi

TI - Compatibility relations on codes and free monoids

JO - RAIRO - Theoretical Informatics and Applications

DA - 2008/6//

PB - EDP Sciences

VL - 42

IS - 3

SP - 539

EP - 552

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

LA - eng

KW - Compatibility relation; free monoid; stability; defect
theorem; partial word.; Sardinas-Patterson algorithm

UR - http://eudml.org/doc/250337

ER -

## References

top- J. Berstel and L. Boasson, Partial words and a theorem of Fine and Wilf. Theoret. Comput. Sci.218 (1999) 135–141. Zbl0916.68120
- J. Berstel and D. Perrin, Theory of Codes. Academic press, New York (1985). Zbl0587.68066
- J. Berstel, D. Perrin, J.F. Perrot and A. Restivo, Sur le théorème du défaut. J. Algebra60 (1979) 169–180.
- F. Blanchet-Sadri, Codes, orderings, and partial words. Theoret. Comput. Sci.329 (2004) 177–202. Zbl1086.68108
- F. Blanchet-Sadri and M. Moorefield, Pcodes of partial words, manuscript. (2005). URIhttp://www.uncg.edu/mat/pcode
- M. Crochemore and W. Rytter, Jewels of Stringology. World Scientific Publishing (2002). Zbl1078.68151
- A. Ehrenfeucht and G. Rozenberg, Elementary homomorphisms and a solution of the D0L sequence equivalence problem. Theoret. Comput. Sci.7 (1978) 169–183. Zbl0407.68085
- M.R. Garey and D.S. Johnson, Computer and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979). Zbl0411.68039
- V. Halava, T. Harju and T. Kärki, Relational codes of words. Theoret. Comput. Sci.389 (2007) 237–249. Zbl1143.68036
- V. Halava, T. Harju and T. Kärki, Defect theorems with compatibility relation. Semigroup Forum (to appear, available online). Zbl1146.20036
- T. Harju and J. Karhumäki, Many aspects of defect theorems. Theoret. Comput. Sci.324 (2004) 35–54. Zbl1078.68083
- P. Leupold, Partial words for DNA coding. Lect. Notes Comput. Sci.3384 (2005) 224–234. Zbl1116.68462
- M. Linna, The decidability of the D0L prefix problem. Int. J. Comput. Math.6 (1977) 127–142. Zbl0358.68114
- 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.
- J.C. Spehner, Présentation et présentations simplifiables d'un monoïd simplifiable. Semigroup Forum14 (1977) 295–329. Zbl0477.20037
- B. Tilson, The intersection of free submonoids of free monoids is free. Semigroup Forum4 (1972) 345–350. Zbl0261.20060

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.