~A TEMPORAL GENERATIVE GRAPH GRAMMAR
FOR HARMONIC AND METRICAL STRUCTURE
Donya Quick, Paul Hudak
Yale University
Department of Computer Science
New Haven, CT USA
[email protected],
[email protected]
ABSTRACT
Most grammars that have been proposed for automated
music composition fall into conventional linguistic categories, such as context-free, context-sensitive, and probabilistic versions of each. For parsing (i.e. musical analysis) these distinctions are important, because of the computational complexity of parsing using these different
grammars. But, for generation (i.e. derivation), the complexity issues are sometimes different, and other goals for
having a generative grammar come into play.
In this paper we describe a new category of grammar
for generating abstract harmonic and metrical structure.
This class of grammars has two distinctive features. First,
it is temporal, meaning that production rules are parameterized by the duration of phrases, thus allowing us to express the metrical structure of a composition. Second, it is
a graph grammar, meaning that the parse trees (or derivation trees) are actually graphs allowing shared nodes, thus
enabling us to express the sharing, i.e. repetition, of specific musical phrases. We formally define this class of
grammars, describe our generative implementation of it,
and present a realistic example of its use: a specific grammar tailored to some styles of classical Western music. In
addition, we show that this class of grammars integrates
nicely with the notion of chord spaces to generate concrete chords from the abstract harmonic structure generated from the grammar.
1. INTRODUCTION
Automated composition is a complex task. Music is multidimensional, and the solution spaces are very large. Even
a seemingly simple task such as choosing pitches for
chords results in an exponential growth in computational
complexity. Having elegant and efficient algorithms is
therefore important for traversing these solution spaces.
As a further complication, those large solution spaces contain many poor or undesirable solutions. So, not only does
a generative algorithm for music have to be efficient, it has
to also find satisfactory solutions in a sea of noise.
For example, probabilistic context-free grammars
(PCFGs) are both efficient to use generatively and, if constructed appropriately, are capable of producing satisfactory solutions. But they also generate many unsatisfac
tory solutions. We could do better if at least some notions
of "satisfactory" could be captured in the grammar itself,
thus eliminating large undesirable regions of the solution
space.
To address this problem, we present a new category of
grammar that we refer to as a temporal generative graph
grammar (TGGG). TGGGs are powerful enough to express both temporal and sharing constraints, leading to
an effective method for the automated generation of harmonic and metrical structures of music.
There are two distinctive features of a TGGG. First,
one often wishes to preserve certain metrical constraints
in a composition. For example, one may wish to replace a
I chord with a II V I progression, but with the constraint
that the total duration of the II V I progression is the same
as that of the original I chord. In our TGGG framework,
this is easily specified with the rule I' IIt/4 Vt/4 It/2
This allows metrical constraints such as those found in
Generative Theory of Tonal Music (GTTM) [14] to be
captured by the grammar itself in a more formal way.
Technically, this feature results in an infinite number
of production rules, but, when used in a generative setting,
that is not problematic. The initial duration to associated
with a given grammar's start symbol directly determines
all the others. One can think of each rule as being a function that takes a time (duration) as an argument.
The second distinctive feature of a TGGG is that it
can capture the notion of repetition of a phrase-i.e., the
sharing of a particular sentential form in a derivation. For
example, if part of a composition has the form ABA, and
we expect both occurrences of A to be precisely the same
phrase, we can write the following in a TGGG (where we
have omitted any temporal superscripts for simplicity):
S - let x =A in xBx
(1)
where S, A, and B are nonterminals. Note that "A" in
this case means that some arbitrary number of production
rules are applied to the non-terminal A, and that the result
is used identically in the two occurrences of x (versus simply writing ABA, where each A could expand differently).
Therefore, a derivation tree is actually a more general type
of directed graph where branches can share nodes. These
shared nodes occur whenever there is a let expression.
Technically, this means that a TGGG is a context
177 2013 ICMC
