Two algorithms

Two algo­rithms for the instan­ti­a­tion of struc­tures of musi­cal objects

Bernard Bel

This is an extend­ed and revised ver­sion of the chap­ter: Symbolic and Sonic Representations of Sound-Object Structures pub­lished in M. Balaban, K. Ebcioglu & O. Laske (Eds.) “Understanding Music with AI: Perspectives on Music Cognition”, AAAI Press (1992, p. 64-109).

Abstract

A rep­re­sen­ta­tion­al mod­el of dis­crete struc­tures of musi­cal objects at the sym­bol­ic and sono­log­i­cal lev­els is intro­duced. This mod­el is being used to design com­put­er tools for rule-based musi­cal com­po­si­tion, where the low-level musi­cal objects are not notes, but “sound-objects”, i.e. arbi­trary sequences of mes­sages sent to a real-time dig­i­tal sound processor.

“Polymetric expres­sions” are string rep­re­sen­ta­tions of con­cur­rent process­es that can be eas­i­ly han­dled by for­mal gram­mars. These expres­sions may not con­tain all the infor­ma­tion need­ed to syn­chro­nise the whole struc­ture of sound-objects, i.e. to deter­mine their strict order in (sym­bol­ic) time. In response to this, the notion of “sym­bol­ic tem­po” is intro­duced: the order­ing of all objects in a struc­ture is pos­si­ble once their sym­bol­ic tem­pos are known. Rules for assign­ing sym­bol­ic tem­pos to objects are there­fore pro­posed. These form the basis of an algo­rithm for inter­pret­ing incom­plete poly­met­ric expres­sions. The rel­e­vant fea­tures of this inter­pre­ta­tion are commented.

An exam­ple is giv­en to illus­trate the advan­tage of using (incom­plete) poly­met­ric rep­re­sen­ta­tions instead of con­ven­tion­al music nota­tion or event tables when the com­plete descrip­tion of the musi­cal piece and/or its vari­ants requires dif­fi­cult cal­cu­la­tions of durations.

Given a strict order­ing of sound-objects, sum­marised in a "phase table" rep­re­sent­ing the com­plete poly­met­ric expres­sion, the next step is to com­pute the times at which mes­sages should be sent. This requires a descrip­tion of "sound-object pro­to­types" with their metric/topological prop­er­ties and var­i­ous para­me­ters relat­ed to musi­cal per­for­mance (e.g. "smooth" or "stri­at­ed" time, tem­po, etc.). These prop­er­ties are dis­cussed in detail, and a time-polynomial con­straint sat­is­fac­tion algo­rithm for the time-setting of sound objects in a poly­met­ric struc­ture is intro­duced. Typical exam­ples com­put­ed by this algo­rithm are shown and discussed.

Excerpts of an AI review of this paper (Academia, June 2025)

Summary of the Work

The man­u­script intro­duces a mod­el for rep­re­sent­ing and instan­ti­at­ing musi­cal struc­tures made of dis­crete sound-objects. It explores sep­a­rate rep­re­sen­ta­tions for sym­bol­ic and phys­i­cal time, then pro­pos­es meth­ods to syn­chro­nize con­cur­rent musi­cal process­es and to com­pute the pre­cise sched­ul­ing of mes­sages (or events) des­tined for a sound proces­sor. The author con­cep­tu­al­izes “smooth” and “stri­at­ed” time, describes “poly­met­ric expres­sions” as high-level objects that can be incom­plete, and pro­vides algo­rithms to infer miss­ing tim­ing details. The paper merges for­mal lan­guage approach­es, real-time con­sid­er­a­tions, and prac­ti­cal exam­ples of usage in a soft­ware envi­ron­ment called Bol Processor.

Comprehensive Model of Time

• The clear dis­tinc­tion between sym­bol­ic time (strict­ly ordered events) and phys­i­cal time (metro­nom­ic or arbi­trary “stri­at­ed” struc­tures) pro­vides an insight­ful way to han­dle simul­ta­ne­ous or over­lap­ping musi­cal events.
• The notion of “smooth” ver­sus “stri­at­ed” time is con­ju­gat­ed with help­ful exam­ples, mak­ing it straight­for­ward to envi­sion both con­texts of performance.

Polymetric Expressions and Incomplete Descriptions

• The approach to poly­met­ric expres­sions accom­mo­dates incom­plete rep­re­sen­ta­tions that can lat­er be resolved by an algo­rith­mic inter­pre­ta­tion. This is par­tic­u­lar­ly valu­able for com­posers and researchers look­ing to exper­i­ment with gen­er­a­tive or rule-based sys­tems with­out being forced into ful­ly spec­i­fied nota­tion from the outset.
• The exam­ples and dia­grams show­ing how one can map poly­met­ric struc­tures to a phase dia­gram illus­trate the con­cept effectively.

Synchronization and Constraints

• The pro­posed syn­chro­niza­tion algo­rithm han­dles con­cur­ren­cy by care­ful­ly prop­a­gat­ing sym­bol­ic tem­pos across sequences. This helps man­age cas­es where direct numer­ic dura­tions are not known beforehand.
• The intro­duc­tion of prop­er­ties such as piv­ot align­ment (PivBeg, PivCent, etc.), trun­ca­tion, elas­tic­i­ty, and relo­cata­bil­i­ty demon­strates thor­ough con­sid­er­a­tion of real­is­tic per­for­mance sce­nar­ios (e.g., ruba­to, par­tial overlaps).

Practical Implementation and Examples

• The paper gives a thor­ough demon­stra­tion of how these algo­rithms inte­grate with a func­tion­al soft­ware envi­ron­ment, includ­ing tan­gi­ble data struc­tures (phase tables, instance tables) and step-by-step flowcharts.
• Musical exam­ples and ref­er­ences to real-time com­put­er music sys­tems under­score the applic­a­bil­i­ty of the approach.

Rich Technical Detail

• The step­wise pseudo-code for the time-setting algo­rithm is exten­sive and trans­par­ent. This lev­el of detail can guide fur­ther exper­i­men­tal or production-level implementations.
• The com­plex­i­ty analy­sis (O(nmax² · imax³) in the worst case) pro­vides an under­stand­ing of poten­tial com­pu­ta­tion­al lim­its, help­ful for any­one plan­ning to use or extend these algorithms.

Potential Impact

• This work is use­ful to com­posers, researchers in algo­rith­mic com­po­si­tion, and devel­op­ers of music soft­ware who need robust syn­chro­niza­tion meth­ods that go beyond sim­ple “note-by-note” scheduling.
• The pro­posed meth­ods can enable more flex­i­ble rep­re­sen­ta­tions of time and con­cur­ren­cy, allow­ing for rich­er gen­er­a­tive or impro­vi­sa­tion­al projects.

Summary of Review

Overall, this paper pro­vides a detailed, for­mal­ized frame­work for resolv­ing con­cur­rent musi­cal struc­tures. It bridges the gap between abstract sym­bol­ic gram­mars and prac­ti­cal real-time per­for­mance con­sid­er­a­tions. Researchers and musi­cians inter­est­ed in algo­rith­mic com­pos­ing or advanced computer-assisted com­po­si­tion tools will like­ly find its approach com­pelling, espe­cial­ly giv­en the exten­sive exam­ples and robust pseudo-code.

Download this paper (PDF)