Melodic Morphing Algorithm in Formalism
Keiji Hirata1 , Satoshi Tojo2 , and Masatoshi Hamanaka3
12NTT/Future University Hakodate
Japan Advanced Iinstitute of Science and Technology
3PREST, JST/University of Tsukuba

Abstract. We introduce a feature structure, corresponding to a timespan tree based on ‘A Generative Theory of Tonal Music’ (GTTM) for amusic piece, and represent the reduction of the tree by the subsumption
among these feature structures. As the collection of them forms a lattice,
we can deﬁne the join and meet operations. We show a melodic morphingalgorithm based on these simple operations.

1Introduction

To facilitate composing music, we often render a pitch event, a chord, and so on
in a formal representation, together with supporting tools. However, there exists
a trade-oﬀ between descriptive power and simplicity in the formal representation,
two of which are basically incompatible. Descriptive power is the capability as
to how faithfully the composer’s original thoughts and emotions are expressed.
On the other hand, simplicity means how concise the description of the music is.
In general, the more abstract a description is, the shorter it is, and the less theproduct of writing and reading costs is. For instance, a Standard MIDI File hashigh descriptive power yet low simplicity, while the chord symbol is the opposite.
The trade-oﬀ can also be considered an issue of controllability in rendering music.
We argue that the key for being compatible is to separate the basic wellunderstood operations from creator’s intention for combining them. Intuitively,
these basic operations include the ones like set arithmetics; addition, subtraction,intersection, and union. Thus we are led to an algebraic framework, in which acreator assembles basic operations into a calculation process for a target task as
the creator intends.
The aim of the paper is to prepare the theoretical foundations for proving
the theorem for the property of a complicated musical task, melodic morphing.
We start with deﬁning the subsumption relation among melodies and building alattice of feature structures, each element of which corresponds to a melody. Using the join and meet operations in the lattice, we construct a melodic morphingalgorithm in the formal way.

2Time-Span Trees in Feature Structures

First, we design the feature structure, f-structure hereafter, for a time-span treeof a music piece. An f-structure is a directed acyclic graph as used in [?]. Since

2

Keiji Hirata, Satoshi Tojo, and Masatoshi Hamanaka
˜tree[]
 head {{ i , j }, ˜event }






˜tree
[] 
 head i ˜event 

left





dtrs
{···}

 dtrs {, ⊥} ˜tree
[]
 right  head j ˜event  
dtrs {· · ·}˜event pitchP[ itch]
barInteger pos
meter Length duration Length

Fig. 1. Feature structures for a time-span tree (left) and a pitch event (right)

the reduction is an intrinsic method to reﬂect musical structures [?], we canproperly map the reduction of the time-span trees to the subsumption relation‘⊑’ between f-structures.
The type of an f-structure is shown headed by ‘˜’ (tilde). An f-structure fora ˜tree is shown on the left-hand side of Fig. ??, and that for an ˜event on
the right-hand side. A binary tree has left and right branches where there aretrees recursively; we call these branches daughters (dtrs). Let σ be a ˜tree fstructure, then the left daughter and the right daughter, denoted by σ.dtrs.leftand σ.dtrs.right respectively, have recursively ˜tree type. The set notation {x, y}means the choice either of x or y. When σ.dtrs is ⊥ (empty), that is, there is nodaughter in the tree, σ.head must be a single pitch event.
The whole f-structure is referred to by a tag, which is shown by such a boxed
number as i or j . The head of a ˜tree f-structure must be either the headof its left daughter tagged by i , that of its right daughter tagged by j , oranother single pitch event. If σ.head = σ.dtrs.left.head, the node has the righthand elaboration of shape, and if σ.head = σ.dtrs.right.head, the left-handelaboration. As such, the head value at the parent level is recursively takenfrom either the left-hand or right-hand branch. As for ˜event type, feature pitch
include C4, B♭6, F ♯3, and so on. Feature pos stands for the start timing, andits value is an f-structure consists of feature bar (the n-th bar) and meter (m-thmeter measured by a quarter note). Feature duration also has a Length value.
A type of an f-structure speciﬁes a set of indispensable features. When noindispensable feature is missing, the typed f-structure is said to be full-fledged.
For example, ˜tree type requires the feature set of head and dtrs, and ˜event
type does pitch, pos.bar, pos.meter, and duration. The property ‘full-ﬂedged’ isconcerned with whether or not rendering a real melody from a f-structure representation. Then, we can provide the formal deﬁnition of subsumption relation
between f-structures, which allows the mechanical calculation.

