Ruka hadi maudhui
The Lumenary
Mwaka wa kwanza wa uzamiliComputationImepangwa

Formal methods

Mathematical methods for specifying and verifying software and hardware: operational and denotational semantics, Hoare logic, model checking, type soundness, and proof assistants for verified programs.

math.comp.formal-methods

Onyesha kila kinachohitajika kufikia mada hii

Somo la mada hii bado halijaandikwa. Muhtasari ulio hapa chini ni sehemu ya ramani ya mtaala na haujakaguliwa.

Inajengwa juu ya

First-order logicThe λ-calculusAlgorithm design and analysis

Masharti ya awali ya lazima 21 (hadi chini kabisa)

Utajifunza

  • Give an operational semantics for a small imperative language and prove properties by induction on derivations.
  • Verify programs with Hoare triples and loop invariants.
  • Model-check finite-state systems against temporal-logic specifications.

Fasili

  • A Hoare triple {P} C {Q} asserts that if P holds before command C runs and C terminates, then Q holds afterwards.
  • Model checking algorithmically decides whether a finite model satisfies a temporal-logic formula.
  • A type system is sound if well-typed programs cannot reach a stuck state (progress and preservation).

Nadharia

  • Hoare logic is sound, and it is relatively complete for suitable languages (Cook).
  • CTL model checking can be done in time linear in the product of the sizes of the model and the formula.
  • By Rice's theorem, verifying arbitrary properties of arbitrary programs cannot be fully automated.

Mawazo potofu ya kawaida

  • Thinking a verified program is correct in every sense; it is correct relative to its specification and its trusted base.
  • Believing partial correctness implies termination.

Ugunduzi wa hiari

Njia za kujifunza

Usomaji zaidi

  • Glynn Winskel, The Formal Semantics of Programming Languages (1993)
  • Michael Huth and Mark Ryan, Logic in Computer Science
  • Christel Baier and Joost-Pieter Katoen, Principles of Model Checking (2008)