Assigning meanings to programs.¶
Floyd, R. W. (1967). Assigning meanings to programs. Mathematical Aspects of Computer Science, 19, 19-32.
Cited by¶
7 citations across 7 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)
- … essentially equivalent measure-based termination argument. 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.
- … essentially equivalent measure-based termination argument. 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.
Verification¶
This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. 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