Differences between revisions 6 and 7
Revision 6 as of 2017-04-17 11:44:03
Size: 17377
Editor: rupak
Comment:
Revision 7 as of 2017-04-17 11:44:42
Size: 16920
Editor: rupak
Comment:
Deletions are marked like this. Additions are marked like this.
Line 62: Line 62:

---- /!\ '''Edit conflict - other version:''' ----

---- /!\ '''Edit conflict - other version:''' ----

---- /!\ '''Edit conflict - your version:''' ----

---- /!\ '''End of edit conflict''' ----
Line 81: Line 73:


---- /!\ '''Edit conflict - other version:''' ----
---- /!\ '''Edit conflict - your version:''' ----
Line 96: Line 84:


---- /!\ '''End of edit conflict''' ----


---- /!\ '''Edit conflict - your version:''' ----

---- /!\ '''End of edit conflict''' ----

Course: Advanced Automata Theory

Summer 2017

Introduction

  • Syllabus and contents.

We shall study automata on finite/infinite words and trees and their relationship to logic and computer-aided verification of systems.

  • Intended Audience.

Computer science or math students with background in logic and theory of computation. (Familiarity with basic algorithms, logic, and theory of computation will be assumed). Talk to the instructor if you are not sure if you have the background. We shall try to keep the class self-contained, please attend the initial lecture for background material.

Further, I expect you (1) have "mathematical maturity" (e.g., you should be comfortable with proofs and abstract reasoning); (2) are interested in the material; and (3) are willing to spend time outside of class in order to better understand the material presented in lectures.

  • Grading


/!\ Edit conflict - other version:



/!\ Edit conflict - other version:



/!\ Edit conflict - your version:



/!\ End of edit conflict


Grading will be based on a written, open-notes, final exam. Open notes means that you are free to bring your notes to the exam. However, you may not use internet access on any device during an exam.

In order to appear for the exam, you have to turn in homework problems (to be assigned approximately biweekly), write up lecture notes for two lectures, and present a result to the class.


/!\ Edit conflict - other version:



/!\ Edit conflict - your version:


Grading will be based on a written, open-notes, final exam. Open notes means that you are free to bring your notes to the exam. However, you may not use internet access on any device during an exam.

In order to appear for the exam, you have to turn in homework problems (to be assigned approximately biweekly), write up lecture notes for two lectures, and present a result to the class.


/!\ End of edit conflict



/!\ Edit conflict - your version:



/!\ End of edit conflict


  • Textbook:

    • Class notes and research papers will be handed out.

The text book Michael Sipser, Introduction to the theory of computation, contains the material we will cover in the first few weeks as well as the required background for the class.

  • Teamwork and Academic Honesty:

Students may collaborate on homeworks, but each student needs to individually write up a solution set and be prepared to present it in class on the due date. The work you submit in this course must be the result of your individual effort. You may discuss homework problems and general proof strategies or algorithms with other students in the course, but you must not collaborate in the detailed development or actual writing of problem sets. This implies that one student should never have in his or her possession a copy of all or part of another student's homework. It is your responsibility to protect your work from unauthorized access. In writing up your homework you are allowed to use any book, paper, or published material. However, you are not allowed to ask others for specific solutions, either in person or by using electronic forums such as newsgroups. Of course, during the administration of exams any form of cooperation or help is forbidden. Academic dishonesty has no place in a university; it wastes our time and yours, and it is unfair to the majority of students. Any dishonest behavior will be severely penalized and may lead to failure in the course.

  • Logistics of Homework:

Homework exercises will be handed out every two weeks (weekday TBA). Your answers must be handed in until the day specified in the homework, at the beginning of the lecture.

  • Teamwork and Academic Honesty:

Students may collaborate on homeworks, but each student needs to individually write up a solution set and be prepared to present it in class on the due date. The work you submit in this course must be the result of your individual effort. You may discuss homework problems and general proof strategies or algorithms with other students in the course, but you must not collaborate in the detailed development or actual writing of problem sets. This implies that one student should never have in his or her possession a copy of all or part of another student's homework. It is your responsibility to protect your work from unauthorized access. In writing up your homework you are allowed to use any book, paper, or published material. However, you are not allowed to ask others for specific solutions, either in person or by using electronic forums such as newsgroups. Of course, during the administration of exams any form of cooperation or help is forbidden. Academic dishonesty has no place in a university; it wastes our time and yours, and it is unfair to the majority of students. Any dishonest behavior will be severely penalized and may lead to failure in the course.

  • Logistics of Homework:

