On special families of morphisms related to δ-matching and don't care symbols

摘要

The δ-matching problem is a special version of approximate pattern-matching, motivated by applications in musical information retrieval, where the alphabet Σ is an interval of integers. We investigate relations between δ-matching and pattern-matching with don't care symbol * (a symbol matching every symbol, including itself). We show that the δ-matching is reducible to k instances of pattern-matching with don't cares. We investigate how the numbers δ and k are related by introducing δ-distinguishing families H of morphisms. The size of H corresponds to k. We show that for minimal families H we have |H| = Θ(δ).