/

2012

/
: 8 2012

/- ,
,

,
.. ,
.. ,
.. ,


. .
, . . . .

.
. . ,
. . . , . . . . .
.

11

1
1.1 . . . . . . . . . . . . . .
1.2 . . . . . . .
1.3 . . . . . .
1.4 , ,
1.5 . . . . . . . .
1.6 . . . . . . . . . . .

.
.
.
.
.
.

21
21
22
29
33
39
41

.
.
.
.

43
43
43
45
48

.
.
.
.
.
.

2
2.1 . . . . . . . . . . . . . . .
2.2 . . . . . . . . . . . .
2.3 . . . . . . . . . . . . . . .
2.4 A L( 3 )
4

.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.

.
.
.
.

2.5 . . . . . . . . . . . . . . . . . . . . . . . . 56
2.6 . . . . . . . . . . . . . . . . . . . . . . . . . 57
2.7 . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3
3.1 . . . . . . . . . . . . . . . . . . . . . . . .
3.2 . . . . . . . . . . . . . . . . . . . .
3.3 . . . . . . . . . . . . . . . . . . .
3.4 A( E), A( A) A( D ) . . . . . . . . .
3.5 . . . . . . . . . . . . .
3.6 . . . . . . . . .
3.7 . . . . . . . . . . . . . . . .
3.8 . . . . . . . . . .
3.9 . . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

63
63
64
65
69
74
75
77
79
81

4
83
4.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
4.2 . . . . . . . . . . . . . . . . . . 84
9

10
4.3
4.4
4.5
4.6
4.7
4.8

. . . . .
. . . . . . . . .
Morris . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

87
91
93
96
100
103

105

107

113

SUMMARY

123

,
.
,
.
, .
.
. .
1 . (formal system)
. X ( ),
X/( ) ( ).
M MUS ,

[

({c(k), c(k)], . . . , a(k), a(k)], b(k)}) {], [}

k Z

,
.
D

][ = = [], c(k)]] = d(k), . . . , a(k)]] = b(k), b(k)] = c(k + 1), k Z

MD = M MUS / D
( ).

MD / B B
Md Md
Babbitt. mod12 modulo
Babbitt.

12

2 .

. ()
X

p ,

x X.

:
q x,
p.

.

.
, Hiller (1959), Xenakis (1961,1963), Barbeau
(1965).

A
B
C
D
E
F
G
H

A
0,021
0,357
0,084
0,189
0,165
0,204
0,408
0,096

B
0,084
0,089
0,076
0,126
0,150
0,136
0,072
0,144

C
0,084
0,323
0,021
0,126
0,150
0,036
0,272
0,144

D
0,336
0,081
0,019
0,084
0,135
0,024
0,048
0,216

E
0,019
0,063
0,336
0,171
0,110
0,306
0,102
0,064

F
0,076
0,016
0,304
0,114
0,100
0,204
0,018
0,096

G
0,076
0,057
0,084
0,114
0,100
0,054
0,068
0,096

H
0,304
0,014
0,076
0,076
0,090
0,036
0,012
0,144

A, B, C, ... (
, trams) .
tram
trams
.
.
20 , .. 3
P.Boulez.

13

, , .
Marc Chemillier

(superimposition)

w = a1 a2 a k , u = 1 2 ( k < )
:

w k u = (1 1 )(2 2 ) (k k ) k+1
: ,
.
: . ( ).

. Chemillier (1990c)
.
L X , Brzozowski (1964) A L L,

u1 L = {w/uw L}, u X
u1 L
u L.
2,
1
34 , 16
.
Zn = {0, 1, . . . , n 1, }
modn
A  1 
L , k
2

,
1k .
2

14

A 
L

1
2k

1.

= k

2
Zn .
2.
< .

X = {/

}
<

2k

3. :

i
i
i

j
j
j
j

i+j,

i + j < n

0 ,

i + j = n

i + j > n

0
(contours)

.
20 , Schoenberg (1967) Toch (1948)
. Seeger (1960)
, , +, , .
w :
I (w), F(w), L(w) H (w).
Adams (1976)
. .. < I, F >
I (w) F(w), . Kolinski (1965)

15

( L)/( L) ( L)/( L), ( L), (. ( L), ( L)) I (w) L(w) (. L(w), F(w)
L(w), H (w)), w L .
Polansky
(1987), Friedmann (1985) Morris (1987). c : X X {1, 0, 1} xy
X 1,0,1 xy
, .
w = x1 xk c( xi x j ) ,
.
Morris (1993)
w

y
x

Morris
w. (. ) ,
w.
Tenney Polansky (1980).
Buteau Mazzola (2000)
.

.

x 1 x k 7 c ( x 1 x 2 ) c ( x 1 x k ) c ( x 2 x 3 ) c ( x 2 x k ) c ( x k 1 x k ).
Polansky (1996)

x 1 x k 7 c ( x 1 x 2 ) + + c ( x 1 x k ) + c ( x 2 x 3 ) + + c ( x 2 x k ) + + c ( x k 1 x k ).
:

16

c : X X R
f : X X Y (Y ) .

. 3
Schutzenberger

(1961)
.
.
, () X
c : X X R, ( x, y)
c( xy). C : X R :
k1

C ( x1 x2 x k ) =

c ( x i x i + 1 ),

x1 , . . . , xk X, k 2

i =1

C( x ) = 0 = C(), x X.
,
,
.
F : X R F, Schutzenberger

(1961) LD ( F)
F . , A( F)
. F : X R ,
u X , u1 F : X R

(u1 F)(w) = F(uw), w X .

3 :

A( A), A( D ), A(E) ,
.

17

A(SA) sasc : Xnote Xnote R,

.

A(S)
.

A(asc ) x1 ,
x2 , . x1 xk ,

.

A(GPR3a)), ( A(GPR2a)))
GPR3a) ( GPR2a))
Lerdahl Jackendoff.
F( GPR3a) F( GPR2a)
GPR3a)
GPR2a) .

Madsen Jorgensen (2003) Marvin (1988, 1991)

.
" ".
(sequential machines)
.
, M X
Y
M

/u

q0

M q , q0
u Y . M
.
. ( (transducers),

18

.), (speech
recognition), Mohri, Pereira, Riley (2000,2002), , Mohri (1997), Pereira, Riley and Sproat (1994)
, Culik II and Fris (1995).

(music identification), Weinstein
Moreno (2007), Mohri, Moreno, Weinstein (2008).

( ) .
Eilenberg (1974)
.
f : X Y

f () = , f (st) = f (s)w, s, t, X , w Y .
s1 f : X Y

(s1 f )(t) = f (s)1 f (st), t X .

, .
f : X Y
.
4 :

Schoenberg .

Mcont

{1, 0, 1} w
f cont : Xnote
0, 1, -1
w ,
.

M1 M2 ,

{ L, S, 0, S, L} f 2 : Xnote

f 1 : Xnote

{11, . . . , 11} f 1 ( xy) =

L, S, 0, S, L xy
leap step, f 2 ( xy) = 11, . . . , 11
x y.

maxima minima Morris.

19

.
Mcont , M1 M2 ,
. , M1 Mcont M2 M1 .
4.6
Y R,
Freedman Forte,
(multiple viewpoints).

20

 1

1.1
. (formal system)
. X ( ),
X/( ) ( ).
M MUS ,

[

({c(k), c(k)], . . . , a(k), a(k)], b(k)}) {], [}

k Z

,
.
D

][ = = [], c(k)]] = d(k), . . . , a(k)]] = b(k), b(k)] = c(k + 1), k Z

MD = M MUS / D
( ).

Md Md
MD / B B
Babbitt. mod12 modulo
Babbitt.

22

1.2

1.2
, c

c, c], d, d], e, f , f ], g, g], a, a], b

()

()
.
, ()
.


..
.

b(k)
..
.

c(k)]
c (k)
..
.

b (0 )
..
.

c(0)]
c (0 )

( )

k = 1, 2, . . .

..
.

b(k)
..
.

c(k)]
c(k)
..
.

1.1.

X (k) = {c(k), c(k)], . . . , b(k)} k = 0, 1, 2, . . .

X NOTE = X (0) X (1) X (1)

Xacc = {], [} (]: , [: )

.1

23

( X NOTE Xacc )

s = w0 x1 ( k 1 ) w1 x2 ( k 2 ) w2 x p ( k p ) w p

w0 , w1 , w2 , . . . , w p Xacc

x1 (k1 ), x2 (k2 ), . . . , x p (k p ) X NOTE .

s1 = ][b(2)c(o)]d (3)][ f (0), s2 = f (1)] g(1), .

,
,

s = x1 ( k 1 ) w1 x p ( k p ) w p ,

x1 (k1 ), . . . , x p (k p ) X NOTE , w1 , . . . , w p Xacc

.
x1 (k1 )w1
x p (k p )w p y1 (1 )u1 yq (q )uq

x 1 ( k 1 ) w 1 x p ( k p ) w p y 1 ( 1 ) u1 y q ( q ) u q ,
M MUS .
s, t M MUS
s vD t,
:

][ = , [] =

c(k)]] = d(k)

d(k)]] = e(k)

e(k)] = f (k)

f (k)]] = g(k)
0 =

g(k)]] = a(k)

a(k)]] = b(k)

b(k)] = c(k + 1)

k = 0, 1, 2, . . .

c(0)]][]d(3) f (1)][[, d(0)d(3) f (1)[

,

c(0)]] = d(0), [] = ][ = .

24

1.2

1.
1. s s D s ( ).
2. s D s0 s0 D s ( ).
3. s D s0 s0 D s00 , s D s00 ( ).
4. s1 D t1 s2 D t2 , s1 s2 D t1 t2 .
, sw tw .
5. s D t w Xacc
D

D M MUS M MUS / D
MD ,

MD = M MUS / D .
MD D
.
s [s] D

[s] D = {t/t M MUS , t D s}

s = f (1)b(1)

[s] D = { f (1)wb(1)w0 /w, w0 L(], [)}

w
L(], [) Xacc
. L(], [)
Dyck , Berstel (1988).
MD

[s] D [s0 ] D = [ss0 ] D

[s] D [s0 ] D
s s0 ss0 ( ) ..

[c(0)[a(0)]] D [ f (0) g(1)]] D = [c(0)[a(0)] f (0) g(1)]] D .

2.

b(k)[[ D a(k)

a(k)[[ D g(k)

g(k)[[ D f (k)

f (k)[ D e(k)
1 =

e(k)[[ D d(k)

d(k)[[ D c(k)

c(k)[ D b(k 1)

k = 0, 1, 2, . . .

.1

25

. b(k 1)] D c(k) b(k 1)][ D c(k)[,

b(k 1) D c(k)[ .
, a(k)]] D b(k) a(k)]][[ D b(k)[[
a(k) D b(k)[[.
.
3.

c(k)] D d(k)[

d(k)] D e(k)[

f (k)] D g(k)[
2 =

g(k)] D a(k)[

a(k)] D b(k)[

k = 0, 1, 2, . . .

. c(k)]] D d(k) c(k)]][ D d(k)[

c(k)] D d(k)[, .

,
.

, k = 0, 1, 2, . . .
x (k)w, w Xacc

1. w , |w|] =
|w|[ , w D x (k)w D x (k).
2. |w|] > |w|[ ,

x (k)w D x (k)]|w|] |w|[ .

|w|] |w|[ 12 q
r,

|w|] |w|[ = 12q + r, 0 r < 12.

26

1.2

x (k)]|w|] |w|[ D x (k)]12q+r

D x (k)]12q ]r
D x (k) ]12 ]12 ]r
| {z }
q

D x (k + 1) ]12 ]12 ]r
| {z }
q 1

..
.

D x (k + q)]r
,

x (k)w D x (k + q)]r .
, x () ( )
c(), x ()
c() (). k x k.
..
.

