TY - JOUR
T1 - On special families of morphisms related to δ-matching and don't care symbols
AU - Cole, Richard
AU - Iliopoulos, Costas
AU - Lecroq, Thierry
AU - Plandowski, Wojciech
AU - Rytter, Wojciech
N1 - Funding Information:
* Corresponding author. E-mail addresses: cole@cs.nyu.edu (R. Cole), csi@dcs.kcl.ac.uk (C. Iliopoulos), thierry.lecroq@univ-rouen.fr (T. Lecroq), wojtekpl@mimuw.edu.pl (W. Plandowski), w.rytter@mimuw.edu.pl (W. Rytter). 1 The work of this author was partially supported by NSF grants CCR 0105678 and CCR 9800085. 2 The work of this author was partially supported by a NATO grant PST.CLG.977017, by Royal Society, JISC, EPSRC and Wellcome foundation grants and a Marie Curie fellowship. 3 The work of this author was partially supported by a NATO grant PST.CLG.977017.
PY - 2003/3/16
Y1 - 2003/3/16
N2 - 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 ℋ of morphisms. The size of ℋ corresponds to k. We show that for minimal families ℋ we have |ℋ| = Θ(δ).
AB - 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 ℋ of morphisms. The size of ℋ corresponds to k. We show that for minimal families ℋ we have |ℋ| = Θ(δ).
KW - Combinatorial problems
KW - Don't care symbols
KW - Pattern-matching
KW - δ-matching
UR - http://www.scopus.com/inward/record.url?scp=0037448824&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0037448824&partnerID=8YFLogxK
U2 - 10.1016/S0020-0190(02)00430-1
DO - 10.1016/S0020-0190(02)00430-1
M3 - Article
AN - SCOPUS:0037448824
VL - 85
SP - 227
EP - 233
JO - Information Processing Letters
JF - Information Processing Letters
SN - 0020-0190
IS - 5
ER -