Alphabeta Math
ExampleConstruction: AI-generatedVerification: 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.

A finite trellis with tied maxima and an unreachable high-score state

Example

Take T=3, vertex layers V1={s}, V2={a,b,c}, and V3={t}. Set α(s)=1 and β(t)=1. The only layer-2 edges are s→a and s→b, each of weight 2. The layer-3 edges are a→t and b→t, each of weight 3, and c→t of weight 100. The vertex order in layer 2 is a<b<c.

Columns in the diagram are layers and arrow labels are multiplicative edge weights. The dashed vertex c 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.

[F1]

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.

[F2]

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.

[F3]

Finite-trellis Viterbi decoding returns a maximum-score path: If a path exists, the algorithm returns a path of maximum score.

Verification

1.1givenF1algebra

Any path must leave s for a or b, since these are the only layer-2 edges. From either state it must go to t. Thus the complete path set is (s,a,t) and (s,b,t), each with score 1⋅2⋅3⋅1=6. There is no path through c because no edge enters c, despite its outgoing edge of weight 100.

2.1givenF2F3step 1.1algebra∎

The prefix values are D1(s)=1, D2(a)=D2(b)=2, and D2(c)=0. Therefore D3(t)=max⁡{2⋅3,2⋅3,0⋅100}=6. The stated order selects predecessor a on the tie, so traceback returns (s,a,t) with maximum score 6, 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