Relational codes of words

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 combinatorics on words is revisited by defining ( R , S ) -codes for arbitrary similarity r...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2007-12, Vol.389 (1), p.237-249
Main Authors: Halava, Vesa, Harju, Tero, Kärki, Tomi
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Code
Combinatorics
Combinatorics. Ordered structures
Computer science
control theory
systems
Data processing. List processing. Character string processing
Exact sciences and technology
Mathematics
Memory organisation. Data processing
Miscellaneous
NP-completeness
Partial word
Relational code
Sardinas–Patterson algorithm
Sciences and techniques of general use
Software
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 combinatorics 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.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2007.09.011