Marc Chemillier
Français / English
Grammars, automata and music

Marc Chemillier

September, 1999
Revised version October, 2011

This page presents musical examples in midi or audio format, illustrating several ways to use grammars and automata to generate music. Some of them are described in a general overview published in 2004 (in French) and other references are given below.

CHEMILLIER M., "Grammaires, automates et musique", J.-P. BRIOT & F. PACHET (eds.), Informatique musicale, Traité IC2, Paris, Hermès, 2004, 195-230.


  • Harmonic jazz substitutions defined by Steedman's grammar
  • Harmonic substitutions defined by Steedman's grammar studied in:

    STEEDMAN M.J.,"A Generative Grammar for Jazz Chord Sequences", Music Perception, 2, 1, 1984, 52-77.
    CHEMILLIER M., "Toward a formal study of jazz chord sequences generated by Steedman's grammar", G. ASSAYAG, V. CAFAGNA, M. CHEMILLIER (eds.), Formal Systems and Music, special issue of Soft Computing, 8, 9, 2004, 617-622.
    CHEMILLIER M., "L'improvisation musicale et l'ordinateur. Transcrire la musique à l'ère de l'image animée", Terrain, 53, « Voir la musique », 2009, 67-83.

    Examples of simple blues chord progressions elaborated by applying this grammar. Each file is a six choruses long blues in E Major, computed by applying four substitution rules to each chorus to produce the next one. The resulting chord progression is arranged for solo piano in the boogie-woogie style. The program which computed those examples is made of two parts:

  • a rule engine which applies Steedman's grammar production rules to the chord sequence,
  • a rational transduction, which arrange the chords by taking piano solo elements from a table, where they are stored in midi format. The chords are processed as two bars long blocks.

    More precisely, a "substitution" is a transformation which consists in replacing certain chords of the chord progression by other chords. The following three examples are represented as arrays, in a way familiar to jazz musicians. The first one is the basic chord progression of the blues. The second one is derived from the first one by applying a few substitutions:

    at the end of the first line, and
    at the beginning of the last line. The third one is the chord progression of Blues for Alice composed by Charlie Parker :

      C     C     C     C7  
      F     F     C     C  
      G     G7     C     C  

      C     C     C    Gm7 / C7 
      F     F     C     A7  
      Dm7     G7     C     C  

      C    Bm7 / E7   Am7 / D7   Gm7 / C7 
      F    Fm7 / Bb7   Em7   Ebm7 / Ab7 
      Dm7     G7     C     C  

    In the following audio files, the three preceeding chord progressions are arranged by using the Band-in-a-box software. The arrangement is computed in the "Blues even" style, for piano, bass and drums (with an organ part played manually) :


  • Pierre Barbaud's counterpoint : In Memoriam (1911-1990)
  • Français / English

    On November 7th, 2011, a meeting was organised by IRCAM and INRIA to celebrate Pierre Barbaud's birthday (October 10th, 1911 - Septembre 10th, 1990) :
    http://www.ircam.fr/colloques.html?event=1088
    http://www.inria.fr/centre/paris-rocquencourt/actualites/pierre-barbaud-centenaire

    An example of a three part counterpoint computed by Pierre Barbaud. This file is the midi translation of the file entitled LCONT1.B3I, which is an original file coded in the format of the synthesis machine called Biniou. We are greatly endebted to Frank Brown (Université du Mans, http://franck.brown.free.fr/Barbaud/) who gave us some copies of these original files. This sequence was played at a concert (March 14th, 1989) devoted to Barbaud. The automaton which computed the following example is partly described (in French) in:

    BARBAUD P., Vademecum de l'ingénieur en musique, Springer, 1993, chapter 5, 105-134.

    It is made of two parts:

  • a Markov chain, which generates three notes perfect chord sequences, using a chord transition table associated with probabilities,
  • a rational transduction, which add ornaments to the chords (passing tones and so on), taken from tables of predefined motives.

    Other examples of files obtained by a simulation of another program of Barbaud (chapters 3 and 4 of his book).

    In addition to the 2004 general overview mentionned on top of this Web page "Grammars, automata and music", the formal model introduced by Barbaud is described in the following papers, and here is a letter by Pierre Barbaud about the report published in 1987.

    CHEMILLIER M., "Monoïde libre et musique, 1ère partie", RAIRO Inf. Theo., 21, 3, 1987, 341-371 (pdf).
    CHEMILLIER M., "Solfège, commutation partielle et automates de contrepoint", Math. Inf. Scienc. hum., 110, 1990, 5-25 (pdf).

    There exist a "Pierre Barbaud association" devoted to his memory and a biography on Wikipedia (in French) about this composer who wrote the soundtrack of movies by Chris Marker (Dimanche à Pékin, 1957, Lettre de Sibérie, 1958), Alain Resnais (Hiroshima mon amour, 1959, L'année dernière à Marienbad, 1961), Agnès Varda, and promoted the concept of "algorithmic music":
    http://www.associationpierrebarbaud.fr/
    http://fr.wikipedia.org/wiki/Pierre_Barbaud


  • Two voices inventions by David Cope
  • Examples of fragments of two voice inventions in a style derived from Bach's, computed by a program by David Cope. The full code in Commun Lisp is published in:

    COPE D., Computer and Musical Style, AR-Editions, 1991, chapter 4, 89-140.

    The program is built in three parts:

  • a finite automaton, which generates melodic profiles as sequences of intervals,
  • a rational transduction, which fills this profiles by replacing every intervals by a melodic motive taken from Bach's works, with the condition that the distance between extremal notes is equal to the interval which is replaced by this motive,
  • a special module for the counterpoint treatment, which places the resulting melodic line in the upper voice, as well as in the lower voice, after being transposed an octave lower, and shifted one bar forward, and then replaces every bars in even position in the upper voice by quater notes one tenth higher from the notes of the other voice, and does the same with the bars in odd position of the lower voice (excepted the first one) one sixth lower from the notes of the other voice.


  • Dan Timis algorithm for synchronizing automata : In Memoriam (1954-2009)
  • Français / English

    Examples of three part counterpoint computed by applying an algorithm for synchronizing automata designed by Dan Timis (Bucharest, July 15, 1954 - Mountain View, February 3, 2009). Each automaton generates one part of the counterpoint. The formal model underlying this algorithm is described in the papers referenced below, including some rare unpublished manuscripts by Dan Timis:

    TIMIS D., "Une grammaire générative pour la musique", Mémoire de DEA Esthétique et sciences de l'art, Sorbonne Paris IV University, 1983 (pdf, 3.7 Mo, 22 pages).
    TIMIS D., "Théorie des codes et analyse musicale", Mémoire de DEA Esthétique et sciences de l'art, Sorbonne Paris IV University, 1983 (pdf, 5.1 Mo, 25 pages).
    CHEMILLIER M., "Monoïde libre et musique, 2ème partie", RAIRO Inf. Theo., 21, 4, 1987, 379-417 (pdf).
    CHEMILLIER M. & TIMIS D., "Toward a theory of formal musical languages", Proc. of the ICMC 88, Cologne, 1988, 175-183 (pdf).
    CHEMILLIER M., "Solfège, commutation partielle et automates de contrepoint", Math. Inf. Scienc. hum., 110, 1990, 5-25 (pdf).
    CHEMILLIER M., "Automata and music", Proc. of the ICMC 92, San-Jose, 1992, 370-371.
    CHEMILLIER M., "Synchronization of musical words", Theoretical Computer Science, 310, 2003, 35-60.

    A copy of the page of Dan Timis notebook (Spring 1986) where he set up for the first time the construction of the synchronization automaton, and a letter by Stephen Travis Pope about the ICMC 88 paper by Chemillier and Timis.

    The following audio files illustrating Dan Timis algorithm were computed in 1992 at Ircam in collaboration with Francisco Iovino, by means of the human voice synthesis software called Chant:

    A very nice article by Morel Koren for remembering our good friend Dan Timis:

    KOREN Morel, "In Memoriam of my friend Dan Timis (1954-2009)", Min-ad, 7, August 2009, published on-line:
    http://www.biu.ac.il/hu/mu/min-ad/8-9-II/Koren_on_Dan_Timis.pdf

    Other Web sites devoted to Dan's memory:
    http://www.museresearch.com/blog/2009/02/tribute-to-dan-timis/
    http://www.ultrasomething.com/photography/2009/02/for-dan/