Relational codes of words

AbstractWe 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