LMC: 2001 Summer Lecture Series on
Temporal Logics and Process Algebras

Meeting Schedule:

Tue/Thu 2pm -- 4pm.
Applied Logic Lab Conference Room (1212).

Lecturers:

K. Narayan Kumar
Madhavan Mukund

Chennai Mathematical Institute, Chennai, India.

Series Outline:

This lecture series will be on temporal logics and process algebras. We expect to cover monadic logics (S1S, S2S); linear temporal logic; decidability and complexity of model checking in these logics and their sublogics; process algebra formalisms (PA, BPA, ...); notions of equivalences among processes; characterization of these equivalences.

The objective is to understand the fundamental concepts in these areas. As a concrete side-effect, we will collect introductory materials on these topics. For each lecture we will have a "volunteer" who'll take good notes and make a clean version of this available after the lecture.

The prerequisite for participation is familiarity with propositional logic, models, quantifiers, automata, and other topics covered in basic undergrad courses and qualifying exams. Materials covered in each lecture will be either posted online via this page, or distributed in the previous lecture.

Here is the plan of action:

0.	June 19 (Tue)	Organization
1.	June 21 (Thu)	Monadic Logics - Part 1 Material from Madhavan Mukund's "Automata on Infinite Words" (cached from http://www.cmi.ac.in/~madhavan/papers/tcs-96-2.html ) Topics: Monadic logics of 1 successor; First-order (F1S) and Second-order logics (S1S); Interpretation over finite strings; Equivalence of S1S over finite strings to regular languages. Lecturer: Kumar Scribes: Miti Adiecha and Yifei Dong
2.	June 26 (Tue)	Monadic Logics - Part 2 Topics: F1S over finite strings and star-free regular languages; F1S and S1S interpreted over infinite strings; Equivalence of S1S over infinite strings to omega-regular languages. Lecturer: Kumar Scribes: Luis Castro and Giridhar Pemmasani
3.	June 28 (Thu)	Monadic Logics - Part 3 Topics: Monadic logics of 2 successors; tree automata. Lecturer: Kumar Scribes: TBD
4.	July 3	Intro to LTL Material from Madhavan Mukund's LTL tutorial (cached from http://www.cmi.ac.in/~madhavan/papers/isical97.html )
5.	July 10 (Tue)	Sublogics, complexity issues - Part 1
6.	July 12 (Thu)	Sublogics, complexity issues - Part 2
7.	July 17 (Tue)	Process Algebras - Part 1
8.	July 19 (Thu)	Process Algebras - Part 2
9.	July 24 (Tue)	Equivalences - Part 1
10.	July 26 (Thu)	Equivalences - Part 2