Dynamic programming for the analysis of serial behaviors

Studies of breakdowns in music performance can provide rich information about the planning activities required for music performance, as well as offer significant advantages over studies of skilled performance in other domains (Palmer & van de Sande, 1993). Yet despite the potential benefits, documented evidence of errors in music performance is scarce, primarily because of methodological limitations. One important practical problem that arises is how to find a correspondence between the actual performance and the score, or intended performance. When performances are long and complex, with potentially many errors, matching a performance to a musical score becomes a nontrivial task. This paper describes an algorithm for this task, developed in the context of a study of music production errors. The solution to the problem utilizes dynamic programming techniques and runs in polynomial time.