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

Richard Cole; Costas Iliopoulos; Thierry Lecroq; Wojciech Plandowski; Wojciech Rytter

doi:10.1016/S0020-0190(02)00430-1

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

Richard Cole, Costas Iliopoulos, Thierry Lecroq, Wojciech Plandowski, Wojciech Rytter

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

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 |ℋ| = Θ(δ).

Original language	English (US)
Pages (from-to)	227-233
Number of pages	7
Journal	Information Processing Letters
Volume	85
Issue number	5
DOIs	https://doi.org/10.1016/S0020-0190(02)00430-1
State	Published - Mar 16 2003

Keywords

Combinatorial problems
Don't care symbols
Pattern-matching
δ-matching

ASJC Scopus subject areas

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Access to Document

10.1016/S0020-0190(02)00430-1

Fingerprint Dive into the research topics of 'On special families of morphisms related to δ-matching and don't care symbols'. Together they form a unique fingerprint.

Cite this

@article{ce36cb2161ee4e3d8ef0b95b1748a730,

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

abstract = "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 |ℋ| = Θ(δ).",

keywords = "Combinatorial problems, Don't care symbols, Pattern-matching, δ-matching",

author = "Richard Cole and Costas Iliopoulos and Thierry Lecroq and Wojciech Plandowski and Wojciech Rytter",

year = "2003",

month = mar,

day = "16",

doi = "10.1016/S0020-0190(02)00430-1",

language = "English (US)",

volume = "85",

pages = "227--233",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "5",

}

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

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 -