Madhavan Mukund



Concurrency Theory

Jan–Apr, 2017


Administrative details

  • Teaching assistants: Debraj Chakraborty, Suman Sadhukhan

  • Evaluation:

    • Assignments, 35%

    • Mid-semeseter exam, 25%

    • Final exam, 40%

    • Copying is fatal.

  • Textbook:

    • We won't follow any one book. References will be put up under "Reading Material" as we go along.


Reading material

Elementary Net Systems

  • Elementary Net Systems (PDF),
    Grzegorz Rozenberg and Joost Engelfriet,
    Lectures on Petri Nets I: Basic Models, Advances in Petri Nets, Springer LNCS 1491 (1998) 12-121.

Petri Nets

  • Place/Transition Nets (PDF),
    Joerg Desel and Wolfgang Reisig,
    Lectures on Petri Nets I: Basic Models, Advances in Petri Nets, Springer LNCS 1491 (1998) 122-173.

  • An Improvement of McMillan's Unfolding Algorithm (PDF),
    Javier Esparza, Stefan Roemer and Walter Vogler,
    Formal Methods in System Design 20(3) (2002) 285-310.

Event Structures

  • Some Behavioural Aspects of Net Theory (PDF),
    P.S. Thiagarajan,
    Theoretical Computer Science, 71 (1990) 133-153.

  • Behavioural Notions for Elementary Net Systems (PDF),
    M. Nielsen, G. Rozenberg and P.S. Thiagarajan,
    Distributed Computing, 4 (1990) 45-75.

  • Petri Nets, Event Structures and Domains (PDF),
    M. Nielsen, G. Plotkin and G. Winskel,
    Theoretical Computer Science, 13 (1981) 85-108.

Theory of Regions

  • Petri Net Synthesis, Part I (PDF),
    E. Badouel and P. Darondeau, draft (2011)

Distributed Automata

  • Automata on Distributed Alphabets, (PDF),
    Madhavan Mukund,
    in Deepak D'Souza and Priti Shankar (eds),
    Modern Applications of Automata Theory, World Scientific (2012) 257-288.

Behavioural equivalences

  • The Linear Time - Branching Time Spectrum I: The Semantics of Concrete Sequential Processes, (PDF),
    Rob J. van Glabeek,
    in J.A. Bergstra, A. Ponse and S.A. Smolka (eds),
    Handbook of Process Algebra, Elsevier (2001) 3-99.

  • The Linear Time - Branching Time Spectrum II: The Semantics of Sequential Systems with Silent Moves, (PDF),
    Rob J. van Glabeek,
    expanded version of article from CONCUR 1993, Springer LNCS 715 (1993) 66-81.

  • Testing Equivalences for Processes, (PDF),
    R. de Nicola and Matthew Hennessy,
    Theoretical Computer Science, 34 (1984) 83-133.

Message-Passing Systems

  • On Communicating Finite-State Machines (PDF),
    Daniel Brand and Pitro Zafiropulo,
    Journal of the ACM, 30(2), (1983) 323-342.

  • The Theory of Message Sequence Charts (PDF),
    K. Narayan Kumar,
    in Deepak D'Souza and Priti Shankar (eds),
    Modern Applications of Automata Theory, World Scientific (2012) 289-324.

  • The Theory of Message Sequence Charts (PDF),
    K. Narayan Kumar,
    Slides from a talk at TIFR, April 2009.

  • Realizability and Verification of MSC Graphs (PDF),
    Rajeev Alur, Kousha Etessami, and Mihalis Yannakakis,
    Theoretical Cmputer Science, 331, (2005) 97-114.

  • Verifying Programs with Unreliable Channels (PDF),
    Parosh Aziz Abdulla and Bengt Jonsson,
    Information and Computation, 127, (1996) 91-101.

Well-Structured Transition Systems

  • Well-Structured Transition Systems Everywhere! (PDF),
    Alain Finkel and Philippe Schnoebelen,
    Theoretical Computer Science, 256, (2001) 63-92.


Course plan

  • Petri nets
  • Unfoldings and event structures
  • Distributed automata
  • Mazurkiewicz traces and Zielonka's theorem
  • Program equivalences: failures, testing, bisimulation
  • Message-passing systems
  • Well-structured transition systems


Lecture summaries