Page  00000164 Proving Musical Properties using a temporal Concurrent Constraint Calculus Camilo Rueda, Frank Valencia Universidad Javeriana-Cali and BRICS, University of Aarhus, Denmark email:crueda@, Abstract We show how the ntcc calculus, a model of temporal concurrent constraint programming with the capability of modeling asynchronous and non-deterministic timed behavior, can be used for modeling real musical processes. We use the nondeterminism facility of ntcc to build weaker representations of musical processes that greatly simplifies the formal expression and analysis of its properties. We argue that this modeling strategy provides a "runnable specification "for music problems that eases the task of formally reasoning about them. We show how the linear temporal logic associated with ntcc gives a very expressive setting for formally proving the existence of interesting musical properties of a process. We give examples of musical specifications in ntcc and use the linear temporal logic for proving properties of a real musical problem. 1 Introduction Constraint programming and constraint satisfaction procedures have found an important place in music applications. Various languages and tools using these notions have been defined ((Assayag, Rueda, Laurson, Agon, and Delerue 1999), (Pachet and Roy 1995), (Laurson 1996)). These tools extend general purpose programming languages with new interfaces and search engines which are deemed suitable to compute musical structures defined by some given set of rules. Recently, more flexible search engines based on soft constraints have been proposed to be able to handle overspecified musical problems ((Truchet, Agon, and Codognet 2001)). The tendency is thus to provide tools that can offer approximate solutions when exact solutions do not exist or are extremely diffi cult to find. Our work belongs to the constraint programming framework but our approach is entirely different. We envision computer supported music composition from a model of computation perspective. We thus look for a reduced set of simple objects and behavior that should be a minimal base to construct meaningful musical processes. The base concept we choose to bootstrap from is that of concurrent process. We regard music performance and composition as a complex task of defining and controlling interaction among concurrent activities. We thus borrow concepts and techniques from concurrent processes modeling to define suitable computational calculi and analyze their behavior in real musical settings. What we gain from this low level approach is twofold. One the one hand, we are able to ground the development of music composition tools on a very precise formal foundation and by this means proposing coherent higher level musical structures and operations. On the other hand, our model can give us clues for constructing formal proofs of interesting properties of a given musical process. In (Alvarez, Diaz, Quesada, Rueda, Tamura, Valencia, and Assayag 2001), PiCO, a concurrent processes calculus integrating constraints and objects is proposed. Musical applications are programmed in a visual language having this calculus as its underlying model. Since there is no explicit notion of time in PiCO some musical processes, in particular those involving real time activity, are difficult to express. Moreover, reasoning about musical processes behavior in PiCO can be difficult since there is no formal logic associated with it. In this paper we propose using a temporal non deterministic concurrent calculus (ntcc, see (Palamidessi and Valencia 2001)) as a formal base to model 164