Homework exercises will be handed out every two weeks (weekday TBA). Your answers must be handed in until the day specified in the homework, at the beginning of the lecture.

Announcements

  • The first lecture is on April 18, 2017.

Schedule

#

Date

Course topic / lecture

Homework

Materials

Video

L1

April 23

Introduction to formal verification

Lecture slides
De Millo, Lipton, and Perlis. Social processes and proofs of programs.

-

April 25

L2

April 28

Preliminaries: graph algorithms, automata theory

Homework 1. Need not be turned in.

Lecture notes

L3

April 30

Preliminaries: propositional logic

Lecture notes
Problem L (Labyrinth). Solution.
Try OCaml, Learn OCaml, Real World OCaml

T1

May 2

Solutions to Homework 1.

L4

May 5

The invariant verification problem. Enumerative invariant verification. Depth first search. Spin.

Notes from an unpublished text book by Rajeev Alur and Tom Henzinger:
The Reactive modules modeling language.
Invariant verification.
SPIN web page.

L5

May 7

Peterson's protocol. Heuristics for enumerative invariant verification. Symbolic invariant verification. Symbolic reachability.

Alur and Henzinger. Symbolic graph representation.

MPG (660 MB)

T2

May 9

Q & A

L6

May 12

Symbolic model checking with SAT

Malik and Weissenbacher. Boolean satisfiability solvers: Techniques and extensions.
Nieuwenhuis, Oliveras, and Tinelli. Solving SAT and SAT modulo theories: From an abstract Davis-Putnam-Logemann-Loveland procedure to DPLL(T).

MPG (678 MB)

L7

May 14

Implementing a SAT Solver. BDDs.

Homework 2. Due May 28, 2014.

MP4 (529 MB)

T3

May 16

Q & A

L8

May 19

BDDs.

Bryant. Graph-based algorithms for Boolean function manipulation. (The BDD paper.)

MP4 (434 MB)

L9

May 21

SMT. Timed automata and difference constraints.

Project suggestions.
Alur, Parthasarathy. Decision problems for timed automata: A survey.

T4

May 23

Q & A

MP4 (313 MB)

L10

May 26

Symbolic execution.

Cadar, Sen. Symbolic execution for software testing: Three decades later.

L11

May 28

Inductive invariants. Abstraction.

T5

May 30

Solutions to Homework 2.

L12

June 2

Predicate abstraction and CEGAR.

Survey on software model checking.

L13

June 4

IC3.

Homework 3. Due June 18, 2014.

Bradley. SAT-based model checking without unrolling. (The IC3 paper.)
Somenzi, Bradley. IC3: Where monolithic and incremental meet. (The IC3 tutorial.)

T6

June 6

Q & A

-

June 9

Holiday (No lecture)

L14

June 11

Interpolation-based model checking

McMillan. Interpolation and SAT-based model checking.

T7

June 13

Discussing projects

L15

June 16

Simulation and Bisimulation

Partition refinement

L16

June 18

Simulation and Bisimulation

T8

June 20

Solutions to Homework 3.

L17

June 23

Well-structured Transition Systems

Majumdar. Marktoberdorf 2013 lecture notes.

-

June 25

Cancelled.

T9

June 27

Q & A

L18

June 30

Example: Concurrent programs

L19

July 2

Safe Temporal Logic (STL)

Homework 4. Due July 9/July 16, 2014.

Notes on STL

T10

July 4

Q & A

L20

July 7

Model checking STL

L21

July 9

Safety vs liveness

Practice exam

Safety and liveness (We did not cover all the material)

-

July 11

Cancelled

L22

July 14

CTL

CTL (For reading about linear time logics and automata: Automata-theoretic verification

L23

July 16

Model checking CTL

Solutions to the Practice Exam

T11

July 18

Solutions to Homework 4. Moved to 10:00 am!

-

July 21

No lecture (preperation time for project presentations)

L24

July 23

Project presentations

T12

July 25

Preparation for exam

Homework 5. (No due date)

Courses/AdvancedAutomataTheory-SS2017 (last edited 2018-03-29 06:38:49 by neider)