x ()
..
.

x () = c()]k x()k1

c()]
c ()
..
.

1.2.

:
2.1. k x (k + q) k + r < 12,

x (k + q)]r D y(k + q) y(k + q)]

, y {c, d, e, f , g, a, b}.
2.2. k x (k + q) k + r 12,

x (k + q)]r D y(k + q + 1) y(k + q + 1)]

.1

27

, y {c, d, e, f , g, a, b}.
3. |w|[ > |w|] ,

x (k)w D x (k)[|w|[ |w|]

|w|[ |w|] 12

|w|[ |w|] = 12q + r, 0 r < 12

x (k)[|w|[ |w|] D x (k)[12q+r

D x (k)[12q [r
D x (k) [|12 {z
[12} [r
q

D x (k 1) [|12 {z
[12} [r
q 1

..
.

D x (k q)[r
x ()
c( + 1) < x >
..
.

c ( + 1)
b()
..
.

x () = c( + 1)[< x()>1

x ()
..
.
1.3.

k x () k + < x () >= 14
3.1. < x (k q) > + r < 12,

x (k q)[r D y(k q) y(k q)[

28

1.2
, y {c, d, e, f , g, a, b}.

3.2. < x (k q) > + r 12,

x (k q)[r D y(k q 1) y(k q 1)[

, y {c, d, e, f , g, a, b}.
,

s = x1 ( k 1 ) w1 x p ( k p ) w p ,
x1 (k1 )w1 , . . . ,
x p (k p )w p .
s
s0 s D s0 .

XRED =

{c(k), c(k)], d(k )[, d(k), d(k)], e(k )[, e(k), f (k ), f (k)],

k Z

g(k)[, g(k), g(k)], a(k)[, a(k), a(k )], b(k)[, b(k )}

s, t s H t
(2 ).
4.
. [s] H
s s

XRED

[s] H = [s] D XRED

, [s] H = {t/t XRED
, t H s}, s XRED
.

XRED
H , M H ,

M H = XRED
/ H .

MD M H
, , : MD M H .

[s] D 7
[s] H
5. MD M H .

.1

29

[s] H , s XRED

.
[

{d(k)[, d(k)], g(k)[, g(k)], a(k )[, a(k )]}

A=

k Z

s XRED
|s| A
A s. ,
s A .
, s 2|s| A .

6. s XRED

card[s] H = 2|s| A .
s, t :
1. s t

| s | = | t |.
2. s {c(k)], e(k)[, f ( k )], b( k )[},
k = 0, 1, 2, . . ., t
.
3. s A , t
(
c(k)] d(k)[ , d(k)]
e(k)[ , f (k)] g(k)[
, ).

1.3

c]

a]

d
d]

a
g]

e
g

f]

1.4.

30

1.3

, "modulo 12 ",
0, 1, . . . , 11.

12 .
mod12 , mod12

k =
k + ,
= k + 12,

k + < 12
k + 12

..

7 8 = 15 12 = 3,
6 6 = 12 12 = 0,
5 3 = 8.

0
1
2
3
4
5
6
7
8
9
10
11

0
0
1
2
3
4
5
6
7
8
9
10
11

1
1
2
3
4
5
6
7
8
9
10
11
0

2
2
3
4
5
6
7
8
9
10
11
0
1

3
3
4
5
6
7
8
9
10
11
0
1
2

4
4
5
6
7
8
9
10
11
0
1
2
3

5
5
6
7
8
9
10
11
0
1
2
3
4

6
6
7
8
9
10
11
0
1
2
3
4
5

7
7
8
9
10
11
0
1
2
3
4
5
6

8
8
9
10
11
0
1
2
3
4
5
6
7

9
9
10
11
0
1
2
3
4
5
6
7
8

10
10
11
0
1
2
3
4
5
6
7
8
9

11
11
0
1
2
3
4
5
6
7
8
9
10

: mod12 k k .

.
, Z12 0, 1, 2, 3, 4, 5,
6, 7, 8, 9, 10, 11, Z12 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}.

.1

31

Xnote = {c, d, e, f , g, a, b} Mmus

(Xnote Xacc )

x1 w1 xk wk xi Xnote , wi Xacc
, i = 1, . . . , k

. Mmus .
s, t Mmus s d t,

:

][ = , [] = ,
c]] = d, d]] = e, e] = f ,
0 =
f ]] = g, g]] = a, a]] = b,

b] = c

d Mmus
Md = Mmus / d .
Md d .
7.

