ON THE COMBINATORIAL COMPLEXITY OF FUZZY PATTERN-MATCHING IN MUSIC ANALYSIS

In music analysis it is a common requirement to search a musical score for occurrences of a particular musical motif and its variants. This tedious and time-consuming task can be carried out by computer, using one of several models to specify which variants are to be included in the search. The question arises: just how many variants must be explic itly considered? The answer has a profound effect on the computer time needed. In this paper, recurrence relations and closed form analytic expressions are derived for the run time complexity of two models of ' 'fuzzy pattern matching'' for use in music analysis; each model assume s the existence of an atomic exact pattern matching operation. The for mulae so obtained are evaluated and tabulated as a function of their i ndependent parameters. These results enable a priori estimates to be m ade of the relative run times of different music searches performed us ing either model. This is illustrated by applying the results to an ac tual musical example.