SEARCHING FOR FLEXIBLE REPEATED PATTERNS USING A NON-TRANSITIVE SIMILARITY RELATION

Given a reflexive and symmetric, but not necessarily transitive, simil arity relation defined on an alphabet of symbols, two objects of size k are related if, at each position, their symbols are related. Then, g iven a set of objects, we are interested in maximal subsets of related objects. We give some general properties of these subsets and we prop ose algorithms for identifying them in the particular case of k-length substrings in a string. These algorithms derive from the Karp, Miller and Rosenberg algorithms for the identification of repeated patterns.