c[ d b, b[[ d a, a[[ d g
g[[ d f , f [ d e, e[[ d d
1 =

d[[ d c
2 =

c ] d d [, d ] d e [, f ] d g [
g ] d a [, a ] d b [

t Mmus

s Mmus .
(1 ) .
(2 ).
s s0
s d s0 .

Xred = {c, c], d[, d, d], e[, e, f , f ], g[, g, g], a[, a, a], b[, b}.
s, t s h t,
(2 ).
,
8. s , s Xred
s 2|s| A ,

A = {d[, d], g[, g], a[, a]}.

32

1.4

,
h Xred
/ M ,
Xred
h
h

Mh = Xred
/ h

1.1.
Md Mh .
Babitt "" , modulo 12 , Babitt (1960,1961).

. Babitt B : M MUS Mmus x1 (k1 )w1 x p (k p )w p
x1 w1 x p w p , :

B ( x1 ( k 1 ) w1 x p ( k p ) w p ) = x1 w1 x p w p
. ..
x1 , . . . , x p Xnote , k1 , . . . , k p Z w1 , . . . , w p Xacc

B( f (2)][c(0)c(1)[b(0)) = f ][cc[b .
B ,

s = x 1 ( k 1 ) w 1 x p ( k p ) w p , t = y 1 ( 1 ) u1 y q ( q ) u q

B(st) =
=
=
=

B ( x 1 ( k 1 ) w 1 x p ( k p ) w p y 1 ( 1 ) u1 y q ( q ) u q )
x 1 w 1 x p w p y 1 u1 y q u q
B ( x 1 ( k 1 ) w 1 x p ( k p ) w p ) B ( y 1 ( 1 ) u1 y q ( q ) u q )
B(s ) B(t)

B . B
, ,

[s] D 7 [ B(s)]d
MD Md . ( ) Md
MD / B , B

[s] D B [t] D [ B(s)]d = [ B(t)]d .

1. Babitt

Md
MD / B .

2. Mh M H / B

Mh
MH / B .

.1

33

1.4 , ,
1.1,
(. 1.1)
..
.

b(0) a(0)]] c(1)[

a(0)] b(0)[
a(0) g(0)]] b(0)[[
g(0)] a(0)[
g(0) f (0)]] a(0)[[
f (0)] g(0)[
f (0) e(0)] g(0)[[
e(0) d(0)]] f (0)[
d(0)] e(0)[
d(0) c(0)]] e(o)[[
c(0)] d(0)[
c(0) d(0)[[ b(1)]
..
.
1.5.

( x, x 0 )
(k, k0 ) . k k0 , ( x, x 0 ) ,
. ( x, x 0 ) ( x 0 , x ).

34

1.4 , ,

( x, x 0 ) k, k0
.
..
.
..
.

x0

k0

x0

k0

..
.
..
.
1.6.

( x, x 0 ) .
- ( -) ( x, x 0 )
.
(c(1), d(2)]) 9

c (1 ), d (1 ), e (1 ), f (1 ), g (1 ), a ( 1 ), b (1 ) , c (2 ) , d (2 ) .

, ( x ( p), x ( p)]),
( x ( p)[, x ( p)) .
,
(b( p), c( p + 1)) .

(e( p), f ( p)),

, ( x ( p), ( x + 1)( p)[),

( x ( p)], ( x + 1)( p)) ,
x Xnote , p Z.
,

.1

35

c d[[ b]
b a]] c[

c] d[

a] b[

d c]] e[[

a g]] b[[

d] e[

g] a[

e d]] f [

g f ]] a[[

f e] g[[
f ] g[
1.7.

, ( x, x 0 ) x, x 0
k, k0 1.7.
( x, x 0 ), x, x 0
k, k0
k k0 .
( x, x 0 ) ( x 0 , x )

. -

36

1.4 , ,

, .
- = 1, 2, . . . , 8 ( -)
.
, , , .
2, 3 , 6 7 , ,
, 1, 4 , 5 8
, .
:
1
1
2
2
2
2
3
3
3
3
4
4
4
5
5
5
6
6
6
6
7
7
7
7
8
8

(0 )
(1 )
(0 )
(1 )
(1 )
(1,5 )
(1 )
(1,5 )
(2 )
(2,5 )
(2 )
(2,5 )
(3 )
(3 )
(3,5 )
(4 )
(3,5 )
(4 )
(4,5 )
(5 )
(4,5 )
(5 )
(5,5 )
(6 )
(5,5 )
(6 )

Babitt
.. B(c(2)]) = c].

B0 : Mmus Xnote
, B 0 ( x1 w1 x k w k ) = x1 x k
. .. B0 (c ]) = c. x1 , . . . , xk Xnote w1 , . . . , wk Xacc

B0 B : M MUS Xnote

.1

37

.. c(2)] 7 c.

() y1 y2 y8 yi { x, x ], x [, x ]], x [[/x Xnote }

B 0 ( y1 ) B 0 ( y2 ) B 0 ( y8 )

cde f gabc

de f gabcd
gabcde f g

e f gabcde
abcde f ga

f gabcde f
bcde f gab

y1 , y2 , . . . , y7 (). y1
, y5 , y4 , y7 ...
:
.

()

38

1.4 , ,
()

( )

()

1.8.

x
1.7
()
x. ,
1.8,
x.
, x .1.5
,
() x. x. ..
c(1)

c(1)d(1) b(1)c(0)d(0) b(0)c(1)d(1) b(1)

.
,

.
,
,
- -
, c(1)

g(1)

a(1)

f (0 )

g (0 )

a (0 )

e(1)

f (1)

d (0 )

e (0 )

f (0 )

c(1)

d(1)

b(1)

c (0 )

d (0 )

.1

39

3 .
() (),
().
(), ().
I, I I, . . . , V I I

.

1.5
(Integer representation)
..
.

..
.

b(k), a(k)]], c(k + 1)[

7 11(k)

a(k)], b(k)[

7 10(k)

a(k), g(k)]], b(k)[[

9( k )

g(k)], a(k)[

8( k )

g(k), f (k)]], a(k)[[

7( k )

f (k)], g(k)[

6( k )

f (k), e(k)], g(k)[[

5( k )

e(k), d(k)]], f (k )[

4( k )

d(k)], e(k)[

3( k )

d(k), c(k)]], e(k)[[

2( k )

c(k)], d(k)[

1( k )

c(k), d(k)[[, b(k 1)]

0( k )

..
.

..
.

40

1.6

MD
[

{0(k), 1(k), . . . , 11(k)}

G=

k Z

, MD G . G

: G G G :

( )

k( x )
k ( x ) =

(k + k0 )( x + x 0 )
(k + k0 12)( x + x 0 + 1)

k + k0 < 12
k + k0 12.

O(0) , k( x )

k( x )
O(0) = (k + 0)( x + 0) = k( x ).
k( x ) (12 k)( x
1),

k( x )
(12 k)( x 1) = (k + 12 k)( x x 1) = O(0).

.
k1 ( x1 ), k2 ( x2 ), k3 ( x3 )
G.

k1 ( x1 )
[k2 ( x2 )
k3 ( x3 )] =

(k1 + k2 + k3 )( x1 + x2 + x3 )
(k + k2 + k3 12)( x1 + x2 + x3 + 1)
1
(k1 + k2 + k3 24)( x1 + x2 + x3 + 2)

k1 + k2 + k3 < 12
12 k1 + k2 + k3 < 24
k1 + k2 + k3 24

, : k1 ( x1 ), k2 ( x2 ) G

( )

k 1 ( x1 )  k 2 ( x2 ) = r ( x1 x2 + q )

q r k1 k2
12.

k1 k2 = 12q + r, 0 r < 12

9. G
() ( )
.

.1

41

1.6

mod12 modulo Babbitt B .
,
.

42

1.6

 2

2.1
, () . :
.


( ).
L X , Brzozowski (1964)
A L L
L.
.
,
34 .
modn Zn

.

2.2
-
Xnote = {c, d, e, f , g, a, b} 1 . ()

1 1 1 1
Xd = {1, , , , }
2 4 8 16
1

Xnote
.

44

2.2

( x, d)
x Xnote d Xd .
,

s = x1 d1 x2 d2 xk dk (Xnote Xd ) .
dur (s) = d1 + d2 + + dk .

1
1
1
1
1
s = (a, )(b, )( f , 1)(b, )(a, )( g, )
4
8
2
8
2

. , , ( 24 , 34 , 44 , 68 , 78
58 , ) .



( ) .
() : ,

( )

( )

. ( ) .
.
-
,
..

.2

45

3
1
1
1
1
1
1
1
1
1
( )( f , )( g, )( f , )|(e, )(c, )|(e, )( f , )|( g, )( g, )|
4
4
4
4
2
4
2
4
2
4
: ,
.. 43 s ( Xnote Xd ) ,
s 34 ;
, L( 34 ) ( L( 43 ) ( Xnote Xd ) ) 34 ,
s L( 34 ) ;

L( 43 ).

2.3

A = (X, Q, I, E, T )

X
Q A
I Q T Q
A ,
E Q X Q () A.
A
Q ,

(q, x, p) E.
: A q
x, p.
i (i I )
i t (t T )
t .

46

2.3

q0

x1

x2

q1

q2

qk1

xk

qk

(q0 I )
(qk T ). x1 x2 xk
A A.
A A |A|.
A

FA : X N (N )
: w X

FA (w) = w.
L X
( ) .
A (deterministic)
q w
q
w.
, Eilenberg
(1974).

c
c

Ac :

Xc

Xc = Xnote {c}

Xnote

Xc
Xnote
c ().
w = f ccgcc

i
i

f
f

i
i

g
g

i
t

c
c

c
c

t
t

.2

47

FAc ( f ccgcc) = 2.
w = cccc,

i
i
i

t
q

c
c
c

t
t
t

FAc (cccc) = 3.
FAc
c.
, L X ,
(
) L.
A L L .
Brzozowski (1964)
L. , L
s X

s1 L = {t/st L}

, s1 L X
"" s L.
, A L

Q L = {s1 L/s X }

s 1 L

(sx )1 L

A L ,
1 L = L,
s1 L s L. A L
L.
3. ( Brzozowski 1964). L X
A L , L .

2.4 A L( 3 )
4

48

2.4 A L( 3 )
4
L( 34 ) ,
A L( 3 ) .
4

L( 43 ). s L( 34 )

3
s = s1 sk , dur (si ) = , i = 1, . . . , k
4

3
3
3
s 1 L( ) = 1 L( ) = L( )
4
4
4
A L( 3 )
4

.
,

3
3
s = s1 sk sk+1 , dur (si ) = , i = 1, . . . , k, dur (sk+1 ) < ,
4
4

(2.1)

3
3
1
L ( ).
s 1 L( ) = s
k
+
1
4
4

(2.2)

3
3
t s1 L( ) st L( ) t = t0 t1 t
4
4
3
dur (t j ) = 4 , j = 1, . . . ,
3
3
3
sk+1 t0 t1 . . . t L( ) sk+1 t L( ),
4
4
4
1
3
t sk+1 L( 4 ), 2.2.
s 2.2,
3
s 1 L( ) =
4
A L( 3 ) q
dur (sk+1 t0 ) =

" ", . , s1 L( 43 ), dur (s) < 43 .

dur (s) = dur (s0 ) <

3
3
3
= s1 L( ) = s01 L( )
4
4
4

. s1 L( 43 ),
dur (s) < 43 ,

.2

d1 + + d k <

3
4

49

d1 , . . . , dk Xd :

8 1
4 1
2
1
1. 21 = 16
, 4 = 16
, 8 = 16
, 16

10 1
1
9 1
6 1
1
5 1
1
3
2. 21 + 18 = 16
, 2 + 16
= 16
, 4 + 18 = 16
, 4 + 16
= 16
, 8 + 16
= 16

1
11 1
1
7
3. 21 + 18 + 16
= 16
, 4 + 18 + 16
= 16

4. ()
0
1 L( 34 ) 16
.
A L( 3 )
4

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, q
, 16.
Xnote Xd . , A L( 3 )
4

( x,d)

x Xnote

x .
, X = {8, 4, 2, 1}
1
} < 34
Xd = {1, 12 , 14 , 81 , 16

.
A L( 3 ) :
4

50

2
1

2
1

2
1

2
1

10

11
4, 8

4
4

4, 8
2

2, 4, 8

Xd

2.4 A L( 3 )

.2

51

: i, j
{0, 1, . . . , 11}

i + j , i + j < 12

0 , i + j = 12

q , i + j > 12

q , x X

0 .

52

2.4 A L( 3 )
4

0
j1
j1
j2
j1 + j2
..
.

j p1
j1 + + j p1
jp
0
..
.

0
k1
k1
k2
k1 + k2
..
.

k q 1
k1 + + k q 1
kq
0

j1 + + j p = = k1 + + kq = 12.

s = ( x1 , d1 )( x2 , d2 ) ( xk , dk )

.2

53

34 , d1 d2 dk Xd
i1 i2 ik {8, 4, 2, 1} , i1 , i2 , . . . , ik
d1 , d2 , . . . , dk
16 (
). i1 i2 ik
s 43 .

1
1
1
1
1
1
1
1
1
1
1
s = (e, )(e, )(e, )(e, )( f , )( g, )(a, )(b, )(a, )( g, )( f , )
4
4
4
8
8
4
4
4
4
4
8
1
1
1
1
1
1
1
1
1
1
1
( g, )( f , )(e, )(d, )(d, )(d, )(d, )(d, )(e, )( f , )( g, )
8
8
8
4
4
4
4
8
8
4
4
34 .

1111111111111111111111
4448844444888844448844
"".

4442244444222244442244
.
:

0
2

2
2

4
2

6
2

8
4

s 43 .
, }
.

54

2.4 A L( 3 )
4

Xd

1
12
= =
,
2
16

1
6
= =
,
4
16

1
3
=  =
.
8
16

.
, Xnote
  (, 1), (, 12 ),
1
), (, 14 ), (, 81 ), (, 16

3
3
12

3
12

3
12

4
3
12

3
12

3
12

3
12

3
12,6

10

3
12,6

11

.2

3
12,6

12,6

12,6

55

56

2.5

1
,
Xd 32

1 1 1 1 1
Xd = {1, , , , , }
2 4 8 16 32
,
A L( 43 ).
A X = {1, 2, 4, 8, 16},
Q = {0, 1, 2, . . . , 20, 21, 22, 23, q}. :
i Q {q} j X

i + j , i + j < 24

0 , i + j = 24

q , i + j > 24

q , x X.

0 .

2.5
modn Zn .

Zn = Zn {} = {0, 1, . . . , n 1, }
: Zn Zn Zn : i, j Z n

i j = i + j,
= 0,
= ,

i + j < n
i + j = n
i + j > n

.2

57

a = = a , a Zn .
Z3 = {0, 1, 2, } ""

0
1
2

0
0
1
2

1
1
2
0

2
2
0

(n, m) Zn Xm = {1, 2, . . . , m} .

ij

i Z n , j Xm .

0 .
1
}. 24 Xd = {1, 21 , 41 , 18 , 16
n = 8, Z8 A L( 2 )
4

X8 = {1, 2, . . . , 8} (
1,2,4,8). 44
1
} n = 16.
Xd = {1, 12 , 41 , 81 , 16

2.6

.
(sequential machines, Eilenberg 1974) ,

. s

s = s1 sk sk+1 s

(2.3)

3
3
3
dur (s1 ) = = dur (sk ) = , dur (sk+1 ) < , dur (sk+1 f irsts ) >
4
4
4
s1 sk sk+1
s 34 .

58

2.6

1
1
1
1
1
1
1
1
1
1
s = (d, )(c, )(d, )(e, )( f , )(, )(d, )(e, )( f , )(a, )
8
16
8
8
2
4
8
8
8
8
1
1
1
1
1
1
1
1
1
1
( g, )(a, )(d, )(c, )( f , )( g, )(e, )(c, )(d, )(, )
8
16
8
8
8
16
8
8
2
4
1
1
1
( g, )( g, )( f , )
8
16
8
= (d, 3)(c, 1)(d, 2)(e, 2)( f , 12)(, 4)(d, 2)(e, 2)( f , 2)( a, 2)
( g, 3)(a, 1)(d, 2)(c, 2)( f , 3)( g, 1)(e, 2)(c, 2)(d, 12)(, 4)
()
( g, 2)( g, 1)( f , 2)
42

1
1
1
1
(d, )(c, )(d, )(e, )
8
16
8
8
.
X Y, M X
Y Q ,
i Q,

Q X Q, (q, x ) 7 q x
: Q X Y . M = ( Q, i, ). M
Q,

x/u

q0

q x = q0 (q, x ) = u.
: Q X Y :

(q, ) = , (q, wx ) = (q, w)(q w, x )

q Q, x X w X .
q Q w = x1 x2 xk

q1

x1 /u1

q2

x2 /u2

qk

xk /uk

qk+1

.2

59

(q, w) = u1 u2 uk
f M : X Y M

f M (w) = (i, w), w X .

f : X Y f = f M
M.
4
. M( 34 )

0, 1, 2, . . . , 11,
:

( x, j)/( x, j)
i + j , i + j < 12
( x, j)/( x, j)|

( x, j)/

( x, j)/

0 , i + j = 12

, i + j > 12

, j

M( 43 )

1
1
1
1
1
1
1
1
s = (c, )(d, )(b, )(d, )(e, )(c, )(c, )( f , )
2
4
8
8
2
2
16
4

(c, 8)(d, 4)(b, 2)(d, 2)(e, 8)(c, 8)(c, 1)( f , 4)

(c, 8)(d, 4)|(b, 2)(d, 2)(e, 8)|(c, 8)(c, 1) =

1
)
= (c, 21 )(d, 14 )|(b, 81 )(d, 81 )(e, 21 )|(c, 12 )(c, 16

60

2.6

s 34 .
4 M( 43 )
.

.

( x, d) ( x, d1 ) ( x, d2 )
d1 + d2 = d

( x, d1 )^
| ( x, d2 )
, s

s = s1 s k s k +1
dur (s1 ) = = dur (sk ) = 43 dur (sk+1 ) < 43 . sk+1 .
Z12 = {0, 1, . . . , 11},
0 :

( x, j)/( x, j)

i + j , i + j < 12

( x, j)/( x, j)|

( x, j)/( x, j1 )^
| ( x, j2 )

0 , i + j = 12

j2 , i + j1 = 12 j2 < 12.

N ( ) . .. N ( 42 )
Z8 = {0, 1, . . . , 7}, 0 12 8.
() ,
N ( 24 )

.2

(d, 3)/(d, 3)

(c, 1)/(c, 1)

61
(d, 2)/(d, 2)

(e, 2)/(e, 2)|

( f , 12)/( f , 8)^
| ( f , 4)

( f , 2) /( f , 2)

(e, 2)/(e, 2)

(d, 2)/(d, 2)

(, 4)/(, 4)|

( a, 2)/( a, 2)|

( g, 3)/( g, 3)

( a, 1)/( a, 1)

(d, 2)/(d, 2)

(c, 2)/(c, 2)|

( f , 3) /( f , 3)

( d, 12) /( d, 8)^
| ( d, 4)

(c, 2)/(c, 2)|

(e, 2)/(e, 2)

( g, 1)/( g, 1)

(, 4)/(, 4)|

( g, 2)/( g, 2)

( g, 1)/( g, 1)

( f , 2) /( f , 2)

(d, 3)(c, 1)(d, 2)(e, 2)|( f , 8)^

| ( f , 4)(, 4)|(d, 2)(e, 2)( f , 2)( a, 2)|( g, 3)( a, 1)
(d, 2)(c, 2)|( f , 3)( g, 1)(e, 2)(c, 2)|(d, 8)^
| (d, 4)(, 4)

" " .

, .

2.7
Brzozowski

1
.
43 , 16
Zn = {0, 1, . . . , n 1, } modn

62

2.7

A 
L

1
2k

,
1k .
2

A L( 7 , 1 )
8 64
1. 78 64

56
7
=
8
64
Z56 .
2.
< 56
64

X = {1, 2, 4, 8, 16, 32}

3. :

i
i
i

j
j
j
j

i+j,

i + j < 56

0 ,

i + j = 56

i + j > 56

 3


3.1
(contours), ,
, Dowling (1978),
Friedmann (1985), Marvin (1988,1991), Morris (1993), Polansky (1996),
Bor (2006), Kolinski (1965), Quinn (1997), Buteau (1998), Mazzola (2002a).
c
( x, y) X
c( xy). , w = x1 x2 xk
X , k k- Mc (w) c( xi x j )

.
(weighted automata).
, ( Schutzenberger

(1961)), , X
R .
A, D, E , , .
, , . , 3.6

, Cambouropoulos
(2002).

64

3.2

Polansky c
Mc (w)
. , asc (w) w. 3.7.
Mc (w) Honingh (2006) w
w c.
3.7.

GPR2a) GPR3a) Lerdahl Jackendoff (1983).

3.2
, X , X
X
e.
(contour) X ,
c : X X R c( xy)
( x, y) X .
C : X R c
:
k1

C ( x1 x2 x k ) =

c ( x i x i + 1 ),

x1 , . . . , xk X, k 2

i =1

C ( x ) = 0 = C ( e ), x X
.
- Xnote = {c, d, e, f , g, a, b}.

- .
Xnote

A, D : Xnote

R
, .

asc, desc : Xnote Xnote R

asc( xy) =

1, y x
0,

.3

desc( xy) =

65

1, y x
0,

w, ( A(w), D (w))
Freedman w, Freedman (1985).
eq : Xnote Xnote R,

eq( xy) =

1, x = y
0,

E : Xnote
R, w
( x, x ) xx
w.

E = Ec + Ed + + E a + Eb

Ex : Xnote
R w
( x, x ) x
w.

. Xnote
.

3.3

,
.

A = (X, Q, I, E, T, I , E , T )

(X, Q, I, E, T ) ,

I : I R, E : E R T : T R,
,
A.
A, ,

66

3.3

q ,

x/r

p ,

I (q) = r, E (q, x, p) = r, T ( p) = r,
.
(label) (weight)

c:

q1

x1 /r1

q2

x2 /r2

xk1 /rk1

xk /rk

qk

qk+1 b

lab(c) = x1 x2 . . . xk , weight(c) = ar1 r2 . . . rk b.

A FA : X R

FA (w) = w.
. ,

q ,

q ,

x/1

p ,

p ,

. A

A.
1. , Fliess (1975),
HMM, Rabiner (1989).

.3

67

( ) F : X R.
. X
[ X , R ]
F : X R.

( F1 + F2 )(w) = F1 (w) + F2 (w), (F)(w) = F(w), w X

R ( F1 , F2 , F [ X , R ], R ).
L [ X , R ]
,

F1 , F2 L F1 + F2 L
F L R F L
[ X , R ].
F [ X , R ],
{1 F1 + + k Fk / F1 , . . . , Fk F , 1 , . . . , k R } [ X , R ],
F < F >.
F1 , . . . , Fk : X R

1 F1 + + k Fk = 0

1 F1 (w) + + k Fk (w) = 0, w X

1 = = k = 0.
F1 , . . . , Fk : X R L L.
F L

F = a1 F1 + + ak Fk , 1 , . . . , k R.
k L dim(L).
, F : X R , u X ,
u1 F : X R

(u1 F)(w) = F(uw), w X .

u1 (v1 F) = (vu)1 F, e1 F = F, u, v X .

68

3.3

e . F : X R ,
LD ( F),

LD ( F) =< u1 F/u X > .

F : X R
LD ( F).
Schutzeberger

(1961),
Fliess (1974), Berstel Retenauer (1988,2010).
4. F : X R LD ( F)
.
F : X R
LD ( F) , ,

LD ( F) =< F1 , . . . , Fk >
F1 , . . . , Fk , ( )
F.
q1 , . . . , qk (
F1 , . . . , Fk ) x X i = 1, . . . , k

x/1
qi

x/k

q1
..
.

qk

x 1 Fi = 1 F1 + + k Fk .

1 , . . . , k x 1 Fi F1 , . . . , Fk .
: F LD ( F), F = e1 F,
F1 , . . . , Fk :

F = a1 F1 + + ak Fk .
qi i

.3

ai

69

qi , ai 6= 0.

: qi Fi (e) 6= 0

qi

Fi (e)

A( F) F
.

3.4 A( E ), A( A ) A( D )

Ec : Xnote
R.
LD ( Ec ) Ec .
+

u1 Ec = Ec (u) 1 + last(u)1 Ec , u Xnote

= Xnote
{ e}

,
(1 : Xnote
R 1(w) = 1, w Xnote
last(u) ()
u) LD (Ec ) 1, x 1 Ec ( x
Xnote ), Ec = e1 Ec . , x Xc = Xnote {c} x 1 Ec =
Ec , LD (Ec ) 1, c1 Ec , Ec .

1 1 + 2 c 1 Ec + 3 Ec = 0

1 1(w) + 2 (c1 Ec )(w) + 3 Ec (w) = 0, w Xnote

1 + 2 Ec (cw) + 3 Ec (w) = 0, w Xnote

w = c, d, cc

1 + 2 = 0
1 = 0
1 + 22 + 3 = 0

3.4 A( E), A( A) A( D )

70

: 1 = 2 = 3 = 0.
1, c1 Ec , Ec LD ( Ec ). ,
ic , qc , tc
Ec , c1 Ec , 1.
,

x 1 (c1 Ec ) = Ec ( x Xc ), c1 (c1 Ec ) = c1 Ec + 1,
x 1 Ec = Ec ( x Xc ), x 1 1 = 1 ( x Xnote )

Xc

ic

qc

Xc

tc

Xnote

Ec = 01 + 1Ec + 0c1 Ec
ic , tc

1(e) = 1, Ec (e) = 0, c1 Ec (e) = 0.

A( A) .

+
u1 A = A(u)1 + (lastu)1 A, u Xnote

LD ( A)

c1 A, d1 A, e1 A, f 1 A, g1 A, a1 A, b1 A = A, 1

(3.1)

. , A( A)

qc , qd , qe , q f , q g , q a , qb , t
(3.1).

y1 ( x 1 A) = 1 + y1 A ( x Xnote , y Xx< )
( Xx<
x), :

.3

qx

qy

71

x, y Xnote

Xnote

t
Xc < Xd <
Xa<
qc

...

qd

qa

qb

Xc< = {d, e, f , g, a, b}, Xd< = {e, f , g, a, b}, . . . , Xa< = {b}.

,

A = 0c1 A + + 0a1 A + 1b1 A + 01

qb A( A) t
( 1(e) = 1, ( x 1 A)(e) = 0, x Xnote ).
A( A).
A( A)
R
A : Xnote
.
A( A)
w = cdba,

qb

qc

qb

qc

d q
d

b
b

t
t

a
a

t
t

FA( A) (cdba) = 2 = A(cdba).

, w = dccd

qb

d q
d

qc

qc

3.4 A( E), A( A) A( D )

72

FA( A) (dccd) = 1 = A(dccd).

n

w = x1 xi xi +1 x k x k +1 x n

xi < xi +1 , . . . , x k < x k +1
n .

qb

x1

q x1

xi

xi +1

q xi

xi +2

xn

..
.
..
.
..
.

qb

x1

q x1

xk

q xk

x k+1

x k+2

xn

2. A( A)
= 1, .
, asc sasc : Xnote Xnote R ,

sasc( xy) = k, y k x
= 0,
A(SA)
sasc A( A)

qc

Xc <

d/2
e/3
qc

..
.

b/12

.3

73

D : Xnote
R,
:

pc , pd , pe , p f , p g , p a , pb , t,
pc t.

px

py

( x, y Xnote ).

Xnote

t
Xd >
Xa>
pc

pd

Xb >

...

pa

pb

Xd> = {c}, . . . , Xa> = {c, d, e, f , g}, Xb> = {c, d, e, f , g, a}.

A( E).
, A( E) E

i, qc , qd , . . . , qa , qb , t
i , t

74

3.5

Xnote

t
c

qc

...

qd

qa
b

qb

qx

qy

x, y Xnote

3.5
Madsen Jorgensren (2003)
() ,
. s ( Xnote Xd )
Xd = {1, 1/2, 1/22 , . . . , 1/26 }, ,

s=

1
x1 , a
21



1
x2 , a
22

1
xk , a
2k

, a j {0, 1, 2, 3, 4, 5, 6}, x j Xnote

abval : Xnote Xd R, abval

1
x, a
2

= a,

( x, 1/2a ) ,
0
( x 0 , 1/2a ) a > a0 , a = a0 a < a0 . ,

.3

75

asc, eq desc. A( A), A( E) A( D ).
Marvin (1988, 1991)

,
.

3.6
X pitch
c, d, e, f , g, a, b

b]

c]]
c]

X pitch :

d
d[

d[[

d]]

e]

f[

g[[

a]]

d]

e[
e[[

c[

X pitch X pitch

C1 = {, , }
C2 = {
}
C3 = X pitch X pitch (C1 C2 )
X pitch

B1 = { }, B2 = X pitch B1 .
s : X pitch X pitch R

s( xy) = p1 ( x ) + p2 ( xy), x, y X pitch

p1 : X pitch R p2 : X pitch X pitch R
(penalty functions)
.
S : X pitch R
k1

S ( x1 x2 x k ) =

[ p1 (xi ) + p2 (xi xi+1)]

i =1

76

3.7

( p1 , p2 ). u X pitch

u1 S = S(u) 1 + last(u)1 S

S, c1 S, d1 S, . . . , b1 S, 1
LD (S).
penalty system ( p1 , p2 )
, LD (S).
penalty system

p 1 ( x ) = 0,
= 4,

x B1
x B2

p2 ( xy) = 0, ( x, y) C1
= 1, ( x, y) C2
= 4, ( x, y) C3

, Campoyropoulos (2002).
A(S) i, qc , qd , . . . , qb , t
, :

X pitch

t
y/s( xy)
z/s(yz)
qx

A(S) :

qy

qz

y
i

FA(S) ( x1 xn ) n n .
i

x1

q x1

x2

xi 1

qi 1

xi /s( xi 1 xi )

xi +1

xn

.3

77

3.7
w = x1 x2 . . . xk c : X X R

Mc ( w ) =

c ( x1 x1 )

c ( x1 x k )
..
.

..
.

c ( x k x1 )

c( xk xk )

. ,
C 3.2,
Mc (w)
.
Mc (w) , Polansky (1996),
( Buteau-Mazzola (2000) ).

c : X R, c ( x1 x p ) =

c ( x i x j ), x 1 , . . . , x p X

1 i < j p

. LD (c )
c .
10. : u X + ,

u1 c = c (u) 1 + c +

| u | x ( x 1 Hc )

(3.2)

xX

Hc : X R
`

Hc ( y 1 y 2 y ` ) =

c ( y 1 y i ),

yi X, 1 i `

i =2

|u| x x u.
. ,
X

u = x1 x2 x k , w = y1 y2 y ` ( xi y j X )

78

3.7

(u1 c )(w) = c (uw)

`

c ( xi y j ) +

c ( xi x j ) +

1 i < j k

c ( yi y j )

1i < j`

i =1 j =1
k

= c (u) + ( xi1 Hc )(w) + c (w)

i =1

= c (u) + c (w) + | u| x ( x 1 Hc )(w)

i =1

.
3.2

1, c , x 1 Hc ( x X )

(3.3)

LD (c ). c
3.3. ,
c = asc,

1, asc , x 1 Hasc ( x Xnote {b})

LD (asc ). asc ( x1 . . . xk )
x1 ,
x2 , .
, .

Xnote

A(asc ) : Xnote

c
a

qc
..
.

qa

Xnote

Xc <
Xa<

Xnote

.3

79

qc , . . . , q a , qb . Xx<
x ( 3.3). w = cddc asc (cddc) = 2
,

i
i

qc

qc

qc
t

d
d

t
t

c
c

t
t

F asc (cddc) = 2.

A asc
.
,
(compactness). w = x1 xk c, Mc (w), ,
k

COMPAc ( x1 xk ) =

c ( xi x j )

i,j=1

Honingh (2006). c ,
COMPAc (w) ()
w.
COMPA asc A(asc ) .

3.8
, Lerdahl Jackendoff
(1983).
GPR2a) x1 x2 x3 x4
x2 x3 ( x1 x2 | x3 x4 ),
[outset( x2), onset( x3)]
x1 , x2 x3 , x4 .
, GPR3a) x1 x2 x3 x4 x2 x3 ( x1 x2 | x3 x4 ),

80

3.8

( ) x2 , x3
x1 , x2 x3 , x4 .
, 4 c : X 4 R
C : X R

C(u) = 0, |u| < 4

k3

C ( x1 x k ) =

c ( x i x i + 1 x i + 2 x i + 3 ),

k4

i =1
4
GPR3a) 4 c : Xnote
R

c( x1 x2 x3 x4 ) = 1,
= 0,

x1 x2 | x3 x4

, C : Xnote
R

s Xnote

GPR3a).
LD (C).
f : Xnote
Y , Y = Xnote {|}

f (s)
s Xnote
s
GPR3a).
, :
1. s Xnote

f (s) = w|u, |u| 3, s1 C = C(s)1 + u1 C.

.
. f (s) = w| x1 x2 t Xnote

(s1 C)(t) = C(st) = C(s) + C( x1 x2 t) = C(s) + (( x1 x2 )1 C)(t)

s 1 C = C ( s ) 1 + ( x1 x2 ) 1 C

.
LD (C)

u1 C(|u| 3), 1.
, C

qu (|u| 3), t.
i = qe
t. .

.3

qx

qxy

81

qxyz

qxyz

c( xyzw) = 1

c( xyzw) = 0

w
qzw

qxyz

qyzw

GPR2b),
GPR3b)-GPR3d) Lerdahl Jackendoff (1983)
GPR3a) .

