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.
Shortest acceptance versus clocked all-branch halting
Example
Let N have distinct states . For each scanned symbol a, its initial options are and . At the only option writes the scanned symbol unchanged, moves right and stays in . Thus on every binary input it has a one-step accepting branch and a diverging branch. A one-transition exact clock converts its cutoff to an all-branch-halting acceptor.
Facts & Assumptions
Given: The displayed finite machine, on any input x including the empty word.
Shortest acceptance takes a minimum and may coexist with divergence; an inclusive exact-clock cutoff preserves precisely the timely accepting branches (Nondeterministic acceptance time and exact clocks).
Cutoff scheduling gives a bounded all-branch machine for the cutoff language (Clocks, cutoffs, and finite unions preserve nondeterministic time bounds).
Verification
On either a bit or the blank scanned for empty x, N's first option enters the accepting state in one transition. Its start state is not accepting, so no length-zero acceptance exists and . On the other branch it reaches cell one in state after the first transition and cell t in that state after t transitions, for every . Hence this branch never halts and N has no finite all-branch running-time function. Its language is nevertheless all binary words.
Take a clock whose first transition on every symbol enters its halt state, so T(n)=1 exactly. Here its transition can be incorporated directly into the finite control: make the same two initial choices as N, but replace the target by rejection. The resulting machine C has precisely two one-step branches, one accepting and one rejecting, on every input. Thus every branch halts after one step and . This is an explicit optimized instance of the inclusive product-clock construction of F2, with no copying needed.
If one tests the cutoff zero instead, its language is empty because the initial state is nonaccepting. A decider can recognize it by a single rejecting transition, but it is not a zero-transition physical exact clock. At cutoff one, testing acceptance before expiry matters: rejecting immediately at the clock's last transition without testing N's simultaneous acceptance would incorrectly remove all inputs. C keeps that acceptance, as its two explicit branches show. This separates raw shortest and worst-branch times while verifying the correct clocked language and endpoints without AC.
Depends on
Used by
Nothing in the library uses this result yet.
Dependency tree · two levels
8 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
- Seiferas, Fischer, and Meyer, pp. 147-149 (standard reference, not scraped)