A1 Refereed original research article in a scientific journal
Relational codes of words
Authors: Halava V, Harju T, Karki T
Publisher: ELSEVIER SCIENCE BV
Publication year: 2007
Journal: Theoretical Computer Science
Journal name in source: THEORETICAL COMPUTER SCIENCE
Journal acronym: THEOR COMPUT SCI
Volume: 389
Issue: 1-2
First page : 237
Last page: 249
Number of pages: 13
ISSN: 0304-3975
DOI: https://doi.org/10.1016/j.tcs.2007.09.011
Abstract
We consider words, i.e. strings over a finite alphabet together with a similarity relation induced by a compatibility relation on letters. This notion generalizes that of partial words. The theory of codes on combinatories on words is revisited by defining (R, S)-codes for arbitrary similarity 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. (c) 2007 Elsevier B.V. All rights reserved.
We consider words, i.e. strings over a finite alphabet together with a similarity relation induced by a compatibility relation on letters. This notion generalizes that of partial words. The theory of codes on combinatories on words is revisited by defining (R, S)-codes for arbitrary similarity 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. (c) 2007 Elsevier B.V. All rights reserved.
Keywords:
code, NP-completeness, partial word, relational code, Sardinas-Patterson algorithm
UTU Research Portal