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

Relational Codes of Words

Vesa Halava, Tero Harju, Tomi Kärki, Relational Codes of Words. Theoret. Comput. Sci 389, 237-249, 2007.

Abstract:

We consider words, i.e., strings over a finite alphabet together
with a compatibility relation induced by a relation on letters. This
notion generalizes that of partial words. The theory of codes on
combinatorics on words is revisited by defining (R,S)-codes for
arbitrary relations R and S. We describe an algorithm to test
whether or not a finite set of words is an (R,S)-code. Coding
properties of finite sets of words are explored by finding maximal
and minimal relations with respect to relational codes.

BibTeX entry:

@ARTICLE{jHaHaKa07a,
  title = {Relational Codes of Words},
  author = {Halava, Vesa and Harju, Tero and Kärki, Tomi},
  journal = {Theoret. Comput. Sci},
  volume = {389},
  pages = {237-249},
  year = {2007},
  keywords = {code, relational code, partial word, NP-completeness, Sardinas–Patterson algorithm},
}

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

Edit publication