Lecture

Hoare Logic: Strongest Postcondition and Weakest Precondition

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

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 introduces Hoare logic, focusing on the concepts of strongest postcondition and weakest precondition. It covers the definitions of Hoare triple, strongest postcondition, and weakest precondition, along with examples and proofs. The instructor explains how to use Hoare logic to simplify proofs about imperative program behavior.

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 (32)

Adaptive behavior

Adaptive behavior is behavior that enables a person (usually used in the context of children) to cope in their environment with greatest success and least conflict with others. This is a term used in the areas of psychology and special education. Adaptive behavior relates to everyday skills or tasks that the "average" person is able to complete, similar to the term life skills. Nonconstructive or disruptive social or personal behaviors can sometimes be used to achieve a constructive outcome.

Behavior modification

Behavior modification is an early approach that used respondent and operant conditioning to change behavior. Based on methodological behaviorism, overt behavior was modified with consequences, including positive and negative reinforcement contingencies to increase desirable behavior, or administering positive and negative punishment and/or extinction to reduce problematic behavior. It also used Flooding desensitization to combat phobias.

Positive behavior support

Positive behavior support (PBS) uses tools from applied behaviour analysis and values of normalisation and social role valorisation theory to improve quality of life, usually in schools. PBS uses functional analysis to understand what maintains an individual's challenging behavior and how to support the individual to get these needs met in more appropriate way, instead of using 'challenging behaviours'. People's inappropriate behaviors are difficult to change because they are functional; they serve a purpose for them.

Applied behavior analysis

Applied behavior analysis (ABA), also called behavioral engineering, is a psychological intervention that applies empirical approaches based upon the principles of respondent and operant conditioning to change behavior of social significance. It is the applied form of behavior analysis; the other two forms are radical behaviorism (or the philosophy of the science) and the experimental analysis of behavior (or basic experimental laboratory research).

Imperative programming

In computer science, imperative programming is a programming paradigm of software that uses statements that change a program's state. In much the same way that the imperative mood in natural languages expresses commands, an imperative program consists of commands for the computer to perform. Imperative programming focuses on describing how a program operates step by step, rather than on high-level descriptions of its expected results.

Related lectures (64)

Hoare Logic: Postconditions and Preconditions

Covers Hoare logic, postconditions, preconditions, and program behavior proofs.

Hoare Logic: Foundations and Applications

Covers Hoare Logic, its foundations, applications, and significance in program verification.

Converting Imperative Programs to Formulas

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

Loops: Control Statements and Functions

Covers modeling control statements with functions in Scala, including while loops, repeat loops, and for-loops translation.