3.9
:

A( A), A( D ), A(E) ,
.

A(SA) sasc : Xnote Xnote R,

.

A(S)
.

A(asc ) x1 ,
x2 , . x1 xk ,

.

82

3.9

A(GPR3a)), ( A(GPR2a)))
GPR3a) ( GPR2a))
Lerdahl Jackendoff.
A( GPR3a)) A( GPR2a)) ,
GPR3a) GPR2a)
.
(.. /, Madsen, Jorgensren (2003),
Marvin (1998,1991), , .)
.
,
( ) .

 4

4.1
(sequential machines)
. .
( (transducers), ...)
(speech recognition), Mohri, Pereira, Riley (2000,2002),
, Mohri (1997), Pereira,
Riley and Sproat (1994), , Culik
II and Fris (1995) (music identification), Weinstein Moreno (2007), Mohri, Moreno Weinstein
(2008).

.

( ) .
Schoenberg ( (transposition), (inversion), (retrograde)),
( )
1, -1, 0
, , Morris (1993),
Friedmann (1985), Marvin (1991), maxima minima
, Morris (1993), Bor (2006), ,
Freedman Forte.

84

4.2

4.2
. u, v, Y ,
u1 v w ( ) v =
uw. w , u1 v = .

(u1 u2 )1 v = u21 (u11 v), u1 u = , 1 v = v, u1 , u2 , v Y