3Calculus in Melody Lattice

Theorem 3.13 in Carpenter [?] deﬁnes that the uniﬁcation of f-structures A andB is the least upper bound of A and B. Therefore, we adopt the uniﬁcation as theMelodic Morphing Algorithm in Formalism

3deﬁnition of join in this paper, and the intersection of the uniﬁable f-structures
as that of meet.
Definition 1 (Meet and Join). Let A and B be full-fledged f-structures representing the time-span trees of melodies A and B, respectively.
If we can fix the greatest lower bound of A and B, that is, the greatest x suchthat x ⊑ A and x ⊑ B is unique, we call such x the meet of A and B, denoted
as A ⊓ B.
If we can fix the least upper bound of A and B, that is, the least y such thatA ⊑ y and B ⊑ y is unique, we call such y the join of A and B, denoted asA ⊔ B.
Definition 2 (Reduction Path). Suppose that each pitch event is given a beatstrength as a result of metrical analysis [?]. For such two f-structures (melodies)
A and B that TB ⊑ TA , a reduction path from A to B is defined as a sequenceof f-structures (melodies) obtained by removing a pitch event (a note) in A \ Bfrom A one-by-one, according to the algorithm, as follows:
Step 1: N := #(TA \ TB ), i := 0, and T0 := TA .
Step 2: Select a pitch event p of the minimum beat strength in Ti \ TB .
Step 3: Reduce Ti to Ti+1 by removing p.
Step 4: Iterate Steps 2 and 3 N times (i = 0 ∼ N − 1).
The resulting sequence T0 , T1 , T2 , · · ·, TN is the reduction path from A to B.
Note that at Step 2 the pitch events (notes) with the minimum beat strength
are the least important notes in the time-span tree. Since such least important notes are multiple and one is chosen from them nondeterministically, there
are more than one reduction path in general. The selection is justiﬁed by thetime-span reduction preference rules: TSRPR1 (metrical position) and TSRPR5(metrical stability) [?]. Hence the algorithm may automatically compute morethan one reduction paths, for every melody C on the reduction path from A toB, B ⊑C⊑
A holds.
//

4

Melodic Morphing Algorithm

Here, we present the morphing algorithm in the formal way[?,?].
Definition 3 (Melodic Morphing Algorithm). The algorithm consists ofthe following steps (Figure ??):
Step 1: Calculate TA ⊓ TB (meet).
Step 2: Select melody TC on the reduction path from TA to TA ⊓ TB , andselect TD on the reduction path from TB to TA ⊓ TB .
Step 3: Calculate TC ⊔ TD (join), and the result is morphing melody µ.
If C close to TA is chosen, the characters of melody A are reﬂected in output µ.
On the other hand, If C close to TA ⊓TB is chosen, those of A are less emphasizedin µ. The character of D, as opposed to B, behaves in the similar way.

4

Keiji Hirata, Satoshi Tojo, and Masatoshi Hamanaka

Melody ATAMorphing melody µ

Melody BTBTC TD

Partially reduced melody
Melody CTCTD

Melody D

Extracted common part
TA TB

Fig. 2. Melodic morphing algorithm

5Conclusion

We have provided an algebraic framework in which a music piece is represented
by an f-structure, corresponding to its time-span tree. As these f-structures wereordered in terms of the subsumption relation, we could construct a lattice ofmelodies and could deﬁne join and meet operations. We have presented a morphing algorithm, which is a complicated calculation in general, from combinations of these simple algebraic operations. In the near future, we will prove thealgorithm is exactly the interpolation of two given melodies.

References
1. Carpenter, B.: The Logic of Typed Feature Structures. Cambridge University Press(1992)
2. Hamanaka, M., Hirata, K., Tojo, S.: Melody Morphing Method Based on GTTM.
In: Proc. of ICMC 2008, pp.155–158 (2008)
3. Hamanaka, M., Hirata, K., Tojo, S.: Melody Extrapolation in GTTM Approach. In:ICMC 2009, pp. 89–92 (2009)
4. Lerdahl, F., Jackendoﬀ, R.: A Generative Theory of Tonal Music. The MIT Press,Cambridge (1983)
5. Marsden A.: Generative Structural Representation of Tonal Music. J. New Music
Research, vol. 34, no. 4, pp. 409–428 (2005)
6. Selfridge-Field, E.: Conceptual and representational issues in melodic comparison.
Computing in Musicology vol. 11, pp. 3–64, The MIT Press, Cambridge (1998)