Page  00000165 timed musical processes in such a way that interesting musical properties can be formally proved. The ntcc calculus inherits ideas from the tcc model (Saraswat, Jagadeesan, and Gupta 1994), a formalism for reactive concurrent constraint programrning. In tcc time is conceptually divided into discrete inztervals (or time-units). In a particular time interval, a deterministic ccp process receives a stimulus (i.e. a constraint) from the environment,, it executes with this stimulus as the initial store, and when it reaches its resting point, it responds to the environment with the resulting store. Also the resting point determines a residual process, which is then executed in the next time interval. The tcc model is inherently deterministic and synchronous. Indeed, patterns of temporal behavior such as "the system must output pitch C within the next t time units" or "the three voices must output the same note but there is no bound in the occurrence time" cannot be expressed within the model. It also rules out the possibility of choosing one among several alternatives as an output to the environment. A very important benefit of allowing the specification of non-deterministic and asynchronous behavior arises when modeling the interaction among several components running in parallel, in which one component is part of the environment of the others. This is frequent in musical applications. These systems often need non-determinism and asynchrony to be modeled faithfully. The ntcc calculus is obtained from tcc by adding guarded-choice for modeling non-determinism and an unbounded but finite delay operator for asynchrony. Computation in ntcc progresses as in tcc, except for the non-determinism and asynchrony induced by the new constructs. The calculus allows for the specification of temporal properties, and for modeling and expressing constraints upon the environment both of which are useful in proving properties of timed systems. In (Rueda and Valencia 2001) we took advantage of the expressiveness of ntcc to program a music improvisation process. In this paper we are interested in the possibility of formally proving the properties of a musical process. We are able to do this thanks to the logical nature of ntcc, which comes to the surface when we consider its relation with linear temporal logic: All the operators of ntcc correspond to temporal logic constructs. In constraint based musical applications, the existence or non existence of a musical structure enjoying given properties is discovered after a time consuming search. The main contribution of this paper is to show that by modeling a music process in ntcc one inherits a well defined logical inference system (see (Palamidessi and Valencia 2001)) that can be used to prove its musical properties (or lack thereof). We apply this approach to a real musical problem taken from (Chemillier 1995). 2 The Calculus In this section we present the syntax and an operational semantics of the ntcc calculus. First we recall the notion of constraint system. Basically, a constraint system provides a signature from which syntactically denotable objects in the language called constraints can be constructed, and an entailment relation specifying interdependencies between such constraints. The underlying language LC of the constraint system contains the symbols -1, A,. ~, ~, true and false which denote logical negation, conj unction, implication, existential quantification, and the always true and always false predicates, respectively. Constraints, denoted by c, d,... are first-order formulae over 12. We say that c entails d in a, written c: F- d (or just c H d when no confusion arises), if c ~- d is true in all models of A. For operational reasons we shall require F- to be decidable. Process Syntax. Processes P, Q,... E Pr~oc are built from constraints c E C and variables x E V/ in the underlying constraint system by the following syntax. FQ:= tell(c) Z when cido P, SP I Q localxzin P Snext PI unless c next P I!P *;P The only move or action of process tell(c) is to add the constraint c to the current store, thus making c available to other processes in the current time interval. The guarded-choice Z when c, do P?' iCI where I is a finite set of indexes, represents a process that, in the current time interval, must 165

