Relational codes of words



: Halava V, Harju T, Karki T

Publisher: ELSEVIER SCIENCE BV

: 2007

 Theoretical Computer Science

: THEORETICAL COMPUTER SCIENCE

: THEOR COMPUT SCI

: 389

: 1-2

: 237

: 249

: 13

: 0304-3975

DOI: https://doi.org/10.1016/j.tcs.2007.09.011


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.


code, NP-completeness, partial word, relational code, Sardinas-Patterson algorithm



Last updated on 14/10/2025 09:58:41 AM