Florent Jacquemard

Rewriting and music Florent Jacquemard (INRIA and IRCAM)

The slides of the lecture will be available here.

Computer Music is a vast domain that studies different music problems, with methods from several scientific disciplines and with various music representations. In this lecture, we will see some applications to written music processing of symbolic computation models such as string and term rewriting, as well as weighted automata. The first example will be the application to computational musicology, more precisely to the formal analysis of music, of the computation of similarity between melodies, defined by edit-distances. It is expressed as a combinatorial optimisation problem for weighted string rewriting systems. Second, we shall consider the application of term rewriting and weighted tree automata techniques to the problem of rhythm transcription.

Outline of the lecture

Introduction to Computer Music.

In this short introduction, we will see various representation models, problems, and tools in Computer Music, in particular examples from physical models, sound analysis and synthesis, Music Information Retrieval, environments for assistance to composition and to musicology.

Part I : Weighted String Rewriting Systems and Edit-Distances.

In this first part, we consider string representations of written music, and the problem of measuring the similarity of melodies, applied to the automation of music formal analysis. Standard similarity measures (string edit-distances) used in text and bio-informatics must be adapted for an usage in music analysis and extensions have been proposed (following earlier applications to speech processing) which are based on weighted string rewrite systems. We will consider the problem of the computation of optimal rewrite sequences for such system, and present related decidability results.

• motivation : string similarity algorithms in computational musicology and formal analysis [1].
• Levenshtein edit-distance, computation by dynamic programming.
• Montgeau and Sankoff extensions for music analysis [9].
• The problem of optimal rewrite sequence computation for weighted string rewriting systems [10], some computationally results [4, 8, 5, 6].

Part II : Tree Representations of Rhythm Notation, Term Rewriting and Weighted Tree Automata Techniques for Transcription.

Automated music transcription is the problem of converting a music performance into a score in common Western music notation. Dealing with rhythm notation is a particularly challenging task in this context. Roughly, it requires a quantization of arbitrary durations (in real-time unit, i.e. seconds) into durations in a musical-time unit (beats) that fit into the proportional rhythm notation, while satisfying various contextual constraints (related to readability, global consistency, music meter etc). We present a recent language-based approach where rhythm notations are represented by parse trees for grammars defining preferred rhythmic patterns. We will describe the theoretical framework behind this approach, which is strongly related to term rewriting, as well as results with it implementation.

• Generalities on music transcription.
• Tree-based representation and an equational theory of rhythm notation [7].
• A term-rewriting based approach to rhythm transcription.
• A weighted-tree-automata-based approach to rhythm transcription [3, 2, 11]. Demo and experiments.

Organization, Prerequisites

The lecture will be organized into a 30 minutes (non-technical) introduction to computer music, followed by two 1 hour sessions for each of the above part, the remaining 30 minutes being used for exercices, demos and experiments.

Some basic knowledge on rewriting and automata theory is assumed. Weighted automata and tree automata and basic properties will be introduced during the lecture but are not a prerequisite.

Bibliographical references

1. J. Berit, B. de Haas W., V. Anja, and van Kranenburg Peter. Finding repeated patterns in music: State of knowledge, challenges, perspectives. pages 277–297, 2013.
2. J. Björklund, F. Drewes, and N. Zechner. An efficient best-trees algorithm for weighted tree automata over the tropical semiring. In Proc. 9th Int. Conf. on Language and Automata Theory and Applications (LATA), number 8977 in LNCS, pages 97–108, 2015.
3. Z. Ésik and W. Kuich. Formal tree series. J. Autom. Lang. Comb., 8(2):219–285, Apr. 2003.
4. M. Giraud and F. Jacquemard. Weighted Automata Computation of Edit Distances with Consolidations and Fragmentations. working paper, July 2018. URL: https://hal.inria.fr/hal-01857267.
5. D. Hofbauer and J. Waldmann. Deleting string rewriting systems preserve regularity. Theoretical Computer Science, 327(3):301–317, 2004.
6. L. Huang. Advanced dynamic programming in semiring and hypergraph frameworks. In COLING, 2008.
7. F. Jacquemard, P. Donat-Bouillud, and J. Bresson. A Structural Theory of Rhythm Notation based on Tree Representations and Term Rewriting. In Proc. 5th Int. Conf. on Mathematics and Computation in Music (MCM), volume 9110 of LNAI. Springer, 2015. URL: https://hal.inria.fr/hal-01138642.
8. M. Mohri. Edit-distance of weighted automata. In J.-M. Champarnaud and D. Maurel, editors, Implementation and Application of Automata, pages 1–23, Berlin, Heidelberg, 2003. Springer Berlin Heidelberg.
9. M. Mongeau and D. Sankoff. Comparison of musical sequences. Computers and the Humanities, 24(3):161–175, 1990.
10. E. Ukkonen. ,Algorithms for approximate string matching. Information and Control, 64:100–118, 1985.
11. A. Ycart, F. Jacquemard, J. Bresson, and S. Staworko. A Supervised Approach for Rhythm Transcription Based on Tree Series Enumeration. In Proc. 42nd Int. Computer Music Conf. (ICMC), 2016. URL: https://hal.inria.fr/hal-01315689.