Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Hoare Logic: Strongest Postcondition and Weakest Precondition

In course

CS-550: Formal verification

We introduce formal verification as an approach for developing highly reliable systems. Formal verification finds proofs that computer systems work under all relevant scenarios. We will learn how to use formal verification tools and explain the theory and ...

Description

This lecture covers Hoare logic, which allows inserting annotations into code to simplify proofs about program behavior. Topics include computing relations, havoc, non-deterministic choice, assume command, and translating programs into relations.

Instructor

Viktor Kuncak

Viktor Kunčak joined EPFL in 2007, after receiving a PhD degree from MIT. Since then has been leading the Laboratory for Automated Reasoning and Analysis and supervised at least 12 completed PhD theses. His works on languages, algorithms and systems for verification and automated reasoning. He served as an initiator and one of the coordinators of a European network (COST action) in the area of automated reasoning, verification, and synthesis. In 2012 he received a 5-year single-investigator European Research Council (ERC) grant of 1.5M EUR. His invited talks include those at Lambda Days, Scala Days, NFM, LOPSTR, SYNT, ICALP, CSL, RV, VMCAI, and SMT. A paper on test generation he co-authored received an ACM SIGSOFT distinguished paper award at ICSE. A PLDI paper he co-authored was published in the Communications of the ACM as a Research Highlight article. His Google Scholar profile reports an over-approximate H-index of 38. He was an associate editor of ACM Transactions on Programming Languages and Systems (TOPLAS) and served as a co-chair of conferences on Computer-Aided Verification (CAV), Formal Methods in Computer Aided Design (FMCAD), Workshop on Synthesis (SYNT), and Verification, Model Checking, and Abstract Interpretation (VMCAI). At EPFL he teaches courses on functional and parallel programming, compilers, and verification. He has co-taught the MOOC "Parallel Programming" that was visited by over 100'000 learners and completed by thousands of students from all over the world.

Official source

Related concepts (15)

Translation

Translation is the communication of the meaning of a source-language text by means of an equivalent target-language text. The English language draws a terminological distinction (which does not exist in every language) between translating (a written text) and interpreting (oral or signed communication between users of different languages); under this distinction, translation can begin only after the appearance of writing within a language community.

Translation studies

Translation studies is an academic interdiscipline dealing with the systematic study of the theory, description and application of translation, interpreting, and localization. As an interdiscipline, translation studies borrows much from the various fields of study that support translation. These include comparative literature, computer science, history, linguistics, philology, philosophy, semiotics, and terminology. The term "translation studies" was coined by the Amsterdam-based American scholar James S.

Literal translation

Literal translation, direct translation, or word-for-word translation is a translation of a text done by translating each word separately without looking at how the words are used together in a phrase or sentence. In translation theory, another term for literal translation is metaphrase (as opposed to paraphrase for an analogous translation). It is to be distinguished from an interpretation (done, for example, by an interpreter). Literal translation leads to mistranslation of idioms, which was once a serious problem for machine translation.

Machine translation

Machine translation is use of either rule-based or probabilistic (i.e. statistical and, most recently, neural network-based) machine learning approaches to translation of text or speech from one language to another, including the contextual, idiomatic and pragmatic nuances of both languages. History of machine translation The origins of machine translation can be traced back to the work of Al-Kindi, a ninth-century Arabic cryptographer who developed techniques for systemic language translation, including cryptanalysis, frequency analysis, and probability and statistics, which are used in modern machine translation.

Predicate transformer semantics

Predicate transformer semantics were introduced by Edsger Dijkstra in his seminal paper "Guarded commands, nondeterminacy and formal derivation of programs". They define the semantics of an imperative programming paradigm by assigning to each statement in this language a corresponding predicate transformer: a total function between two predicates on the state space of the statement. In this sense, predicate transformer semantics are a kind of denotational semantics.

Related lectures (37)

Hoare Logic: Strongest Postcondition and Weakest Precondition

Covers Hoare logic, strongest postcondition, and weakest precondition for simplifying proofs in imperative programming.

Proteins: Central Dogma and Translation

Explains protein synthesis, translation, and the central dogma of molecular biology.

Protein Synthesis: Translation

Explains protein synthesis through translation, covering ribosomes, tRNA, amino acids, genetic code accuracy, and translation stages.

Converting Imperative Programs to Formulas

Explores converting imperative programs to formulas, including verification conditions, formula construction, and control flow structures.

Combinatorial Search: For-Expressions