Page  00000166 non-deterministically choose one of the Pj (j C I) whose corresponding constraint cj is entailed by the store. The chosen alternative, if any, precludes the others. If no choice is possible then the summation is precluded. We use Zici Pi as an abbreviation for the "blind-choice" process CiI when (true) do P. We use skip as an abbreviation of the empty summation and "+" for binary summations. Process P I| Q represents the parallel composition of P and Q. In one time unit (or interval) P and Q operate concurrently, "communicating" via the common store. We use Hie, Pi, where I is finite, to denote the parallel composition of all Pi. Process local x in P behaves like P, except that all the information on x produced by P can only be seen by P and the information on x produced by other processes cannot be seen by P. The process next P represents the activation of P in the next time interval. Hence, a move of next P is a unit-delay of P. The process unless c next P is similar, but P will be activated only if c cannot be inferred from the current store. The "unless" processes add (weak) time-outs to the calculus, i.e., they wait one time unit for a piece of information c to be present and if it is not, they trigger activity in the next time interval. We use nextn(P) as an abbreviation for next(next(... (next P)... )) where next is repeated n times. The operator! is a delayed version of the replication operator for the 7r-calculus ((Milner 1999)):! P represents P II next P II next2p II..., i.e. unbounded many copies of P but one at a time. The replication operator is the only way of defining infinite behavior through the time intervals. The operator * allows us to express asynchronous behavior through the time intervals. The process * P represents an arbitrary long but finite delay for the activation of P. For example, * tell(c) can be viewed as a message c that is eventually delivered but there is no upper bound on the delivery time. We shall use! P and I P, where I is an interval of the natural numbers, as an abbreviation for,iCI next2P and i,1 next1P, respectively. For instance, *[,,,,]P means that P is eventually active between the next m and m + n time units, while![~,,,]P means that P is always active between the next m and rn + n time units. 2.0.1 Operational Semantics. Operationally, the current information is represented as a constraint c E C, so-called store. The operational semantics is given by considering transitions between configurations y of the form (P, c). We define I as the set of all configurations. The formal definition (see (Palamidessi and Valencia 2001) for details) introduces two reduction relations, one representing internal transitions and the other observable transitions. The internal transition (P, c) -- (Q, d) should be read as "P with store c reduces, in one internal step, to Q with store d ". The observable transition P ( d)Q should be read as "P on input c from the environment reduces, in one time unit, to Q and outputs d to the environment ". Such an observable transition is defined in terms of a sequence of internal transitionstransitions (P, c) --+* (Q', d) starting in P with store c and ending in some process Q' with store d. Crudely speaking, to obtain Q we should remove from Q' what was meant to be executed only in the current time interval. Since Q is to be executed in the next time interval we should also "unfold" the sub-terms within next R expressions in Q'. As in tcc, the store does not transfer automatically from one interval to another. To illustrate reductions in ntcc, consider a musical process, say! P, that continually outputs either C (MIDI=60) or E (MIDI=64) until another process (the conductor) Q signals the end. Process!P 11 Q, for P and Q as defined below, models the example. def P def when (Go =- 1) do (tell (Note = 60) + tell (Note = 64) ) 1l unless End = I next tell (Go = 1) def Q - tell(Go = 1) I tell(End = 1) Then there is a sequence of internal transitions (! P, Go = 1) - (P II next! P, Go = 1) --* (tell (Note = 65) || next! P, Go = 1) - (next! P, Note = 65 A Go 1) t-... Initially the store contains constraint Go = 1 (which, as described below, will be added to thestore by Q). Replicated process!P then creates a 166

Page  00000167 copy of P and schedules itself for the next time unit. Process P chooses note E (the store gets Go = 1 A Note = 65 ). No further reductions are possible in the current time unit. Two processes,!P and tell Go = 1 are scheduled for the next time unit. So, in the case P Q, for an arbitrary (number of time units) n > 1, the following are possible transitions: (!P || Q, true) * (next!P | next tell Go = 1 || next'tell(End = 1), Go = 1 A Note = 64) and (true, Go=1A Note=64)!P Q!P || tell Go = 1 || nextn- tell(End = 1). The first one is the internal transition relation, whereas the second is the observable transition. Thus!P continually outputs either pitch C or E for an arbitrary number n of time units until the constraint End = 1 is put in the store. As mentioned before, an important feature of the ntcc model is that there is a logic associated with it. We describe next this logic. 3 A Logic of ntcc Processes A relatively complete formal system for proving whether or not an ntcc process satisfies a lineartemporal property was introduced in (Palamidessi and Valencia 2001). In this section we summarize these results. 3.0.2 Temporal Logic. We define a linear temporal logic for expressing properties of ntcc processes. The formulae A, B,... C A are defined by the grammar A::= c A = A I -A I|,A OA I A I A. The symbol c denotes an arbitrary constraint. The symbols =, - and El represent temporal logic implication, negation and existential quantification. These symbols are not to be confused with the logic symbols -6, and E3 of the constraint system. The symbols O, W, and > denote the temporal operators next, always and sometime. Given a property A (e.g. x > 10) the intended meaning of OA, OA and <>A is that the property holds, in the next time unit, always and eventually, respectively. We use A V B as an abbreviation of -7A > B and A A B as an abbreviation of -i(-=A V -iB). We shall say that process P satisfies A iff every infinite sequence that P can possibly output satisfies the property expressed by A. A relatively complete proof system for assertions P F- A, whose intended meaning is that P satisfies A, can be found in (Palamidessi and Valencia 2001). We shall write P F- A if there is a derivation of P - A in this system. The following notion will be useful for discussing properties of our musical examples. Definition 1 (Strongest Derivable Formulae) A formula A is the strongest temporalformula derivable for P if P F- A and for all A' such that P F- A', we have A => A'. Note that the strongest temporal formula of a process P is unique modulo logical equivalence. We give now a constructive definition of such formula. Definition 2 (Strongest Formula Function) Let the function stf: Proc -+ A be defined as follows: stf (tell(c)) stf ( WHEN(ca, Pi)) stf(P | Q) stf (local x P) stf (next P) stf (unless c next P) stf(!P) stf(*P) - c = (V c A stf(Pi)) = stf(P) A stf(Q) = Il stf (P) = stf(P) S cv Ostf(P) = stf(P) - >stf(P). where the expression WHEN(ci, Pi)) represents process,ej when (ci) do Pi. From (Palamidessi and Valencia 2001) it follows that P F- stf(P). From this we have: Proposition 1 For every process P, stf(P) is the strongest temporal formula derivable for P. Note that to prove that P F- A is sufficient to prove that stf(P) => A. In addition, the proof system described in (Palamidessi and Valencia 2001) gives extra mechanisms for carrying out proofs of process properties. 167

Page  00000168 4 Musical examples We introduce a broad idea for modeling music process in ntcc by means of a well known problem: Constructing a chromatic series containing all notes and all intervals. For simplicity we assume that notes are numbered 1..12 and likewise for intervals, 0..11, expressed in half tones. We define 12 ntcc processes each taking care of choosing one note (among those still available considering previous choices) and then informing the others about its choice. A note is chosen so that intervals are not repeated. It will be convinient to specify our processes by using (possibly recursive) definitions. In ntcc it is possible to encode recursive definitions of def the form A PA, where A is the process name and PA. The intended behavior of a call A is that of PA. A precise encoding of recursion in ntcc is given in (Palamidessi and Valencia 2001). In what follows we rely on the usual intuitions concerning procedure calls in a programming language. CHOOSEm de (unless Tokern = rr next (CHOOSEme ) Swhen Token = me do >j when (Pre =- j )do,i unless ( NchoicNl i VIchoice $ int(j, i) ) next (! tell (Nchoice i) |! tell (Ichoice int(j, i)) | tell( Token = me + 1) | tell( Prey = i) S!tell( Note,,e = i) ) def SERIES df (tell (Token = 1) tell (Pre =- 1) || CHOOSE1 |... | CHOOSE12 In process CHOOSEi summations range over note values. Each process CHOOSEi nondeterministically selects a certain note value unless it has already been chosen or the interval formed with the previous note has already appeared. Variable Prey represents the value taken by the previous note in the sequence. Summation over j serves to find what that specific value was so as to use it for testing the constraint over the intervals. Function int(j, i) computes the interval between notes i and j. Once a note successfully selected, the process states this fact forever and propagates forward new constraints to forbid further choices of this note (tell Nchoice / i ) and also of the corresponding interval (tell Ichoice / int(j, i)). A token is passed so that all note processes are run sequentially. The fact that this problem has a solution can be stated as follows: FSERIESr H 012 V( Note12 - i). i That is, eventually the twelve note in the twelve time unit has a concrete value. Since this can only happens when all the other notes have a concrete value, a solution is implied (we use OP as a shorthand for p nested occurrences of operator 0. See below). One may also wonder whether solutions having certain interval patterns do exist. For instance, the logic could be used to prove that there are solutions with a third followed by a fifth in the middle of the series: rSERIES- H o 012 (V(Note12 = i) A(|Note6 - Notse5 = 3) A(INote7 - Note6I = 7)) 4.1 modeling a harmonic problem We model next a musical process described in (Chemillier 1995). It deals with harp music from Nzakara people of Central African republic. Two voices are constructed in such a way that the second one reproduces the first (up to transposition) with a time gap of p. The upper and lower voices play notes in the sets {64,67, 70} and {60, 62, 64}, respectively. A transposition function f(64) = 60, f(67) = 62, f(70) = 64 gives for each upper voice note the lower note that is to be played p time units later. Additional constraints state that time units that are either contiguous or separated by p units should not play the same chord. Finally, all chords thus formed must belong to the set {(60, 64), (60, 67), (62, 67), (62, 70), (64, 70)}. The four ntcc processes shown below model this problem. 168

Page  00000169 NOTES~midi:,p) ~ Cv (when err~ors2 v do unless chord(PNu, PNLi CNL. BNL, midi) next (tell errors2 v +t 1) I (when chord(PNu, PNL, CNL, BNL. midi) do (tell (C~in rnidi) IInext (tell PNur midi) IInext" (tell CN~L f(midi) IItell B~VU midi IInext (tell PNL f(midi)) IInext2P (tell BNL f(miL1di)) IInext (tell errors2 v 2))) CHOOSE(S) de NOTES(64,p) + NOTES(67,p)) + NOTES(7o,p) COUNVTERde CZl (when erro~sl 1 v do (when wrong71(CNL, C7Nu) do next (tell error~s v 1 - ) II (unless w~rong(CNL, CNu~) next (tell errorsl= v) silence). It also initializes the number of errors and launches the other process for all time units from zero to the number of notes. 4.2 proving properties of the Nzakara process The model given above is weaker than required for the Nzakara musical problem. Instead of asserting chord membership constraints, errors are simply counted. Giving weaker nice models allows proving negative properties of the real problem, such as the fact that there is no solution. We give first the strongest temporal formula for the process: stf(PROCESS(~,,)) (Dpi CNL 0 A r BNu- 0) A(Z, PNL 0 ) A (D~,p.lBNIL 0) Aerrorsl - 0 A errors2 0 A (Z1,_istf(CHOOSE,) A~stf (COUNTER)) where strongest temporal formulae for processes CHOOSER and COUNITER are PROCESS(~,, -![O,pl1] (tell CNL 0 A BNui O )A PNiL IItell errorsl 1 - 0 tell errors2 - 0 IInextP (tell PNL 0) II![O,2p-1] (tell BNL 0)./ [O,n-1] (CHOOSE~,s ) COUNTER) Variables PNx, CNx and BNx represent the previous note, the current note and the back note played p time units before, respectively. Index X is either U (upper voice) or L (lower voice). Process CHOOSE(,) models the nondeterministic selection of a note in the upper voice. Procss OTESmid~p)verifies the chord constraints (except membership to the given set) and then outputs the current upper note (CNn;). It also sends its current upper and lower notes as previous and back notes for the future. When the chord constraint does not hold, variable errors2 is incremented in the next time unit. Process COUNTER counts the number of output chords not belonging to the given set. Summation index v1 ranges from 0 to ri (the number of notes). Finally, PROCESS(rip) states that there cannot be lower, previous or back notes before the time gap of p, so these are set to zero (meaning a stf (COUNTER)(VU erro'rsl v 1 A (-lwrong A O(errorsl V(w~romg A O(errorsl v + 1))) 'v)),> stf(CHOOSE(,)) (ViE {64,67,70} stff(NOTES, p,))) VEo.T}er'rors2= w A(chordmidi V O(er'rors2 w + 1)) Aehordmidi A CNu; A O(PNu mir~dit) AOP(CNL f(rni~di) A BNU midi,) Ao~-t1(PNL, - f(rnidi)) AO(BNL f(rnidi)) A O(errors2 w l)) In the above definitions we write Ok"A for kc nested occurrences of 0 in 0(0(...(oA))...). Similarly, we write DkA for A A oA A 0(oA) A\...A OkA. We can use the strongest formula of PR~OCESS for proving various musical properties. It is straightforward to prove from.stf (NOTES) that the value of er'rors2 never decreases and also that a chord constraint violation implies a non zero vale of errors2 in subsequent time units. That is, L1(stf(NOTES~,,p)) A errors2 #j 0 (errors7'2 > w)) uii 169

Page  00000170 stf(NOTES(,,p)) A errors2 = w A -chord The expressive power of linear time logic and the S0 (errors2 > w) weaker implementation of the Nzakara process in Similarly, from the strongest formula of COUNTER ntcc allow us to infer many other interesting mui:,1..... 4-: I '.Iv.,1 -.. { "l,'l;:. i \\ we can prove that errorsl never decreases and that a single violation of the chord set membership constraint causes a non zero value of errors1 there on. The proof of the non solvability of the Nkazara process can be carried out by showing that each possible chord in the given set leads to a chord constraint violation: Proposition 2 Each chord in the given set violates a chord constraint. For all k E O..n - p we have: stf (PROCESS(n,p)) OP+k(CNL = 60 A CN = 64 Aerrorsl =0 z> errors2 > 0) st.f(PROCESS(,,Tp) = O02p+k(CNL = 60 A CNu = 67 Aerrorsl = 0: errors2 > 0) st f(PROCESS(,,,p)) FO3P+k(CNL = 62 A CNu = 67 Aerrorsl = 0 =: errors2 > 0) stf (PROCESS(,~,)) ) 0o3pk 1 ( (((CNL - 62 A CNu = 70) V(CNL = 64 A CNu = 70)) Aerrorsl = 0) = errors2 > 0) Since there are no options for chords other than those ruled out by the previous proposition, we have Corollary 1 There is always a chord constraint violation after three periods (Nzakara time gaps), i.e., st f (PROCESS(,p))) D03P+ +(errors -= 0 = errors2 > 0) from which it is easy to show Corollary 2 There is no solution for the Nzakara musical process having 30 notes and a time gap of 6, i.e., stf (PROCESS(3o,)) ) 0030( errorsl > 0 V errors2 > 0) sIcal properties, suchn as ( see (CLhemiicr 199yj)) Proposition 3 There is a Nzakara musical process having 30 notes and a time gap of 6 with fewer than 7 wrong chords, i.e., st f(PROCESS(30,6)) O030( errors2 = 0 A errorsl < 7) 5 Related and Future Work We have described an ongoing project concerning modeling musical processes with ntcc. The main advantages of this approach is that construction and manipulation of musical structures rests on the firm ground of a precise, simple, yet powerful "time aware" computational model. This allows us to better understand interactions among concurrent musical processes and thus having better clues for the development of coherent music composition tools, particularly for real time settings. It is of course true that complex musical processes, particularly those involving several musical dimensions, could be extremely difficult to model in such a "low level" mechanism. Our aim is not promote ntcc as a computer music language, but as a sort of "runnable specification" formalism of a variety of musical processes. A strong point of the described approach is that the linear temporal logic associated with ntcc can be used to prove (or disprove) interesting musical properties of processes before running them. We showed how this can be achieved for non trivial musical problems. The expressiveness of the logic allows us to state interesting musical properties in a very compact way. Moreover recent results show that a significant fragment of ntcc, which include all the applications examples in this paper, can be compiled into finite state systems. Finite state systems are amenable to automatic verification (of a program satisfying a temporal logic formula), since their observable behavior can be finitely represented. We plan to pursue this line of work in three directions: first, modeling in ntcc and proving properties of a variety of rhythm processes, in particular those aiming at constructing material obeying well defined patterns, such as described in (Laurson and Kuuskankare 2001) or the metric modulations in (Nicolas 1990). Initial work in this area 170

Page  00000171 has given us encouraging results. Second, extending ntcc to a probabilistic model following ideas in (Herescu and Palamidessi 2000). This is justified by the existence of rhythm patterns examples involving stochastic rules which cannot be faithfully modeled with non-deterministic behavior. Third, we have begun the implementation of an abstract machine for ntcc and plan to construct a music composition language on top of it. References Alvarez, G., J. Diaz, L. Quesada, C. Rueda, G. Tamura, F. Valencia, and G. Assayag (2001, January). Integrating constraints and concurrent objects in musical applications: A calculus and its visual language. Constraints. Assayag, G., C. Rueda, M. Laurson, C. Agon, and 0. Delerue (1999). Computer-assisted composition at ircam: From patchwork to openmusic. Computer music journal 23(3), 59-72. Chemillier, M. (1995). Une esthetique perdue. In E. de Dampierre (Ed.), La musique de la harpe, Paris, pp. 99-208. Presses de I'Ecole normale Superieur. Herescu, 0. and C. Palamidessi (2000). Probabilistic asynchronous pi-calculus. FoSSaCS, 146 -160. Laurson, M. (1996). Pwconstraints reference manual. Available through IRCAM user's group. Laurson, M. and M. Kuuskankare (2001). A constraint based approach to musical textures and instrumental writing. In Proceedings of Workshop on musical constraints, CP2001, Paphos, Cyprus, pp. 44-51. Milner, R. (1999). Communicating and Mobile Systems: the 7r-calculus. Cambridge University Press. Nicolas, F. (1990). Le feuillete du temps, essaie sur les modulations metriques. Entretemps (9). Pachet, F. and P. Roy (1995). Mixing constraints and objects: A case study in automatic harmonization. In Proceedings of TOOLS Europe'95, Versailles, France, pp. 119-126. Prentice-Hall. Palamidessi, C. and F. Valencia (2001, 26 November). A temporal concurrent constraint programming calculus. In Proc. of the Seventh International Conference on Principles and Practice of Constraint Programming. Rueda, C. and E Valencia (2001). Formalyzing timed musical processes with a temporal concurrent constraint calculus. In Proceedings of Workshop on musical constraints, CP2001, Paphos, Cyprus, pp. 44-51. Saraswat, V., R. Jagadeesan, and V. Gupta (1994, 4-7 July). Foundations of timed concurrent constraint programming. In Proc. of the Ninth Annual IEEE Symposium on Logic in Computer Science, pp. 71-80. Truchet, C., C. Agon, and P. Codognet (2001). A constraint programming system for music composition, preliminary results. In Proceedings of Workshop on musical constraints, CP2001, Paphos, Cyprus, pp. 34-43. 171