.
f : X Y
.

f () = , f (st) = f (s)w, s, t, X , w Y

(4.1)

f : X Y ,
s X s1 f : X Y

(s1 f )(t) = f (s)1 f (st), t X

(4.2)

(4.1).
11. s X , s1 f

1 f = f , (s1 s2 )1 f = s21 (s11 f ), s1 , s2 X .

f : X Y

f (st) = f (s) f (t), f () = , s, t, X

.
f : X Y
f , s1 f = f (s X )
t X

(s1 f )(t) = f (s)1 f (st) = f (s)1 f (s) f (t) = f (t).

2,
, .

M(X, Y, Q, i, )
X, Y, Q ,
, i .

.4

85

Q X Q, (q, ) 7 q 
: Q X Y .
M

/u

q0

q  = q0 (q, ) = u.
: Q X Y
:

(q, ) = , (q, s) = (q, s)(q s, ) (q Q, X, s X )

q Q s =
1 2 k

q1

1 /u1

q2

2 /u2

qk

k /uk

qk+1

(q, s) = u1 u2 uk .
M

f M : X Y , f M (s) = (i, s), s X .

f M , s, t, X ,

f M (st) = f M (s)(i s, t)
f : X Y M , f = f M .
.
5. (Eilenberg 1974). f : X Y

,

card{s1 f /s X } < .

86

4.2

,
M f f .
f

Q f = {s1 f /s X }.
1 f = f

Q f X Q f , (s1 f ) = (s)1 f
f : Q f X Y , f (s1 f , ) = f (s)1 f (s),
X , s X .
, f : X Y s1 f = f s X
(. Q f = { f }), .

Q f X Q f , ( f , ) 7 f
f : Q f X Y , f ( f , ) = f ( )
X . M f

/ f (),

X.

, Schoenberg Z T : Z Z (t Z )
I : Z12
t
12
12
12
12

I (1 k ) = (12 1 ) (12 k )
Tt (1 k ) = (1 t) (k t)
, 1 i k, . i Z12
Z12 = {0, 1, . . . , 11} mod12
mod12 ( . 1).
I
Tt

0/0 11/1
i

0/t 11/11 + t
i

.4

87

R : Z12
Z12
, R(1 k ) = k 1

. ,

.

4.3
.

c : X X R
. f : X X Y
( X , Y ).
f : X Y :

f () = = f (), X
f (1 2 k ) = f (1 2 ) f (2 3 ) f (k1 k ), i X, k 2

.
f : X Y , s, t X ,

f (st) = f (s) f (last(s)t),

last(s) s.

s1 f = last(s)1 f , s X
f

Q f = { 1 f / X } { f }, 1 f = f
f
M f (cardX ) + 1 q (
X ), q = i ( )

88

4.3

/ f ( )

, X.

X - Xnote =
{c, d, e, f , g, a, b} Y = {1, 0, 1}.

f cont : Xnote Xnote {1, 0, 1}

:

f cont ( xy) = 1, 1 0,
y x, x x = y,
.

c1 f cont , d1 f cont , . . . , a1 f cont , b1 f cont , f cont

. x, y Xnote , x < y,

( x 1 f cont )(y) = f cont ( x )1 f cont ( xy) = f cont ( xy) = 1

(y1 f cont )(y) = f cont (y)1 f cont (yy) = f cont (yy) = 0,

x 1 f cont 6= y1 f cont . ( x 1 f cont )( x ) = 0
f cont ( x ) = ( ), x 1 f cont 6= f cont . ,
M f cont Mcont

(cardXnote ) + 1 = 8 qc , qd , . . . , qa , qb , i ()

Mcont :

x/

qx

y/0, 1, 1

qy

x, y Xnote

4.1 Mcont

x = y, x < y x > y . .., w = dc f f e

d/

qd

c/-1

qc

f /1

qf

f /0

qf

e/-1

qe

.4

89

f Mcont (dc f f e) = 1 1 0 1 = 1 1 0 1.
Y = {1, 0, 1}
. Y1 = { L, S, 0, S, L},

L = , S = ,1
0 = , S = , L = ,
Y2 = {11, . . . , 1, 0, 1, . . . , 11}
( ) ( ) .

f 1 : Xnote
{ L, S, 0, S, L}

f 2 : Xnote
{11, . . . , 1, 0, 1, . . . , 11}

M1 M2 Mcont

y/ 1, 0, 1

qx

qy

qx

y/ L, S, 0, S, L

qy

qx

y/ 11, . . . , 1, 0, 1, . . . , 11

qy

.
Mcont , M1 , M2 , . , M = ( Q, i, ) :
X Y M0 = (Q0 , i 0 , 0 ) : X Y 0
(, ) : Q Q0
: Y Y 0 ,

(i ) = i 0 ( )

q1

/u

q2

M,
1

90

4.3

( q1 )

/(u)

( q2 )

M0 ( ).
M M0
.
12.

f M0 = f M
.
. : Y Y 0
,

(u1 v) = (u)1 (v) u, v Y .

, s = 1 2 k X

i0

1 /u10

q10

2 /u20

q20

q0k1

k /u0k

q0k

M0 i 0
s,

f M0 (s) = u10 u20 u0k .

,

qi0 = (qi ) ui0 = (ui ) qi Q

ui Y , 1 i k.

1 /u1

q1

2 /u2

q2

qk1

k /uk

qk

M
i s,

f M ( s ) = u1 u2 u k .

f M0 (s) = u10 u20 u0k = (u1 ) (u2 ) (uk )

= ( u1 u2 u k )
= ( f M (s)) = ( f M )(s)
f M0 = f M .

.4

91

Mcont M1 M2 ,
. M1 Mcont
, = id Q , : { L, S, 0, S, L}
{1, 0, 1} ( L) = (S) = 1, (0) = 0,
(S) = ( L) = 1. , M2 M1 (id Q , )

: {11, . . . , 1, 0, 1, . . . , 11} { L, S, 0, S, L}

( x ) = L, 11 x < 2, (2) = (1) = S, (0) = 0,

(1) = (2) = S ( x ) = L 2 < x 11.

4.4

2.5 34 ,
.

f : (Xnote Xd ) [(Xnote Xd ) { | }]

m1 ) s = s1 sk sk+1 , dur (si ) = 43 , 1 i k, dur (sk+1 ) < 43 ,

