Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-24T14:55:12.729Z Has data issue: false hasContentIssue false
  • English
  • Français

Compatibility relations on codes and free monoids

Published online by Cambridge University Press:  03 June 2008

Tomi Kärki
Tomi Kärki*
Affiliation:
Department of Mathematics and Turku Centre for Computer Science, University of Turku, 20014 Turku, Finland; [email protected]
Get access

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.

Keywords

Compatibility relationfree monoidstabilitydefect theorempartial word.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 42 , Issue 3: JM'06 , July 2008 , pp. 539 - 552
Copyright
© EDP Sciences, 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

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