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.
A finite trellis with tied maxima and an unreachable high-score state
Example
Take , vertex layers , , and . Set and . The only layer-2 edges are and , each of weight . The layer-3 edges are and , each of weight , and of weight . The vertex order in layer 2 is .
Columns in the diagram are layers and arrow labels are multiplicative edge weights. The dashed vertex has no incoming edge, so it is unreachable. The proof below uses the explicit edge list and scores, not the drawing.
\begin{tikzpicture}[>=stealth]
\node[circle,draw] (s) at (0,0) {$s$};
\node[circle,draw] (a) at (2,1) {$a$};
\node[circle,draw] (b) at (2,0) {$b$};
\node[circle,draw,dashed] (c) at (2,-1) {$c$};
\node[circle,draw] (t) at (4,0) {$t$};
\draw[->] (s) -- node[above] {$2$} (a);
\draw[->] (s) -- node[above] {$2$} (b);
\draw[->] (a) -- node[above] {$3$} (t);
\draw[->] (b) -- node[below] {$3$} (t);
\draw[->] (c) -- node[below] {$100$} (t);
\end{tikzpicture}
Facts & Assumptions
Given: The weighted trellis and vertex order specified in the Example.
Finite weighted trellises: A path must start with positive initial weight, follow allowed edges through every layer, and end with positive terminal weight; its score is the product of these weights.
Max-product Viterbi decoding on a finite trellis: Viterbi computes the maximum prefix products, stores a maximizing predecessor for each positive value, then chooses a maximum terminal product and follows the backpointers.
Finite-trellis Viterbi decoding returns a maximum-score path: If a path exists, the algorithm returns a path of maximum score.
Verification
Any path must leave for or , since these are the only layer-2 edges. From either state it must go to . Thus the complete path set is and , each with score . There is no path through because no edge enters , despite its outgoing edge of weight .
The prefix values are , , and . Therefore . The stated order selects predecessor on the tie, so traceback returns with maximum score , as [F3] also guarantees.
Depends on
Used by
Nothing in the library uses this result yet.
Dependency tree · two levels
4 results within two dependency steps 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)