f ( s ) = s1 | s2 | | s k | s k +1
m2 ) s = s1 sk sk+1 s, dur (si ) =
dur (sk+1 f irst(s)) > 43 ,

3
4,

1 i k, dur (sk+1 ) <

3
4,

f ( s ) = s1 | s2 | | s k | s k +1

M( 34 ).
f .
s m1 ), t ( Xnote Xd )

(s1 f )(t) = f (s)1 f (st)

= (s1 |s2 | |sk |sk+1 )1 f (st)
1
1
= s
k+1 (s1 | s2 | | sk |) (s1 | s2 | | sk |) f (s k+1 t)
1
1
1
= s
f (s k+1 t) = (s
k+1 f (s k+1 t) = f (s k+1 )
k+1 f )(t)

92

4.4

1
s1 f = s
k+1 f .
s m2 ),

(s1 f )(t) = f (s)1 f (st) = f (s)1 f (s) = = I (t)

I t
. s1 f = I . f
s1 f (dur (s) < 34 ), I .

.
1. dur (s) = dur (s0 ) < 43 s1 f = s01 f .

(s1 f )(t) = (s01 f )(t) t (Xnote Xd ) .

, t = t0 t1 dur (st0 ) = 34 ,

(s1 f )(t) = f (s)1 f (st) = s1 st0 | f (t1 ) = t0 | f (t1 ).

t , t = t0 ( x, d)t1
dur (st0 ) < 34 , dur (st0 ) + d > 34 ,

s1 f (t) = f (s)1 f (st) = t0 .

.
2. 0 dur (s) < dur (s0 ) < 43 s1 f 6= s01 f .
,
t (s1 f )(t) 6= (s01 f )(t).

dur (s) = k/16, dur (s0 ) = /16, k 1, k, {1, 2, 4, 8, 16}

t = t0 ( x, 1/8),

t0 = ( x1 , 1/16)( x2 , 1/16) ( x11 , 1/16).

11
f (s0 t) = s0 t0 dur (s0 t0 ) = 16
< 43 dur (s0 t) = 13/16 > 43 .
f (st) = st dur (st) 12/16 = 3/4.
(s1 f )(t) = t (s01 f )(t) = t0 , s1 f 6= s01 f ,
.

f
,

3
d 1 + d 2 + + d k < , ti X d (1 i k )
4

.4

93

0/16, 1/16, 2/16, . . . , 11/16

0/16 1 f = f . ,
M( 34 )

0, 1, 2, . . . , 11,
I . M( 34 )
2.5.
.

4.5 Morris

maxima minima Morris
.
R A A ,

R

: u, v A , u
v u = w1 u0 w2 , v = w1 v0 w2
R

(u0 , v0 ) R. u
v u = v
R

u = u0
u1
u2 u k
uk+1 = v
R

, , u
v u
v.
R

u A

R

v A u
v.
R

:
R

(confluent)
u

u1
u2

u1

u2

94

4.5 Morris

(terminating)
u A
.

(convergent) .

,
R

u A ,
n f (u), u.
u 7 n f (u)
A A .

Morris w Xnote
(
morris(w)) w

xx x ( x Xnote )
xyz xz, x < y < z x > y > z ( x, y, z Xnote ).
morris(de f gc) = dgc.
Maxima(w) w
w w,
Morris (1993). w ,
.

maxima(cd f cd) = c f cd
maxima(cdc) = cdc, ...
,

maxima(w) = maxima(morris(w )), w Xnote

.

w maxima(w), w 7 maxima(w)
, ( ) .
w , maxima(w)

w, f max (w).

maxima(cdc) = cdc, f max (cdc) = d.

.
f max (w) = f max (morris(w)), w Xnote

.4

95

f max : Xnote
Xnote

, s, t Xnote

f max (st) = f max (s) f max (last2 (morris(s))t)

last2 (w)
w.

s1 f max = last2 (morris(s))1 f max , |s| 2.

c1 f max , d1 f max , . . . b1 f max , 1 f max = f max

, x < y x 1 f max 6=

y1 f max ,

( x 1 f max )(yz) = y y > z (y1 f max )(yz) = .

Q f max = {( xy)1 f max / x 6= y} { x 1 f max / x Xnote } { f max }

cardQ f max = (72 7) + 7 + 1 = 50,

M f max 50 :

qxy ( x, y Xnote , x 6= y), qx ( x Xnote ), i = q .

M f max

y/

x/

x/

qxy

qx

z/

y/

qyz

x < y < z x > y > z x > y y < z

qxy

96

4.6

qxy

z/y

qyz

x < y y > z.
, w = cdcec

c/

qc

d/

qcd

c/d

qdc

e/

qde

c/d

qec

f M (w) = dd = dd.
f max (w)
w,
().

4.6
Conklin Witten (1995), (multiple
viewpoint) ,
k-

f : X Y1 Yk

N3 (N
Freedmann (1985) f r : Xnote
), w
(n1 , n0 , n1 ) ,
w.
Forte (1973)
N12 , mod12 w Z
f or : Z12
12
(n0 , n1 , . . . , n11 ) nk k
w (0 k 11).
v : X M,
M . M

: M M M, (m1 , m2 ) 7 m1 m2

m1 (m2 m3 ) = (m1 m2 )m3 , m1 , m2 , m3 M

.4

97

e M

me = m = em, m M.
: M M M,
T : M M M

m1 T m2 = m2 m1 , m1 , m2 M.
( M, , e) , ( M, T , e) ,
( M, , e).
,
,
.
( M, , e)

mm1 = mm2 = m1 = m2 , m1 , m2 , m M
( M, , e) , M 1
M ( ) = . 0 M
0 = , = 0
= 0 .
1 ( )
.

1 = e, e1 = , (1 2 )1 = 21 (11 ), , 1 , 2 , M
.

.
1. N k k-

(n1 , . . . , nk ) + (n10 , . . . , n0k ) = (n1 + n10 , . . . , nk + n0k )

(0, . . . , 0).

(n1 , . . . , nk )1 (n10 , . . . , n0k )

n1 n10 , . . . , nk n0k .

(n1 , . . . , nk )1 (n10 , . . . , n0k ) = (n10 n1 , . . . , n0k nk )

98

4.6

2. Y1 Yk k-
(s1 , . . . , sk ) si Yi , 1 i k,

(s1 , . . . , sk )(s10 , . . . , s0k ) = (s1 s10 , . . . , sk s0k )

( 1 , . . . , k ), i Yi , i =
1, . . . , k.
(s1 , . . . , sk )1 (s10 , . . . , s0k )
si si0 , 1 i k.

1 0
(s1 , . . . , sk )1 (s10 , . . . , s0k ) = (s11 s10 , . . . , s
k s k ).

Y (k = 1).
( M, , e) ( ) , ( M, T , e) (
) .
f : X M, M ,

f () = e, f (st) = f (s) s, t X , M.
f s X

s1 f : X M, (s1 f )(t) = f (s)1 f (st), t X

.
X M 4.2 Y
M.
f : X M , ( X
M) .
4.2.
Freedmann

x/

qx

y/

qy

x, y Xnote

= (1, 0, 0), (0, 1, 0) (0, 0, 1), x < y, x = y

x > y, .
Forte

.4

0/(1, 0, . . . , 0)

99

11/(0, . . . , 0, 1)

Z
(retrograde) R : Z12
12

R(st) = R(t) R(s) s, t Z12

 Z12
( u1  u2 = u2 u1 )

R(st) = R(s)  R(t), s, t Z12

R Z12
) T .
(Z12
R

x/x,

x Z12 .

, x1 x2 xk ,

x1  x2   x k = x k x2 x1
.
.
f i : X Yi , 1 i k, .

f =< f 1 , . . . , f k >: X Y1 Yk , f (s) = ( f 1 (s), . . . , f k (s)), s X

( ),

s1 f =< s1 f 1 , . . . , s1 f k >, s X .
, M f

Q f = {< s1 f 1 , . . . , s1 f k > /s X }

100

4.7

M f

< s 1 f 1 , . . . , s 1 f k >

/(u1 ,...,u )

< (s)1 f 1 , . . . , (s)1 f k >

ui = f i (s)1 f i (s ), 1 i k, X.

4.7

.
f : X R , X (R, +, 0)
.
, Q f f .
f : X R , Berstel - Retenauer (2010), Salomaa
- Soittola (1980). A f f
3 :
1. f

s f : X R, (s f )(t) = f (st), t X .2
2. f 1 , . . . , f k LD ( F)

LD ( f ) =< s f /s X >
, Culik II Kari (1980).
3. f 1 , . . . , f k A f
:
f s f s1 f
3, f
s1
2

.4

f1

x/1
fi

101

x/k

..
.

x X, ai R (1 i k)

fk

x f i = 1 f 1 + + k f k
1 , . . . , k x f i
f 1 , . . . , f k .
4. f LD ( f )
f 1 , . . . , f k

f = 1 f1 + + k f k .
k- ( 1 , . . . , k ) A f .
5. k- ( f 1 (), . . . , f k ()) A f (
).
1
}
X = Xnote Xd Xd = {1, 12 , 41 , . . . , 16
f d : ( Xnote
Xd ) R

w = ( x1 , d1 ) ( xk , dk )
f d ( w ) = d1 + + d k
A f d f d

A f d : ( x, d)/d

( x, d)/d

( x, d)/d

( x, d) Xnote Xd

4.2 A f d

f d

f d (w1 w2 ) = f d (w1 ) + f d (w2 ), w1 , w2 (Xnote Xd )

( x, d)/d

x Xnote , d Xd .

102

4.8

.
f : X R s X

(s1 f )(t) = f (st) f (s), t X

s 1 f = s f f (s )1
1 : X R 1(s) = 1, s X .
LD ( f )
f f
1,

LD ( f ) =< Q f {1} > .

f
dim < Q f > < .
f , Q f
< Q f > ,
f .
6.
(R, +, 0).
. "" .

f : (Xnote Xd ) R, f (( x1 , d1 ) ( xk , dk )) = d1 dk
,

(( x1 , d1 ) ( xk , dk ))1 f = d1 dk f d1 dk 1
= d1 d k ( f 1 )

.
, LD ( f ) ,
f dim LD ( f ) = 1, f
.

.4

103

4.8
:

Schoenberg .

Mcont

f cont : Xnote
{1, 0, 1} w
0, 1, -1
w ,
.

M1 M2 ,

f 1 : Xnote
{ L, S, 0, S, L} f 2 : Xnote

{11, . . . , 11} f 1 ( xy) =

L, S, 0, S, L xy
leap step, f 2 ( xy) = 11, . . . , 11
x y.

maxima minima Morris.


.
Mcont , M1 M2 ,

. , M1
Mcont M2 M1 .
4.6
Y R,
Freedman Forte,
(multiple viewpoints).

104

4.8

1.
- ( ). tilling automata GiammarresiRestino (1997) on-line tessellation automata, Inoue - Nakamara (1997).

2.
. I, I I, I I I M , IV, V, V I

I
I
II
I I IM
IV
V
VI

a11
a21
a31
a41
a51
a61

II
a12
a22
a32
a42
a52
a62

I I IM
a13
a23
a33
a43
a53
a63

IV
a14
a24
a34
a44
a54
a64

V
a15
a25
a35
a45
a55
a65

VI
a16
a26
a36
a46
a56
a66

( )

6 6 ( aij )

( )

B3

1
2
A1
A2
A3

Ai { I, I I, . . . , V I } Bi .
( ) : "" ..
II V a25 , .
( )
() .

106

(un ),
,

B1 + + Bn un , n 0
(un ) Fibonacci (u0 = u1 = 1
un+2 = un+1 + un ) Lindenmayer
, Prusinkiewitz P. and Lindenmayer A. (1996), Rosenberg G.
and Salomaa A. (1980), Prusinkiewicz P. (1986).
"
", ( aij ) (
= 1
= 0),
, Moore C. and Crutchfield J. (2000).
( ) .

