LemmaStatement: AI-adaptedProof: AI-generatedPipeline-generatedprecheck passjudge pass (gpt-6-luna)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

The optimal-prefix recurrence for a finite trellis

Statement

For a finite weighted trellis with $T = 0$ , the unique prefix path through no layers is empty and has score $1$ . For $T \geq 1$ , define $D_{1} (v) = α (v)$ and, for $2 \leq t \leq T$ , $D_{t} (v) = \max ({D_{t - 1} (u) w_{t} (u, v) : (u, v) \in E_{t}} \cup {0}) .$ Then $D_{t} (v)$ is the maximum score of a prefix path ending at $v$ ; if no such prefix exists, $D_{t} (v) = 0$ .

Facts & Assumptions

Given: A finite weighted trellis as in the Definition.

[F1]

Finite weighted trellises: For $T = 0$ , the unique path through no layers is empty with score $1$ . For $T \geq 1$ , a prefix path through layer $t$ starts with positive initial weight and follows an allowed edge at each preceding layer; its score through $t$ is the initial weight times the edge weights.

[A1]

For an induction step at layer $t \geq 2$ , assume that $D_{t - 1} (u)$ is the maximum score of a prefix path ending at each $u \in V_{t - 1}$ , and is zero exactly when no such prefix path exists.

Proof

1.1givenF1algebra

If $T = 0$ , the unique prefix path through no layers is empty and has score $1$ . For $T \geq 1$ , at layer $1$ the only prefix ending at $v$ is the one-vertex prefix. It exists exactly when $α (v) > 0$ , and then has score $α (v) = D_{1} (v)$ ; when $α (v) = 0$ there is no prefix and $D_{1} (v) = 0$ .

1.2givenF1A1algebra

Fix $t \geq 2$ and $v \in V_{t}$ . Every prefix ending at $v$ has a predecessor $u$ with $(u, v) \in E_{t}$ and is obtained by appending that edge to a prefix ending at $u$ . Its score is the predecessor-prefix score multiplied by the positive weight $w_{t} (u, v)$ . By [A1], the best such extension through each $u$ has score $D_{t - 1} (u) w_{t} (u, v)$ ; if no predecessor prefix exists this value is zero. Taking the maximum over the finite predecessor set, with zero when it is empty, gives exactly the stated recurrence.

2.1step 1.1step 1.2induction∎

The $T = 0$ case and the base case in step 1.1, together with the induction step in step 1.2, prove the claim for every trellis length and every layer.

Depends on

Finite weighted trellises

Used by

Dependency tree · one level

1 result within one dependency step of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Manolis Kellis, 6.096 Algorithms for Computational Biology, Lecture 7: Gene Finding and HMMs, MIT OpenCourseWare (Spring 2005) (standard reference, not scraped)
Stanford CS262, Lecture 7: Hidden Markov Models (standard reference, not scraped)