Assigning meanings to programs.¶
Floyd, R. W. (1967). Assigning meanings to programs. Mathematical Aspects of Computer Science, 19, 19-32.
Cited by¶
8 citations across 8 artifacts.
Each citation links to the sentence it supports in the citing article.
Primes¶
- Algorithm
- A common failure is assuming termination without formal verification, leading to infinite loops on certain inputs
This sourceIntroduces the inductive-assertions method for partial correctness and the well-founded-ordering method that converts termination claims into well-founded-descent proofs.
- A common failure is assuming termination without formal verification, leading to infinite loops on certain inputs
- Constraint
- … Analysis* consolidated the theory of convex constraints and the duality between feasible sets and supporting hyperplanes; Montanari's 1974 formalization and Mackworth's 1977 arc-consistency algorithms founded constraint-satisfaction as a distinct computer-science subfield; Floyd's 1967 "Assigning Meanings to Programs"
This sourceIntroduces the variant-function discipline that converts program-termination claims into well-founded-descent proofs.
- … Analysis* consolidated the theory of convex constraints and the duality between feasible sets and supporting hyperplanes; Montanari's 1974 formalization and Mackworth's 1977 arc-consistency algorithms founded constraint-satisfaction as a distinct computer-science subfield; Floyd's 1967 "Assigning Meanings to Programs"
- Invariance
- … is the mechanism by which symmetries generate conservation laws (Noether's theorem gives the continuous-group version — each continuous symmetry of the action corresponds to a conserved quantity), topological invariants (genus, Euler characteristic, homotopy class) classify spaces up to deformation, loop invariants
This sourceIntroduces the variant-function discipline that converts program-termination claims into well-founded-descent proofs.
- … is the mechanism by which symmetries generate conservation laws (Noether's theorem gives the continuous-group version — each continuous symmetry of the action corresponds to a conserved quantity), topological invariants (genus, Euler characteristic, homotopy class) classify spaces up to deformation, loop invariants
- Iteration
- Meta-Symbolic Reflection
- Listed in the references but not attached to a specific claim.
- Recursion
- A common failure is plausible-looking recursive definitions that do not terminate because the "decreasing" measure does not decrease on every path
This sourceIntroduces the variant-function discipline that converts program-termination claims into well-founded-descent proofs.
- A common failure is plausible-looking recursive definitions that do not terminate because the "decreasing" measure does not decrease on every path
- Well-Foundedness (Well-Ordering)
- Loops, recursions, proof-search procedures, rewrite systems, constraint-solving algorithms, and dataflow-analysis fixpoint computations all prove termination by exhibiting a well-founded "variant" or "measure" that the process strictly decreases at every step.
This sourceIntroduces the variant-function discipline that converts program-termination claims into well-founded-descent proofs.
- Loops, recursions, proof-search procedures, rewrite systems, constraint-solving algorithms, and dataflow-analysis fixpoint computations all prove termination by exhibiting a well-founded "variant" or "measure" that the process strictly decreases at every step.
Mechanisms¶
- Termination & Totality Proof Review
- Termination itself is best shown the disciplined way, by a well-founded ranking measure
This sourceA strictly decreasing well-founded ranking proves that execution terminates; correctness of the resulting state requires a separate proof obligation.
- Termination itself is best shown the disciplined way, by a well-founded ranking measure
Verification¶
Does it exist? Not checked yet. This entry carries no identifier to resolve. It was extracted from the citation as written in the article, normalized, and deduplicated against the rest of the registry.
Does it back the claim? Not recorded. Neither this nor any other of the 8 citations of this work carries a recorded support check.
Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.
See how references were verified.
Links previously used in the corpus¶
Before the registry existed this work was also linked 1 other way.
Registry ID ref:942ebd2bc8c0 · see in the full table