3.
f M : X Y M (X
) ()
X :

u1 u2 f M (u1 ) = f M (u2 )

F : X R :

F1 F2

u [r ]

F1 (u) =

F2 (u) {r }.

u [r ]

max,
min, . ,
.

, . (1997). .
, .
Adams C. (1976). Melodic Contour Typology Ethnomusicology 20.2:179215.
Andreatta M. (1999). La theorie mathematique de la musique se Guerino
Mazzola et la construction de canons rythmiques. DEA Dissertation,
EHESS / Ircam.
Andreatta M. (2003). Methodes Algebriques en Musique et Musicologie
du XXeme Siecle: Aspects theoriques, analytiques et compositionnels.
PhD Thesis, Ircam / EHESS.
Andreatta M. (2004). On group-theoretical methods applied to music:
some compositional and implementational aspects. Perspectives in Mathematical Music Theory.
Assayag G. (2002). Hans G. Feichtinger and Jose-Francisco Rodrigues,
eds. Mathematics and Music: A Diderot Mathematical Forum. Berlin:
Springer.
Babbitt M. (1960). Twelve-Tone Invariants as Compositional Determinants. The Musical Quarterly, Vol. 46, No 2, pp. 246-259.
Babbitt M. (1961). Set Structure as a compisitional Determinant. Journal
of Music Theory, Vol. 5, No 1, pp. 72-94.
Barbaud P. (1965). Introduction a la Composition Musicale Automatique,
Dunod e d.
Barbaud P. (1968). La musique discipline scientifique , Paris, Dunod.
Berstel, J., Reutenauer, C. (1998). Rational Series and their languages.
EATCS Monographs on Theoretical Computer Science, Springer.

108

Berstel, J., Reutenauer, C (2010). Noncommutative Rational Series with

Applications, Cambridge University Press.
Bor, M. (2006). Contour Reduction Algorithms: A Theory of Pitch and
Duration Hierarchies for Post-Tonal Music. Ph.D. Thesis, The University
of British Columbia, Canada.
Bozapalidou M. (2012). Automata and Music Contour Functions. Journal
of Mathematics and Music (to appear).
Brzozowski J. A. (1964). Derivatives of Regular Expressions. J. Assoc.
Comp. Mach. Vol. 11, No 4, pp. 481-494.
Buteau, C. (1998). Motivic Topologies and Their Meaning in the Motivic
Analysis of Music. Masters Thesis, Universite Laval.
Buteau C., Mazzola G (2000). From Contour Similarity to Motivic Topologies, In: Musicae Scientiae Europan Society for Cognitive Sciences of
Music (ESCOH), vol. IV, no 2, pp. 125-149.
Campouropoulos E. (1998). Towards a General Computational Theory of
Musical Structure. PhD Thesis, The University of Edinburgh, Faculty of
Music and Department of Artificial Intelligence.
Campouropoulos E. (2000). Pitch Spelling: from Numbers to Sharps and
Flats. Proceedings of VIII Brazilian Symposium on Computer Music. Fortaleza, Brazil.
Chemillier M. (1987) Monoide libre et musiqu. RAIRO Inf. Theo. vol. 21,
no 3 et 4, pp. 341-371 et 379-417.
Chemillier M. (1990a). Languages musicaux et automates: la rationalite
du langage seriel. Actes du Colloque, "Structures musicales et assistance
informatique", MIM, 36 bd Pardigon, 13004 Marseille.
Chemillier M. (1990b). Structure et methode algebriques en informatique
musicale, these, Universite Paris 7.
Chemillier M. (1990c). Solfege, Commutation Pertielle et Automates de
Contrepoint. Mathematiques et Sciences Humaines, tomo 110, pp. 5-25.
Chemillier M. (1992). Aspects Mathematiques des Applications en Informatique Musicale des Automates Finis. Expose au Seminaire Logique &
Algorithmique.

109

Chemillier M. (1999a). Grammaires, automates et musique, F. Pachet

(ed.), Informatique musicale, Hermes.
Chemillier M. (1999b). Generateurs musicaux et singularities JIM99, pp.
167-178.
Chemillier M., Timis D. (1988). Toward a theory of formal musical languages. Proc. of the ICMC, Cologne, pp. 175-183.
Conklin D., Witten I. (1995). Multiple Viewpoint Systems for the Music
Prediction. Journal of New Music Research, 24, 51-73.
Culik II K., Fris I. (1995). Weighted Finite Transducer in Image Processing, Discrete Applied Mathematics, 58, pp. 223-237.
Dershowitz N., Jouannaud J. (1990). Rewriting Systems. In Handbook of
Theoretical Computer Science, pp. 243-320, Elsevier Publishers.
Dowling W.J. (1971). Recognition of inversions of Melodies and Melodic
Contours. Perception and Psychophysics. 9.3B:348-49.
Dowling W.J., Fujitani D. (1971). Contour, Interval, and Pitch Recognition in Memory for Melodies. The Journal of the Acoustical Society of
America 49.2 pp.524-31.
Dowling, W.J. (1978). Scale and Contour: Two Components of a Theory
of Memory for Melodies. Phychological Reports, 85.4: 341-54.
Edworthy J. (1985). Interval and Contour in Melody Processing. Music
Perception 2.3:375-88.
Eilenberg, S. (1974). Automata, Languages and Machines, vol. A, Academic Press.
Fliess, M. (1974). Matrices de Hankel, J. Math. Press Appl. 53, pp. 197222.
Fliess, M. (1975). Series rationnelles positives et processus stochastiques. Annales de lInstitut Henki Poincare, Section B-Vol. XI, no 1,
pp. 1-21.
Friedmann, M. (1985). A Methology for the Discussion of Contour: Its
Application to Schoenbergs Music. Journal of Music Theory 29.2: 22348.
Forte A. (1973). The Structure of Atonal Music, New Haven, CT: Yale
University Press.

110

Giammarresi D., Restivo A. (1997). TwoDimensional Languages, Handbook of Formal Languages, Vol. 3 Beyond Words, 215-267, G. Rozenberg
A. Salomaa Eds, Springer.
Hiller L. (1959). Experimental Music Composition with an Electronic
Computer, New York, MacGraw Hill.
Honingh, A.K. (2006). The Origin and Well-Formedness of Tonal Pitch
Structures. Ph.D. Thesis, University of Amsterdam.
Inoue K., Nakamara A. (1977). Some Properties of Two-Dimensional Online Tessellation Acceptors, Information Sciences, Vol. 13, 95-12.
Koliski, M (1965). The General Direction of Melodic Movement. Ethnomusicology 3.3, pp. 240-64.
Lerdahl, F. and Jackendoff, R. (1983). A Generative Theory of Tonal Music. MIT Press.
Lewin D. (1997). Fortes Interval Vector, My Interval Function and Regeners Common-Note Function, Journal of Music Theory 21.2:194-237.
Madsen, S.T., Jorgensen, M.E. (2003). Automatic Discovery of Parallelism
and Hierarchy in Music. Masters Thesis, University of Aarhus, Denmark.
Marvin E.W. (1989). A Generalized Theory of Musical Contour: Its Application to Melodic and Rhythmic Analysis of Non-Tonal Music and its
Perceptual and Pedagogical Implications. PhD dissertation, University of
Rochester.
Marvin, W.E. (1991). The Perception of Rhythm in Non-Tonal Music:
Rhythmic Contours in the Music of Edgard Varese. Music theory Spectrum 13.1: 61-78.
Marvin E.W., Laprade P. (1987). Relating Musical Contours. Extensions
of a Theory for Contour. Journal of Music Theory 31, no 2, pp.225-67.
Mazzola G. (1985). Gruppen und Kategorien in der MusikQ Entwurfeiner
mathematischen Musiktheorie. Berlin: Heldermann.
Mazzola G. (2002). The topos of Music Geometric Logic of Consepts, Theory and Performance. Basel: Birkhauser.
Mazzola, G. (2002). The Topos of Music Basel: Birkhauser.
Mohri M. (1997). Finite-State Transducers in Language and Speech Processing. Computational Linguistics, 23(2), pp. 269-311.

111

Mohri M., Pereira F., Riley M. (2000). The Desigh Principles of a Weighted
Finite-State Transducer Library, Theoretical Computer Science, 231, pp.
17-32.
Mohri M., Pereira F., Riley M. (2002). Weighted Finite-State Transducers
in Speech Recognition, Computer Speech and Language, vol. 16, no. 1,
pp. 69-88.
Mohri M., Moreno P., Weinstein E. (2008). Efficient and Robust Music
Identification with Weighted Finite-State Transducers, IEEE Transactions on Audio, Speech, and Language Processing, Vol. X, pp. 1-12.
Moore C., Crutchfield J. (2000). Quantum automata and quantum grammars. Theoretical Computer Science, Vol.237, Issues 1-2, pp.275-306.
Moriss R. (1987). Composition with Pitch-Classes: A Theory of Compositional Design. New Haven and London: Yale University Press.
Moriss R. (1993). New directions in the theory and analysis of musical
contours. Music Theory Spectrum, 15, No2: 205-28.
Pereira F., Riley M., Sproat R. (1994). Weighted rational transductions
and their application to human language processing, in ARPA Workshop
on Human Language Technology.
Polansky, L. (1996). Morphological Metrics. Journal of New Music Research, vol. 25: 289-368.
Prusinkiewicz P. (1986). Graphical Applications of L-Systems. Proc. of
Graphics Interface 86. pp.247-253.
Prusinkiewicz P., Lindermayer A. (1991). The Algorithmic Beauty of
Plants (The Virtual Laboratory).
Quinn, I. (1997). Fuzzy Extensions to the Theory of Contour. Music
Theory Spectrum 19/2, pp. 232-263. Berkeley: University of California
Press.
Rabiner, LR. (1989). A tutorial on hidden Markov models and selected
applications in speech recognition. Proceedings of the IEEE.
Rozenberg G., Salomaa A. (1980). The Mathematical Theory of L-Systems.
Academic Press.
Schmuckler M. (1999). Testing of Melodic Contour Similarity. Music Perception 16.3:295-326.

112

Schoenberg A. (1967). Fundamentals of Musical Composition, eds. Gerald Strang and Leonard Stein. (London: Faber & Faber).
Schoenberg A. (1978). Theory of Harmony. University of California Press,
Berkeley and Los Angeles.
Schutzenberger,

M.P. (1961). On the definition of a family of automata,

Information and Control 4, pp. 245-270.
Schwanauer S. (1993). Levitt D. (eds). Machine Models of Music. MIT
Press.
Seeger Ch. (1960). On the Moods of a Musical Logic. Journal of the American Musicological Society 13.1:224-61.
Tenney, Polansky (1980). Temporal Gestalt Perception in Music. Journal
of Music Theory 24, pp. 205-41.
Toch E. (1948). The Shaping Forces in Music: An Inquiry into the Nature
of Harmony, Melody, Counterpoint, Form. (New York: Criterion Music
Corp.)
Weinstein E., Moreno P. (2007). Music Identification with Weighted
Finite-State Transducers, Proceedings of ICASSP, Honolulu, Hawaii.
Xenakis I. (1961). La Musique Stochastique: e lements sur les procedes
probabiliste de composition musicale. Revue dEsthetique, Vol. 14, No
4-5.
Xenakis I. (1963). Musiques Formelles. Richard-Masse.

