A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Relational codes of words
Tekijät: Halava V, Harju T, Karki T
Kustantaja: ELSEVIER SCIENCE BV
Julkaisuvuosi: 2007
Lehti: Theoretical Computer Science
Tietokannassa oleva lehden nimi: THEORETICAL COMPUTER SCIENCE
Lehden akronyymi: THEOR COMPUT SCI
Vuosikerta: 389
Numero: 1-2
Aloitussivu: 237
Lopetussivu: 249
Sivujen määrä: 13
ISSN: 0304-3975
DOI: https://doi.org/10.1016/j.tcs.2007.09.011
Tiivistelmä
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.
Avainsanat:
code, NP-completeness, partial word, relational code, Sardinas-Patterson algorithm
Turun yliopiston Tutkimustietojärjestelmän portaali