Mazzola, Guerino / Noll, Thomas / Lluis-Puebla, Emilio: Perspectives in Mathematical and Computational Music Theory

as special case of our framework. The chord sequence would then play the role of the observations being made and the pathway in the harmonic space would be interpreted as a hidden stochastic process. However, the Viterbi algorithm is just based on the assumption that the evaluation of pathways can be obtained step by step in terms of an order-preserving evaluation of partial pathways. This assumption does not presuppose a stochastic interpretation.

Consider a chord sequence $S = (Xk)k=0,...,n$ and associated harmonic paths $H = (Hk)k=0,...,n$ to be evaluated as candidates for best harmonic analyses $S |\H$ . We sketch a very general situation in which the Viterbi algorithm works. For each index $k = 1,...,n$ we consider

a function $transVal : [0, oo ) × HARM × HARM --> [0, oo ) k$ evaluating path-continuing transitions $(v,H ~ H ) k-1 k$ which depend only on the value $v$ of the previous path and the two loci $H k-1$ and $H k$ of that transition,
a function $locusValk : [0, oo ) × HARM --> [0, oo )$ evaluating path-specific choices $(v,Hk)$ which depend only on the values $v$ of the previous paths (leading to $Hk$ ) and the concrete choice of $Hk$ at index $k$ , which of course includes dependence upon the chord $Xk$ at index $k$ .

Remark 3 Both functions $transV al k$ and $locusV al k$ may depend upon $k$ , i.e. they may depend upon the chord sequence $S$ . Within our framework $locusVal k$ in fact substantially depends upon $k$ , because it encodes the significations $X |\H k k$ , but $transVal k$ does not depend upon $k$ . The investigation of proper dyadic significations would require the definition of variable functions $transV al k$ .

As an essential presupposition we need that $transValk$ and $locusValk$ are both order-preserving in their first argument, whenever they do not vanish. Further we assume them to be zero-preserving. This latter condition just means that zero values stand for discarded transitions or loci which should not occur at all in any analysis, i.e. $transV alk(0,Hk- 1 ~ Hk) = 0$ and $locusV alk(0,Hk) = 0$ for all $Hk- 1,Hk (- HARM$ . According to the first condition, does $v1 < v2$ imply

transVal (v ,H ~ H ) < transVal (v ,H ~ H ), k 1 k- 1 k wheneverk 2transk-V 1al(v k,H ~ H ) > 0 locusV al(v ,H ) < locusV al(v ,H ), k 2 k-1 k k 1 k whenevekr 2locuksV al(v ,H ) > 0 k 2 k

If we further consider an initial evaluation $eval0 : HARM --> [0, oo )$ we define the values $evalk((H0,...,Hk))$ of the increasing partial paths of $H$ as:

eval1((H0, H1)) = locusVal1( transVal1(eval0(H0), H0 ~ H1),H1) ... evalk((H0,...,Hk)) = locusValk( transValk(evalk-1(H0,...,Hk -1),Hk -1 ~ Hk),Hk)

Note, that the partial evaluation maps are order-preserving too. The total value of a path $H = (H0,...,Hn)$ is its last partial value, i.e. $eval(H) = evaln(H)$ . A best