1.
X . x X x
/ X
x X .

, :

X = {1, 2, 3}, Y = {1, a, x, 2, y} .

X
x P:

X = { x / x P}.
N Z
, ,

N = {0, 1, 2, 3, . . . }, Z = {. . . , 2, 1, 0, 1, 2, . . . }
R .
X Y
X Y, X Y.

X Y , X = Y,
X Y Y X , .

114

,
. .
P( X ) X ,
, X . X =
{1, 2, 3}, P(X ) :

, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}.
.
X Y, X Y,
X Y.

X Y = { x / x X x Y }.

.. X = {1, 2, 3, 4, 5} Y = {3, 5, 6, 7}

X Y = {3, 5}.
X Y X Y = ,
.
X Y, X Y,
X Y.

X Y = { x / x X x Y }.

X Y = {1, 2, 3, 4, 5, 6, 7}.

.
( ) X1 , . . . , Xn X ,
, ""
X , .

115

Xi X j = i 6= j
X = X1 X n .

X1 = {1, 3, 5}, X2 = {2, 4} X3 = {6}

X = {1, 2, 3, 4, 5, 6}.

.
.
, X Y, X Y, ( x, y),
x X y Y,

X Y = {( x, y) / x X y Y }.

{1, 2} {a, , } = {(1, a), (1, ), (1, ), (2, a), (2, ), (2, )}.

. X1 , . . . , Xn
X1 Xn , n- ( x1 , . . . , xn )
x1 X1 , ..., xn
Xn .

2.
X Y. X Y,
f x X
f ( x ) Y, f : X Y.

f
x

f (x)

116

f x X
f

y Y x 7
y.
f : X Y

1 1, X
Y,
x1 6= x2 = f ( x1 ) 6= f ( x2 ),
, X f
Y.
f : X Y g : Y Z
g f : X Z ( g f )( x ) =
g( f ( x )), x X .

3.
E, R E E.
( x, y) R x Ry " x
R y". R
:
1. , x E, x R x,
2. , x Ry, yR x,
3. , x Ry yRz, xRz.
x E,

[ x ]R = {y / y E, yR x }
x R.
R E :
1. x Ry, [ x ]R = [y]R , , .
2. R X .

X/R,

X/R = {[ xR ] / x X }

117

4.

X . X X :

x1 x2 x

x1 x2 x y1 y2 y
,

= x1 = y1 , x2 = y2 , . . . , x = y .

, . .

X , X ,

X = { x1 x2 x / xi X, N } {}.
X X .
v = x1 x2 x w = y1 y2 y
X ,
w v:

vw = x1 x2 x y1 y2 y .
. X = { a, b}
v = aa w = bbb vw = aabbb wv = bbbaa.
vw 6= wv.

1. , v, w, u
X

(vw)u = v(wu).
2. v X

v = v = v
.

118

w |w|,
.

aaba, bba, b
1, 4,3 1, | aaba| = 4,
|bba| = 3, |b| = 1.

|| = 0,
|vw| = |v| + |w|
a X , w X
|w| a a
w. .. w = abbabaabb, |w| a = 4 |w|b = 5.

|vw| a = |v| a + |w| a

w X -
:

w0 = , w1 = w, w2 = ww, . . . , wk = ww w (k ).

w w = w+ , (w ) = w .
.
, X = { a, b, c},

aaabbcccaa

a3 b2 c 3 a2

bbbbbbbccccc

b7 c 5 .
w X n N

|wn | = n |w|

119

5.
M (m1 , m2 )
M M
m1 m2 .
m1 , m2 , m3 M,

m1 (m2 m3 ) = (m1 m2 )m3 .

e M ,

em = m = me
m M.
M
. :
1. N
0.
2. N {0} 1.
3. N max,
( a, )
.
X
.
( M, , e) m M m0 M

mm0 = e = m0 m.

.
( M, , e) ( N, , f ) 
e f . h : M N ,
, :

h(m1 m2 ) = h(m1 )h(m2 ), m1 , m2 M

h(e ) = f
h

, h

120

, h 1-1
M N
h,
h:M~
N.
h :
X M, X ,
M.
1. w X
|w|, X (N, +, 0)

|ww0 | = |w| + |w0 | || = 0.

, X ( M, , e) ,
f : X M f : X M
x1 x2 xk X
f ( x1 ) f ( x2 ) f ( xk ) M,

f( x1 x2 xk ) = f ( x1 ) f ( x2 ) f ( xk ),
f() = e.
f

u = x1 xk v = xk+1 x
X

f(uv) = f( x1 xk xk+1 x )
= f ( x1 ) f ( x k ) f ( x k +1 ) f ( x )
= f(u) f(v)
f .
2. Mat( X pitch )
X pitch

a11

A = ...
am1

a1n

..
. =

amn

r1 ( A )
..
.

rm ( A)

ri ( A) i- A.
.

121

 Mat( X pitch ) .

r 1 ( A )r 1 ( B )

..

r 1 ( A )r k ( B )
r1 ( B )
r1 ( A )

.. ..
..

.  . =
.

r ( A )r ( B )
rk ( B)
rm ( A)
m

..

.
r m ( A )r k ( B )

(1 1)
E = (e) e.

 
b]
c]]
c]
H (0 ) = c , H (1 ) =
, H (2 ) = d ,
d[
d[[
e[[

 
a]]
d]

b
, . . . , H (11) =
H (3 ) =
e[
c[

Mat( X pitch ), .
k 7 H (k), k Z12

H : Z12
Mat(X pitch ), H (k1 km ) = H (k1 )   H (km )
Z12
Im( H ) ( H ). ( Im( H ), , E)
.
Im( H )
- .
H
(integer file).

( M, , e)
R. R

m1 Rm2 m10 Rm20 m1 m10 R m2 m20 .

122

""
[m1 ]R [m2 ]R

[m1 ]R [m2 ]R [m1 m2 ]R .

M/R
([m1 ]R , [m2 ]R ) [m1 m2 ]R . M/R
M R.
f : ( M, , e) ( M 0 , 0 , e0 ).
f

m1 f m2 f (m1 ) = f (m2 )
M/ f M 0 .
[m] 7 f (m). .
. f : ( M, , e) ( M 0 , 0 , e0 )

M/ f ~
M0 .

, . A

( x, y) 7 x y, ( x, y) 7 x  y
A , 

x  (y z) = x  y + x  z, ( x y)  z = x  z y  z, x, y, z A.

SUMMARY

The present thesis is a contribution to the computability of musical languages and musical functions by means of automata and sequential machines.
It is composed of four chapters and one appendix. In chapter 1 the
basic notions of Music are introduced in a formal way.
Consider the musical alphabet of accidentals Xacc = {], [} and the
extended alphabet
[

{c(k), c(k)], d(k), d(k)], e(k ), f (k),

X NOTE =

k Z

f (k)], g(k), g(k)], a(k ), a(k)], b(k )}.

The musical strings are all the strings over the alphabet X NOTE Xacc not
starting by an accidental. They constitute a monoid M MUS . We say that
the musical strings s, s0 are diatonically equivalent, notation s D s0 , if s0
results from s by applying finitely many times next the identities.

][ = , [] = , ( the empty string )



c(k)]] = d(k), d(k)]] = e(k), e(k)] = f (k),

f (k)]] = g(k),
g(k)]] = a(k), a(k)]] = b(k), b(k)] = c(k + 1)

It is the most economical system that any other musical identity results
from. Actually D is a congruence on the monoid M MUS and so the
quotient MD = M MUS / D is converted into a monoid, that we call
diatonic monoid.
Now, let Xnote = {c, d, e, f , g, a, b} be the c-major scale alphabet and
Mmus be the monoid of musical strings over X NOTE Xacc . We introduce
the monoid Md = Mmus / d , where d is the congruence generated by
the previous relations without octave indices. In order to compare the
monoids MD and Md we use the Babbitt morphism B : M MUS Mmus
which deletes octave indices from musical strings. It is shown that Md is
isomorphic to the quotient monoid MD / B , where B is the congruence
induced by B. In the sequel the notions of interval, scale and chord are
formally described.

124

SUMMARY

An automaton is a finite directed graph A whose vertices are its states

and whose edges (transitions of A) are of the form

labelled over the input alphabet X . Initial and terminal states are specified. A succesful path is a sequence of successive transitions starting from
an initial state and ending to a terminal state.
An input string is recognized by A if it is the label of a successful path
and the behaviour of A is the language of all strings recognized by A.
A monophonic melody is a string of musical points i.e. of pairs ( x, d)
consisting of a note x and its duration d.
To write a melody s in meter , means to insert bars along s

s1 | s2 | | s k 1 | s k |
so that

duration(s1 ) = = duration(sk ) =

Our scope in chapter 2 is to construct an automaton, actually the minimal

one from state point of view, which decides whether a monophonic melody
can be written in a specific meter .
Classical contours i.e. "up and down moves" of various music parameters, are primitive tools for analysing music texts. They give information about the flow complexity and perception of a music piece, Dowling
(1978), Friedmann (1985), Marvin (1991), Morris (1993), Polansky (1996),
Bor (2006).
Actually, a contour c can be viewed as a function assigning a number
c( xy) to each pair of music entities x, y from a certain alphabet X . More
precisely, to any string w = x1 x2 xk over X , a k k-matrix Mc (w) is
associated with entries c( xi x j ) and the traditional contour functions are
obtained by summing up all the entries of some parts of this matrix.
Our aim, in this chapter, is to automatically compute such functions
by means of weighted automata. For this, we utilize a known construction
of the minimal weighted automaton computing a given string function.
Such automata are displayed for the functions A, D, E which count the
numbers of ascending, descending or horizontal moves of a music string
respectively.
Furthermore, we indicate how other music processes such as pitch
spelling can fit in the above setup. We provide the minimal weighted

125

SUMMARY

automaton whose behaviour is the function which measures deviation

from normal spelling.
Polanskys general combinatorial form is obtained by summing up all
the entries above the principal diagonal of the contour matrix Mc (w) and
its minimal automaton is constructed. The sum of all entries of Mc (w) is
the compactness of the music string w, which measures how close to each
other are the notes of w, Honingh (2006), and the automatic computation
of the resulting music function is also achieved.
Sequential machines constitute the simplest machine model computing functions which assign strings from an input alphabet to strings of an
output alphabet. Such functions are frequently encountered in Music.
A sequential machine M can be depicted by a directed graph whose
vertices are the states of M and whose transitions are of the form

/u

q0

meaning that if M is in state q and is fed with the input letter then it goes
to state q0 and outputs the string u. In addition the model is deterministic.
This means that for any input string 1 k , there is a unique path

1 /u1

q1

qk1

k /uk

qk

and the emitted string is u1 uk (i denoting the single initial state).

Functions computed by such systems are called sequential and they
have the fundamental property to preserve initial segments.
Our aim in the present chapter is to construct the minimal sequential
machines computing the following fundamental music processes:

Schoenbergs elementary transformations (transposition, inversion,

etc.), Schoenberg (1978),

the classical contour function (which to any musical string w corresponds the string of 1s, 1s or 0s according to the wave of w moves
upwards, downwards or in the same level, with respect to a certain
musical parameter), as well as its refinements, Morris (1993), Marvin
(1991),

the Morris maxima and minima functions, Morris (1993), Bor (2006),
the function which to any monophonic melody corresponds its largest
initial segment that may be written in a specified meter .

126

SUMMARY

In the Appendix we present some basic notation and facts that we use
throughout this thesis.