Mazzola, Guerino / Noll, Thomas / Lluis-Puebla, Emilio: Perspectives in Mathematical and Computational Music Theory

this sort of CSPs library, in section 2. From this consultation we could deduce some general rules about mixing CAC and CP (section 3), which led us to choose a local search algorithm for the resolution that we’ll describe more briefly in section 4.

2 Some musical CSPs

This section details the CSP modelling. We’ll always keep the CSP formalism, with variables ranging over domains, and constraints which specify some partial information on the variables. We identify three classes of CSPs : the first one are the mere compositionnal problems, i.e. they have been proposed by either composers, or OpenMusic users. Several of them have been used in compositionnal work. The second class gathers three problems dealing with musical analysis (modelized with Marc Chemillier).

2.1 CSPs in Computer Assisted Composition

2.1.1 Sorting chords

Given a set $X$ of $n$ chords, the goal is to order them so that the number of common notes between two successive chords is maximal. It can be seen as a manner to arrange a musical material initially at random. It is an optimization problem where the domain is the set of all permutations of the elements of $X$ , $X1...Xn$ . The constraint is $sum maximize 1\<i\<nCard(Xi /~\ Xi+1)$ .

This CSP is equivalent to the Travelling Salesman Problem (TSP), just take the chords as cities, and (a fixed, large number, minus) the number of common notes between two chords as the distances.

The goal is to find reasonably good solutions in a reasonable time. An algorithm based on a TSP Approximation Algorithm graph theory already exists in OM, which optimizes the global number of common notes. The trouble is that it shows local gaps : for a long sequence, the successive chords have many notes in common, then there are two chords with no shared notes. Musically, this is not satisfying even if the number of total common notes is high. With a CSP modelization, we can avoid this by putting an additional constraint, stating »at least one shared note between two successive chords«, plus the constraint on the number of common notes.

2.1.2 Asynchronous rhythms

This problem is given by the italian composer Mauro Lanza (who used the solutions in several works, Erba Nera Che Cresci, Segno nero Tu Vivi for voice and electronic, Aschenblume for ensemble, and Burger Time, for tuba and electronics). The goal is to construct rhythmical patterns played repetitively and asynchronously, see figure 1. Formally, we have $n$ voices, and a fixed time unit. Each voice plays repetitively a rhythmic pattern of fixed length $li$ , with $ni$ onsets, which can be represented as a set of integers ${Vi,j,j \< ni}$ , where $i$ is the voice number.