An invariant establishes correctness only with its proof obligations.
Key knowledge
A loop proof establishes an invariant initially, preserves it through each guarded iteration, and uses it with the false guard to derive the postcondition. Total correctness also requires termination, for example a nonnegative integer variant that strictly decreases.
Conditions and scope
The precondition must imply initialization and the body must satisfy preservation.
Preservation alone proves neither the required output nor termination.
Sources · 1
References
Sources retain their recorded scope. A source link alone does not establish verification of every statement.
A loop proof establishes an invariant initially, preserves it through each guarded iteration, and uses it with the false guard to derive the postcondition. Total correctness also requires termination, for example a nonnegative integer variant that strictly decreases.
Dynamic programming states subproblems and recurrences, checks an acyclic dependency order and base cases, and evaluates each needed subproblem once by memoization or bottom-up order. Total work sums the nonrecursive work over evaluated states.
A directed network flow respects nonnegative capacities and conserves flow at vertices other than source s and sink t. Residual capacities allow unused forward flow and undoing existing flow. A feasible flow is maximum exactly when no residual s–t path exists, equivalently when its value equals the capacity of some s–t cut.
For a finite CFG, chart Iⱼ stores dotted productions [A→β·γ,k], where k is the starting position. Predict every production of the next nonterminal, scan matching terminals, and complete finished nonterminals into waiting items at their start positions. Close prediction/completion under repeated application. Accept length-n input iff [S′→S·,0]∈Iₙ.
Represent nonnegative integer keys with d base-B digits and stably sort each digit from least to most significant. After each pass the processed suffix is ordered, giving total O(d(n+B)) time with counting-sort passes. Choosing B=n makes bounded nᶜ keys linear-time for fixed c.
Sequential consistency presents operations in one order preserving each thread's program order. The C++ concurrency design distinguishes synchronization/atomic operations from conflicting unsynchronized ordinary accesses. In its simpler model with default sequentially consistent atomics, data-race-free programs receive sequentially consistent behavior. Relaxed or acquire/release atomics can be free of ordinary data races without providing a single sequentially consistent global execution; their ordering requires separate memory-model reasoning.
Shared-state invariants require reasoning across interleavings.
In the stated Python model, a sequence runs in order unless control is redirected. An if/elif/else statement selects the first true branch, or its else branch if none is true. A while statement tests before each iteration and repeats its body while the test remains true.
While-loop execution supplies the steps to which an invariant proof applies.