• 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. TUCS Technical Reports 767, Turku Centre for Computer Science, 2006.

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.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tHaHaKa06a,
  title = {Relational Codes of Words},
  author = {Halava, Vesa and Harju, Tero and Kärki, Tomi},
  number = {767},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2006},
  keywords = {code, relational code, partial word, NP-completeness},
  ISBN = {952-12-1721-9},
}

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

Edit publication