Yih-Kuen Tsay's Wiki @ IM.NTU

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Automatic Verification, Fall 2019 ======
The goal of this course is to acquaint the students with fundamentals of automatic verification (of computer systems, in particular software) and to prepare them for conducting research in the area.

===== Announcements =====
  * 11/05: {{courses:av2019:hw5.pdf|HW#5}} due on 11/13.
  * 11/05: slides for Automata-Theoretic Approach and for An Example available.
  * 10/30: slides for Symbolic Model Checkers available.
  * 10/24: the diagram in Problem 3 of HW#4 corrected.
  * 10/23: slides for Model Checking mu-Calculus available.
  * 10/23: {{courses:av2019:hw4.pdf|HW#4}} due on 10/30.
  * 10/15: slides for Symbolic Model Checking available.
  * 10/09: {{courses:av2019:hw3.pdf|HW#3}} due on 10/16.  
  * 10/09: slides for Binary Decision Diagrams available.
  * 10/02: slides for Ordered Sets and Fixpoints available.
  * 10/02: {{courses:av2019:hw2.pdf|HW#2}} due on 10/09.  
  * 09/18: slides for Temporal Logic Model Checking available.
  * 09/18: {{courses:av2019:hw1.pdf|HW#1}} due on 09/25.
  * 09/11: slides for Introduction and for Systems Modeling available.
  * 09/03: this website created on 08/31.
===== Instructor =====

[[http://im.ntu.edu.tw/~tsay/|Yih-Kuen Tsay (蔡益坤)]], NTU IM Dept., 3366-1189, ''Xtsay@im.ntu.edu.twX'' (between the enclosing pair of X's)

===== Lectures =====

Wednesday 2:20--5:20PM, Room 203, Management Building 1 (when the class is small enough, we meet in the seminar room on the 11th floor)

===== Office Hours =====

Tuesday 1:30--2:00PM, Wednesday 1:30--2:00PM, or by appointment, Room 1108, Management II

===== Textbooks =====

  - //Model Checking//, E.M. Clarke, O. Grumberg, and D.A. Peled, The MIT Press, 1999. [CGP](A copy of this book has been put on reserve at NTU Library in the 教師指定參考書區 under the name “BM-5自動化軟體驗證”.) 
  - //Principles of Model Checking//, C. Baier and J.-P. Katoen, The MIT Press, 2008. [BK] (A copy of this book has also been put on reserve at NTU Library.) 
  - //The SPIN Model Checker: Primer and Reference Manual//, G.J. Holzmann, Addison-Wesley, 2003. [H]
  - //Temporal Verification of Reactive Systems: Safety//, Z. Manna and A. Pnueli, Springer, 1995. [MP]
  - //Selected Papers//. [SP]
  - //Class Notes//. [CN]

===== Syllabus/Schedule (with links to slides/notes)=====
This course provides an introduction to the foundations, methods, and tools for automatic verification. The focus is on algorithmic (including model checking) methods. A separate complementary course entitled "Software Specification and Verification" covers deductive methods. We shall seek a balance between breadth and depth, covering both the foundations and some of the more successful methods and tools. Below is a tentative list of topics and their schedule:
  * Introduction [CGP: Ch. 1; BK: Ch. 1; H: Ch. 1] (.5 week: 9/11a) [{{courses:av2019:introduction.pdf|slides}}]
  * Systems Modeling [CGP: Ch. 2; BK: Ch. 2,3; H: Ch. 2; MP: Ch. 0.1-4] (.5 week: 9/11b)   [{{courses:av2019:modeling.pdf|slides}}]
  * Temporal Logic Model Checking [CGP: Ch. 3,4; BK: Ch. 6; MP: Ch. 5.2-3] (2 weeks: 9/18, 9/25) [{{courses:av2019:temporal_logic_model_checking.pdf|slides}}]
  * Ordered Sets and Fixpoints [CN] (1 week: 10/2) [{{courses:av2019:ordered_sets.pdf|slides}}]
  * Binary Decision Diagrams [CGP: Ch. 5; SP] (1 week: 10/9) [{{courses:av2019:bdd.pdf|slides}}]
  * Symbolic Model Checking [CGP: Ch. 6] (1 week: 10/16) [{{courses:av2019:symbolic_model_checking.pdf|slides}}]
  * Model Checking μ-Calculus [CGP: Ch. 7] (1 week: 10/23) [{{courses:av2019:mu_calculus.pdf|slides}}]
  * Symbolic Model Checkers [CGP: Ch. 8; SP; CN] (1 week: 10/30) [{{courses:av2019:symbolic_model_checkers.pdf|slides}}]
  * Automata-Theoretic Approach [CGP: Ch. 9; BK: Ch. 4.3,4.4,5; H: Ch. 6; MP: Ch. 5.1] (2 weeks: 11/6, 11/13)  [slides: {{courses:av2019:automata_theoretic_approach.pdf|Automata-Theoretic Approach to Model Checking}}, {{courses:av2019:p_U_q.pdf|An Example of Temporal Formula to Automaton Translation}}]
  * The Spin Model Checker [H: Ch. 3, 4, 7, 12] (1 week: 11/20) [{{courses:av2019:the_spin_model_checker.pdf|slides}}]
  * Equivalence, Simulation, and Abstraction [CGP: Ch. 11,13; BK: Ch. 7; SP] (1 week: 11/27) [{{courses:av2019:abstraction.pdf|slides}}]
  * Compositional Reasoning [CGP: Ch. 12; SP; CN] (1 week: 12/4) [{{courses:av2019:compositional_reasoning.pdf|slides}}]
  * Satisfiability Solving and Tools [SP; CN] (1 week: 12/11) [{{courses:av2019:sat.pdf|slides}}]
  * Bounded Model Checking [SP] (1 week: 12/18) [{{courses:av2019:bounded_model_checking.pdf|slides}}]
  * **Final** (**2019/12/25**)
  * Satisfiability Modulo Theories (SMT), Solvers, and Applications [SP; CN] (1 week: 2020/1/8) [{{courses:av2019:smt.pdf|slides}}]

===== Grading =====

Homework Assignments 20%, Participation 10%, Final Exam 40%, Term Paper/Report 30%.
Yih-Kuen Tsay's Wiki @ IM.NTU

User Tools

Site Tools

Page Tools
