- Atlas
- Computer Science
- Formal Methods
Formal Methods
Formal methods are the branch of software engineering that uses mathematical reasoning to establish what a program does.
12 frameworks, from 1967 to today · Software Engineering · Computer Science
- Axiomatic semantics 1967-Present
- Semantics 1967-Present
- Proof assistant 1970-Present
- Formal Specification and Refinement 1975-Present
- Abstract Interpretation 1977-Present
- Temporal and Modal Logics of Programs 1977-Present
- Process calculus 1978-Present
- Model Checking 1981-Present
- Lightweight Formal Methods 1996-Present
- Deductive Software Verification Tools 2000-Present
- SMT-Based Deductive Verification 2000-Present
- Runtime Verification 2001-Present
Overview
Formal methods are the branch of software engineering that uses mathematical reasoning to establish what a program does1. Instead of testing a system on some inputs and hoping the rest behave, a formal method treats a program or a design as a mathematical object and tries to prove a property of it—that it never divides by zero, that two processes never deadlock, that a protocol delivers every message exactly once1. The stakes are highest where failure is unacceptable or invisible: flight control, medical devices, security protocols, chip designs, railway signalling. The field's history is a long argument about whether such reasoning can be made practical, and the gradual, uneven answer that it can—for some systems, at some cost.
Logics for programs, 1940s–1960s
The intellectual root is the idea that a program is a piece of mathematics. Alan Turing had already shown in 1936 that a machine's behaviour could be described formally, but the first logic built specifically for programs came from John McCarthy. In 1963 he proposed using mathematical logic to prove that programs meet their specifications, and his 1967 paper on the "mathematical science of computation" framed programs as recursive functions. Around the same time, Robert Floyd published "Assigning Meanings to Programs" (1967), which introduced assertions: statements about the state of a program placed at points in its text. Floyd showed how to reason from one assertion to the next through each statement, so that a proof about a whole program could be assembled from local steps. This was the seed of axiomatic semantics—giving a program meaning by the logical rules its statements obey2.
Hoare logic and the verification dream, 1969–1970s
The decisive step was C. A. R. Hoare's 1969 paper "An Axiomatic Basis for Computer Programming."23 Hoare introduced what became known as the Hoare triple: {P} S {Q}, read as "if assertion P holds before statement S, then Q holds afterwards." Each kind of statement got a rule—assignment, sequencing, conditionals, loops—so that a program's correctness could be proved by applying rules mechanically. The loop rule required a loop invariant: a property true before and after every iteration, which the programmer must supply1. That requirement revealed the field's central difficulty: proofs need human insight, and the insight is often as hard as writing the program.
The 1970s were the era of ambitious program verification. Projects such as the Stanford Pascal Verifier and the work of Edsger Dijkstra, whose 1976 A Discipline of Programming recast programming as deriving a program from its specification via weakest preconditions (the weakest condition that guarantees a desired outcome), aimed to make verified software routine. They largely did not. Proofs were long, tools were fragile, and the gap between toy programs and real systems was enormous. The lesson, absorbed slowly, was that full functional verification of large programs by hand was impractical—but the ideas were sound and would return in better tools.
Semantics: giving languages a mathematical meaning, 1970s
Parallel to verification, a community asked a more basic question: what does a program mean? Formal semantics of programming languages supplied answers in three main styles. Operational semantics, developed by Gordon Plotkin in the early 1980s (building on earlier work), defines meaning by the steps a machine takes. Denotational semantics, associated with Christopher Strachey and Dana Scott in the late 1960s and 1970s, maps each program to a mathematical function, with Scott's domain theory providing the spaces in which recursive definitions make sense. Axiomatic semantics is the Hoare-style approach4. These gave later tools a rigorous foundation: a compiler or analyser could be reasoned about because the language itself had a definition. Robin Milner's 1970s work on the ML language and its operational semantics, and later his π-calculus, carried this tradition into practice.
Concurrency and temporal logic, 1977–1980s
Sequential programs were hard enough; concurrent ones were worse, because their behaviour depends on interleaving. Two lines of work addressed this. First, temporal and modal logics of programs: Amir Pnueli's 1977 paper "The Temporal Logic of Programs" proposed describing a concurrent system's requirements in temporal logic—logic with operators like "always" and "eventually"—so that properties such as "the system never deadlocks" or "every request is eventually answered" could be written as formulas15. Second, process algebras: Hoare's Communicating Sequential Processes (CSP, 1978) and Robin Milner's Calculus of Communicating Systems (CCS, early 1980s) modelled concurrent systems as collections of processes interacting through channels or handshakes, with algebraic laws for reasoning about them678. These gave concurrency a vocabulary and a calculus; they also set up the question of how to check that a real system satisfied a temporal formula.
Model checking: exhaustive search that worked, 1981–1990s
The answer came from model checking, introduced independently by Edmund Clarke and E. Allen Emerson (1981) and by Jean-Pierre Queille and Joseph Sifakis (1982). The idea: represent a system as a finite state transition graph—every possible state and every allowed move between states—and check a temporal-logic formula against it by exhaustive search1. For finite-state systems this is decidable and can be automated completely; no loop invariants, no human proof. The obstacle was size: the number of states grows exponentially with the number of components. The breakthrough was symbolic model checking, developed by Ken McMillan, Clarke and others in the early 1990s, which represented sets of states with binary decision diagrams and could handle systems with astronomically many states. Model checking became the field's great practical success, especially in hardware, where finite-state descriptions are natural. Intel, IBM and others adopted it for chip verification; the 2007 Turing Award went to Clarke, Emerson and Sifakis for the work1.
Abstract interpretation: reasoning about all inputs at once, 1977
Where model checking enumerates states, abstract interpretation reasons about programs by over-approximating their behaviour1. Introduced by Patrick and Radhia Cousot in 1977, it maps a program's concrete states onto a simpler abstract domain—say, intervals of integers—and computes what must hold in the abstract world. If the abstraction says "this variable is never zero here," that conclusion is sound for every concrete execution. The price is imprecision: the abstraction may report a possible error that cannot actually occur. Abstract interpretation became the basis of static analysers, notably the Astrée tool, which proved the absence of runtime errors in the flight-control software of the Airbus A380—a landmark demonstration that formal analysis could scale to industrial code.
Specification languages and refinement, 1980s–1990s
To prove anything, one needs a precise statement of what is wanted. Formal specification languages supplied it. Z, developed at Oxford in the late 1970s and 1980s, described systems in set theory and first-order logic; VDM, from Cliff Jones and colleagues in the 1970s, used a model-based style with pre- and postconditions. Later, the B method (Jean-Raymond Abrial, 1980s–1990s) and its successor Event-B supported refinement: starting from an abstract specification and stepping down through increasingly concrete designs, each step proved to preserve the abstract behaviour9. This correct-by-construction approach—build the system so that correctness is established as you go, rather than checked at the end—was used on real railway systems, including driverless metro lines in Paris9. The specification languages made the central trade-off explicit: precision costs effort, and the effort must be repaid by the assurance gained.
Interactive theorem proving, 1970s–present
For systems too complex or too infinite for automatic methods, interactive theorem provers let a human and a machine cooperate on a proof10. The lineage runs from Automath (Nicolaas de Bruijn, late 1960s) through the LCF family (Robin Milner, 1970s), which introduced the idea of a small trusted kernel that checks every proof step. Later systems—HOL, Isabelle, Coq, and more recently Lean—grew into large libraries of mathematics and program theory110. Their use in software includes the CompCert project (Xavier Leroy and colleagues, 2000s), a C compiler whose correctness—that it preserves the meaning of the source program—was proved in Coq. CompCert showed that a real, widely used tool could be verified end to end, and it is now used in safety-critical settings.
Lightweight formal methods and runtime verification, 1990s–2000s
The recurring complaint was cost. Lightweight formal methods answered it by applying formal techniques selectively: not proving a whole system correct, but using a model checker on a protocol design, or a type system or static analyser to catch a class of bugs1. The term, promoted by Daniel Jackson and others around the late 1990s, reframed formal methods as tools in a working engineer's kit rather than an all-or-nothing commitment. Jackson's Alloy tool, which searches for counterexamples to a specification within a bounded scope, is a representative example: it does not prove correctness, but it finds flaws cheaply111. Runtime verification, emerging in the early 2000s, took another route: instead of proving properties ahead of time, monitor a running system and check that it obeys a formal specification, raising an alarm when it does not12. This brought formal specifications into deployed systems where full verification was impossible.
The present
Today the field is less a single programme than a family of techniques at different costs and strengths. Model checking is standard in hardware and increasingly in software, aided by bounded variants and by SMT solvers—automated decision procedures for logical formulas over arithmetic, arrays and bit-vectors—that power tools like CBMC and the deductive verifiers descended from Hoare logic. Deductive verification tools such as Why3, Frama-C and Dafny let programmers write specifications and discharge proof obligations, partly automatically and partly with interactive help1. Abstract interpretation underpins commercial static analysers. Interactive provers verify compilers, operating-system kernels and cryptographic libraries1. The open questions are the old ones in sharper form: how to make specifications cheap enough to write, how to scale proofs to the systems industry actually builds, and how to combine the assurance of proof with the flexibility that changing software demands. The history's arc is from the conviction that programs could be proved right to the working knowledge of when and at what cost they can be.
References
- Formal methods (introduction, Verification, Automated proof, History, Applications, Interactive theorem proving, Semi-formal methods, Deductive program verification), Wikipedia
- Semantics (programming languages) (History), Wikipedia
- Hoare logic, Wikipedia
- Axiomatic semantics, Wikipedia
- Linear temporal logic, Wikipedia
- Communicating sequential processes, Wikipedia
- Process calculus (History), Wikipedia
- Calculus of communicating systems, Wikipedia
- B-Method (History, Event-B), Wikipedia
- Proof assistant (introduction, History), Wikipedia
- Alloy (specification language), Wikipedia
- Runtime verification (History and context), Wikipedia
The frameworks of Formal Methods
Each framework is a way of working the field has used: when it held, and the question it answers.
- 1967-Present
- 1967-Present
- 1970-Present
- 1975-Present
Formal Specification and Refinement
How do we state precisely what a system must do?
- 1977-Present
Abstract Interpretation
How can we reason about all inputs at once?
About Abstract Interpretation
In the late 1970s, formal methods faced a practical impasse. Hoare logic offered rigorous proofs of program correctness, but the manual effort required was prohibitive for all but the smallest programs. Formal specification languages like VDM and Z raised the level of abstraction to system design, but they did not automatically verify that an implementation matched its specification. What was needed was a way to extract useful, guaranteed-correct information about a program's runtime behavior automatically—without executing it and without the full cost of theorem proving. Abstract interpretation, formalized by Patrick Cousot and Radhia Cousot in 1977, provided exactly that: a theory of sound approximation that made static program analysis both principled and practical.At its core, abstract interpretation replaces the concrete, infinite set of possible program states with a finite, computable abstraction. The key intellectual move is to define a Galois connection between two worlds: a concrete domain (the actual semantics of the program) and an abstract domain (a simpler, finite representation). A concretization function maps abstract values back to the sets of concrete states they represent, while an abstraction function goes the other way. This pair of functions must form a Galois connection, ensuring that reasoning in the abstract domain is sound with respect to the concrete semantics.The curriculum for a first course in abstract interpretation typically proceeds through these clusters:- Foundations: Abstract domains and Galois connections. Students first learn how to define an abstract domain—a lattice of abstract values—and the pair of monotonic functions (abstraction and concretization) that relate it to the concrete domain. The monotonic function property ensures that the ordering in the abstract domain respects the ordering in the concrete domain.
- Abstract semantics and soundness. The concrete semantics of a program is given by a collecting semantics—the set of all possible states reachable at each program point. An abstract semantics is defined by replacing each concrete operation with an abstract transformer that operates on abstract values. The central theorem is soundness (over-approximation): the abstract semantics must produce a superset of the concrete reachable states, guaranteeing that no real behavior is missed (though false positives are possible).
- Fixpoint semantics and computation. The abstract semantics is defined as the least fixpoint of a system of equations over the abstract domain. Computing this fixpoint directly may not terminate if the abstract domain has infinite ascending chains. Widening operators accelerate convergence by jumping to a safe over-approximation, while narrowing operators refine the result after widening. Chaotic iteration is the standard algorithm for computing the fixpoint efficiently by iterating over program points in an order that respects control flow.
- Applications: Program invariants and static analysis. The output of abstract interpretation is a set of program invariants—properties that hold at every program point for all executions. These invariants are the basis for static analysis tools that detect bugs (e.g., division by zero, buffer overflows) or enable compiler optimizations (e.g., constant propagation, dead code elimination).
Abstract interpretation emerged directly from the limitations of earlier formal methods. Patrick Cousot and Radhia Cousot, both French computer scientists, introduced the framework in their 1977 paper "Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints." Their key insight was to unify a scattered set of ad-hoc program analysis techniques (like data-flow analysis and type inference) under a single mathematical theory based on lattice theory and fixpoint semantics. The Cousots showed that many existing analyses could be seen as instances of abstract interpretation with different abstract domains, and that the theory provided a systematic way to design new analyses and prove them correct.The framework coexisted with and complemented its peers. While Hoare logic (1969) and axiomatic semantics focused on deductive verification of code, abstract interpretation automated the discovery of invariants. Formal specification languages (VDM, Z, B Method) targeted design-time correctness, but abstract interpretation could analyze the final implementation. Model checking (emerging around 1981) explored state spaces exhaustively but suffered from state explosion; abstract interpretation provided a way to soundly approximate those state spaces. Theorem proving (HOL, Isabelle, Coq) offered full expressiveness but required human guidance; abstract interpretation was fully automatic but traded completeness for automation.Abstract interpretation's legacy in formal methods is profound. It provided the first rigorous foundation for static analysis, transforming it from an ad-hoc collection of compiler tricks into a principled discipline. Today, virtually all production static analyzers—from simple type checkers to sophisticated industrial tools like Astrée (used to verify avionics software) and Polyspace—are built on abstract interpretation. The framework also influenced later developments: lightweight formal methods like Alloy and TLA+ adopted similar approximation strategies, and SAT/SMT-based verification (1990s onward) automated the search for counterexamples in a way that abstract interpretation had automated the search for invariants.A common misconception is that abstract interpretation is synonymous with static analysis. In fact, it is a specific theory of sound approximation; many static analysis tools are unsound (they may miss bugs) or use ad-hoc heuristics. Another pitfall is to confuse abstract interpretation with model checking: model checking explores all concrete states of a finite model, while abstract interpretation works with abstract states and is designed for infinite-state systems. The two are complementary: abstract interpretation can provide the invariants that model checking uses to prune its search, and model checking can verify properties that abstract interpretation cannot prove.The 16 concepts its tower teaches
- Abstract domain
- Abstract interpretation
- Abstract semantics
- Abstract transformer
- Chaotic iteration
- Collecting semantics
- Concretization function
- Fixpoint semantics
- Galois connection
- Least fixpoint
- Monotonic function
- Narrowing
- Program invariant
- Soundness (over-approximation)
- Static analysis
- Widening
- 1977-Present
Temporal and Modal Logics of Programs
How do we write down what a concurrent system must always do?
- 1978-Present
- 1981-Present
Model Checking
Can we check every possible state automatically?
About Model Checking
Model checking emerged in the early 1980s to address a pressing problem in formal methods: how to verify the correctness of finite-state systems automatically, without the manual ingenuity required by deductive verification. Where earlier frameworks like Hoare logic demanded that a human supply loop invariants and proof steps, model checking offered an algorithmic alternative. Given a finite-state model of a system and a specification expressed in temporal logic, a model checker can automatically determine whether the specification holds by exhaustively exploring all reachable states of the model. Crucially, when a property fails, the model checker produces a counterexample trace—a concrete sequence of states that leads to the violation—giving engineers a specific bug to fix rather than an abstract proof obligation. This combination of automation and actionable feedback made model checking one of the most practically successful formal methods, especially in hardware verification.Core curriculum. A first course in model checking typically builds from the system representation to the specification language, then to the core algorithms and their optimizations. The following concepts form the teaching spine:- Finite-state model — the system under verification is abstracted as a directed graph where nodes represent states and edges represent transitions. Each state is labeled with atomic propositions that hold at that point.
- Temporal logic specification — desired system behavior is expressed in a logic that can reason about the ordering of events over time. The two main dialects are Computation Tree Logic (CTL) and Linear Temporal Logic (LTL). CTL quantifies over paths (e.g., "along all paths, eventually holds"), while LTL reasons about individual execution traces (e.g., "globally, if then eventually ").
- Safety and liveness properties — specifications are classified into two broad categories: safety properties assert that "nothing bad ever happens" (e.g., the elevator door is never open while the cabin moves), and liveness properties assert that "something good eventually happens" (e.g., every floor request is eventually serviced).
- State space exploration — the fundamental algorithm: starting from the initial state, the model checker systematically visits all reachable states, checking the temporal logic specification against each state. For finite-state systems, this reduces to a graph search.
- **Bü automaton** — for LTL model checking, the specification is translated into a Büchi automaton, a finite automaton that accepts infinite words. The model checking problem then reduces to checking whether the product of the system model and the automaton has an empty language (i.e., no accepting run ).
- Binary Decision Diagrams (BDDs) — a compact, canonical representation of Boolean functions. BDDs enable symbolic model checking, which manipulates sets of states implicitly rather than enumerating them individually, dramatically increasing the size of systems that can be verified.
- Partial order reduction — a technique that exploits the independence of concurrent events to reduce the number of interleavings that must be explored, mitigating state explosion in concurrent systems.
- Counterexample-guided abstraction refinement (CEGAR) — an iterative method that starts with an abstract model, checks it, and if a counterexample is found, refines the model to eliminate spurious counterexamples until either a real bug is found or the property is proved.
- Explicit-state model checking — the original approach, where each state is represented explicitly and stored in a hash table. This contrasts with symbolic model checking and is still used in tools like SPIN for protocol verification.
- Model checking tools (SPIN, NuSMV) — SPIN, developed at Bell Labs, specializes in LTL verification of asynchronous software models, especially communication protocols. NuSMV, derived from the original SMV (Symbolic Model Verifier), supports both CTL and LTL and is widely used for hardware verification.
- Property Specification Language (PSL) — an industrial standard for expressing temporal logic assertions in hardware design, bridging the gap between formal verification and engineering practice.
Intellectual history. The intellectual roots of model checking lie in two earlier developments. First, Amir Pnueli's 1977 proposal to use temporal logic for specifying program properties provided the specification language that model checking would later adopt. Pnueli received the 1996 Turing Award for this work. Second, the tradition of automated theorem proving and deductive verification (Hoare logic, 1969) established the ideal of mathematical correctness but revealed the impracticality of manual proof for large systems.The framework itself was founded independently by two groups in the early 1980s. Edmund M. Clarke and E. Allen Emerson published their seminal paper "Design and Synthesis of Synchronization Skeletons Using Branching Time Temporal Logic" in 1981, introducing CTL model checking for finite-state systems. At roughly the same time, Jean-Pierre Queille and Joseph Sifakis developed a similar approach, published in 1982. These works defined the core problem: given a finite-state structure and a temporal logic formula , decide whether . For their foundational contributions, Clarke, Emerson, and Sifakis shared the 2007 Turing Award.Early model checking used explicit-state enumeration, which quickly ran into the state explosion problem: the number of states grows exponentially with the number of system components. The breakthrough came in the late 1980s when Ken McMillan and others, building on Randal Bryant's work on Binary Decision Diagrams, developed symbolic model checking. By representing sets of states implicitly as BDDs, symbolic model checking could verify circuits with millions of states, making the technique practical for industrial hardware verification. The SMV tool, developed by McMillan at Carnegie Mellon, became the canonical implementation.In the 1990s, model checking expanded to software. Gerard Holzmann's SPIN tool, first released in 1991, applied explicit-state model checking to communication protocols, using order reduction to handle concurrency. The CEGAR technique, formalized by Edmund Clarke and others in the early 2000s, allowed model checking to scale to larger software systems by iteratively refining abstractions. These developments allowed model checking to coexist with peer frameworks: abstract interpretation provides static analysis without state enumeration, while lightweight formal methods like Alloy and TLA+ use bounded model checking or explicit-state exploration for software specifications. Model checking did not replace these frameworks but supplemented them, offering a distinct point in the design space: full automation and counterexample generation, at the cost of requiring finite-state models.Key insights: Model checking transformed verification from a manual proof activity into an automated debugging tool, introduced the crucial concept of counterexample-guided debugging, and demonstrated that exhaustive state exploration is feasible for many real-world systems when combined with symbolic representations and abstraction.Common pitfalls: Model checking is not testing—it exhaustively checks all behaviors of a finite-state model, not a sample. It is also not a silver bullet: state explosion remains a challenge, and infinite-state systems require abstraction or restriction to finite domains.The 16 concepts its tower teaches
- Binary Decision Diagrams (BDDs)
- Büchi automaton
- Computation Tree Logic (CTL)
- Counterexample trace
- Counterexample-guided abstraction refinement (CEGAR)
- Explicit-state model checking
- Finite-state model
- Linear Temporal Logic (LTL)
- Model checking tools (SPIN, NuSMV)
- Partial order reduction
- Property Specification Language (PSL)
- Safety and liveness properties
- State explosion problem
- State space exploration
- Symbolic model checking
- Temporal logic specification
- 1996-Present
- 2000-Present
Deductive Software Verification Tools
Can a tool prove a program meets its contract?
- 2000-Present
SMT-Based Deductive Verification
Can solvers discharge the routine proof steps?
- 2001-Present
How the ideas connect
Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.
Deductive Software Verification Tools influenced by Axiomatic semantics
Deductive verification tools are Hoare-logic provers in practice: they generate verification conditions from annotated programs using the rules Hoare set out. The loop invariant the programmer supplies is still the central artefact.
Carried by C. A. R. Hoare.
Model Checking influenced by Temporal and Modal Logics of Programs
Model checking was created to decide whether a finite-state system satisfies a temporal-logic formula, taking Pnueli's program logics as the specification language. Clarke and Emerson's algorithm checks CTL formulas against state graphs.
Carried by Edmund Clarke; E. Allen Emerson; Amir Pnueli.
Formal Specification and Refinement influenced by Axiomatic semantics
Specification languages and refinement methods took the pre/postcondition assertion style of Hoare logic as their basic statement of what a program must do. The B method's proof obligations are essentially Hoare-style triples discharged over refinement steps.
Carried by Jean-Raymond Abrial; Cliff Jones.
Abstract Interpretation grew out of Semantics
Abstract interpretation was presented as a theory of semantics: concrete semantics is mapped to an abstract semantics by Galois connections. The Cousots built the framework explicitly on the denotational and operational semantics of the day.
Carried by Patrick Cousot; Radhia Cousot.
Process calculus influenced by Semantics
Process calculi gave concurrent languages an operational semantics in the Plotkin style, defining behaviour by labelled transition rules. Milner's CCS and its successors were presented as operational semantics of process terms.
Carried by Robin Milner; Gordon Plotkin.
Deductive Software Verification Tools influenced by Proof assistant
Deductive verification tools use interactive provers as their backend to discharge the verification conditions they generate. The trusted-kernel architecture of LCF-style provers carries over into these tools.
Deductive Software Verification Tools influenced by Formal Specification and Refinement
Deductive verification tools take specifications written in specification languages and generate proof obligations from them, inheriting the pre/postcondition and refinement discipline. The specification is the input; the tool proves the code meets it.
SMT-Based Deductive Verification influenced by Formal Specification and Refinement
SMT-based verifiers inherit the specification-and-refinement style, expressing contracts as pre/postconditions and discharging them with solvers. The refinement obligations of the B tradition reappear as verification conditions.
Runtime Verification influenced by Temporal and Modal Logics of Programs
Runtime verification monitors executions against temporal-logic specifications, inheriting the formulas and semantics developed for program logics. The specifications written for offline checking are reused on running traces.
Model Checking influenced by Process calculus
Model checkers for concurrent systems took process-algebraic descriptions as input and checked them against temporal formulas, linking the two concurrency traditions. Tools built on CCS/CSP-style specifications made the state graph explicit for search.
Runtime Verification influenced by Model Checking
Runtime verification adapted the specification languages and monitoring ideas of model checking to execution traces, checking properties online instead of by exhaustive state search. The temporal formulas are the same; only the checking method changes.
Lightweight Formal Methods influenced by Model Checking
Lightweight formal methods promoted bounded and partial uses of model checking, such as checking small models or limited properties, as a practical compromise. The model-checking engine is the tool being applied lightly.
Beyond the field
Where Formal Methods's ideas came from in other fields, and what they led to there: the strongest 12 of 33 links.
Proof assistant influenced by Proof Theory in Mathematical Logic
Proof assistants implement proof theory: natural deduction and sequent calculus, Gentzen's rules, and the Curry–Howard correspondence between proofs and programs are the formal basis on which their kernels check derivations.
Carried by Gerhard Gentzen; Haskell Curry; William Alvin Howard.
Abstract Interpretation influenced Scalable Bug-Finding Static Analysis in Program Analysis
Scalable bug-finding analyzers apply abstract interpretation, often unsound or path-sensitive variants, to whole programs. The lattice-based abstraction machinery from Cousot and Cousot is the technical core of these tools.
Carried by Patrick Cousot; Radhia Cousot.
Abstract Interpretation influenced Counterexample-Guided Abstraction Refinement in Program Analysis
CEGAR builds directly on abstract interpretation: the abstract domain and its concretization function come from Cousot-style abstraction, and refinement adjusts the abstraction when a spurious counterexample appears. The technique is a refinement loop around abstract interpretation.
Carried by Patrick Cousot; Radhia Cousot.
Temporal and Modal Logics of Programs influenced by Temporal logic in Philosophical Logic
The philosophical temporal logic of Prior and its later development gave Pnueli the modal operators and semantics he reinterpreted over computation paths to specify reactive systems.
Carried by Amir Pnueli; Arthur Prior.
Temporal and Modal Logics of Programs influenced by Temporal logic in Modal Logic
Pnueli's 1977 paper applied Prior's tense logic directly to program correctness, reading temporal operators as statements about execution sequences; this founded the temporal logic of programs.
Carried by Amir Pnueli; Arthur Prior.
Model Checking led to Model-based verification in Systems Verification
Model checking is the algorithmic core that model-based verification applies to system and software models. The later framework generalizes model checking from finite-state programs to engineering models of whole systems.
Model Checking influenced Counterexample-Guided Abstraction Refinement in Program Analysis
Counterexample-guided abstraction refinement was introduced to make model checking scale, using the model checker to produce counterexamples that drive refinement of the abstract model. The counterexample is the central artifact passed between the two.
Carried by Edmund M. Clarke; Thomas A. Henzinger.
Lightweight Formal Methods grew out of Formal Methods in Software Engineering
Lightweight formal methods were proposed in the mid-1990s as a deliberate branch of formal methods, applying them selectively where cost-effective rather than for full verification.
Deductive Software Verification Tools grew out of Formal verification in Software Testing
Deductive software verification tools are the mechanised continuation of the formal verification tradition, turning program logics and proof rules into working tool support.
SMT-Based Deductive Verification grew out of Formal verification in Software Testing
SMT-based deductive verification is a continuation of formal verification, replacing or supplementing interactive proof with satisfiability-modulo-theories solvers.
Axiomatic semantics influenced Mechanized semantics in Pl Semantics
Mechanized semantics frequently formalizes axiomatic semantics, such as Hoare logic, and proves its soundness with respect to operational or denotational definitions inside a proof assistant. The axiomatic approach supplies the proof rules being mechanized.
Axiomatic semantics influenced Abstract Interpretation in Program Analysis
Axiomatic semantics in Formal Methods, chiefly Hoare logic, provided the assertion-based program semantics that abstract interpretation generalized into a lattice-theoretic framework. Cousot and Cousot explicitly related their approximation theory to these earlier semantic styles.
Carried by C. A. R. Hoare; Patrick Cousot.

Formal Methods is a planet in Nousfarer
Its city has a tower for each of these 12 frameworks. Land, walk in, and climb one concept at a time.
Land on Formal MethodsRelated fields
Fields its ideas are linked to
- Mathematical Logic 4 links
- Program Analysis 4 links
- Programming Languages 4 links
- Pl Semantics 3 links
- Software Engineering 3 links
- Software Security 2 links
- Software Testing 2 links
- Systems Verification 2 links
- Model Theory 1 link
- Proof Theory 1 link
- Network Protocols 1 link
- Logic 1 link