Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: Computing Evolutionary Chains in Musical Sequences. | Computing Evolutionary Chains in Musical Sequences Maxime Crochemore Institut Gaspard-Monge Universite de Marne-la-Vallee E-mail mac@ Costas S. Iliopoulos King s College London Dept. Computer Science csi@ Yoan J. Pinzon King s College London Dept. Computer Science pinzon@ Submitted March 23 2000 Accepted May 22 2000 Abstract Musical patterns that recur in approximate rather than identical form within the body of a musical work are considered to be of considerable importance in music analysis. Here we consider the evolutionary chain problem this is the problem of computing a chain of all motif recurrences each of which is a transformation of similar to the original motif but each of which may be progressively further from the original. Here we consider several variants of the evolutionary chain problem and we present efficient algorithms and implementations for solving them. Keywords String algorithms approximate string matching dynamic programming computer-assisted music analysis. 1 Introduction This paper is focused on string-matching problems which arise in computer-assisted music analysis and musical information retrieval. In a recent article 4 a number of stringmatching problems as they apply to musical situations were reviewed and in particular the problem of Evolution Detection was introduced and discussed. It was pointed out that no specific algorithms for this problem either in music or in string-matching in general exist in the literature. However it seems that musical patterns or motifs actually evolve in this manner in certain types of composition an actual case is shown by the successive thematic entries shown in the appended Music Example. A more recent example from Messiaen s piano work Vingt Regards sur L Enfant Jesus is given in 3 . A musical score can be viewed as a string at a very rudimentary level the alphabet denoted by E could simply be the set of notes in the chromatic or diatonic notation or Partially .
