Compatibility relations on codes and free monoids

Tomi Kärki

RAIRO - Theoretical Informatics and Applications (2008)

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

Abstract

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

How to cite

top

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

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.