Course Information

CS 735: Formal models for Concurrent and Asynchronous Systems

1. Petri nets – Modeling and analyzing asynchronous systems using Petri nets. Decision problems related to reachability, coverability, etc. for different variants of Petri nets. Other verification related issues. Tools, implementations and case-studies.

2. Asynchronous automata and Zielonka's theorem. - partial orders, traces, diamond closure, optimal constructions.

3. Message passing automata and message sequence charts – Models for scenario based modeling of concurrent and message passing systems.

4. Lossy channel systems and generalization to the theory of well-structured transition systems. Properties of well-quasi orders, well-structured transition systems and decidability issues. Relation to Petri nets and other examples.

Understanding Petri Nets: Modeling Techniques, Analysis Methods, Case Studies by W Reisig, Springer, 2013.

Petri Nets: Properties, Analysis and Applications, Invited tutorial-survey paper by T Murata, Proceedings of IEEE, Vol 77, No.4, 1988.

Automata on Distributed Alphabets: M Mukund Modern Applications of Automata Theory, D D'Souza and P Shankar (eds), World Scientific, pp. 45-78, 2012.

Formal Models of Communicating Systems:
Languages, Automata, and Monadic Second-Order Logic by B Bollig, Springer, 2006.

Well-structured transition systems everywhere!-- Research article by A Finkel and P Schnoebelen, TCS, 2001.
Home Page


Discrete structures, Automata theory or equivalent.
Other Details

Duration : Full Semester Total Credit : 6
Type : Theory
Autumn Semester 2019-20

Status : Offered Instructor : Prof. S. Akshay
Spring Semester 2019-20

Status : Not Offered Instructor : ---

Last Modified Date: 15-Jul-2013


Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback