Category Archives: Formal methods

True Concurrency and Net Unfoldings

This week I gave a talk at my university on true concurrency. My main focus, although, was partial-order semantics for Petri nets.

Slide screenshot

Slide screenshot


Computer scientists have been paying attention concurrency and parallelism since the dawn of the computing as science. In this talk I would like to discuss the topic called true concurrency – the concurrency in presence of parallelism, as opposed to concurrency defined by interleaving.

Carl Adam Petri played a crucial role in the area of true concurrency, he was interested in analyzing the relations and connections between the abstract machines (that of Turing, Church and others) and their physical counterparts. Petri observed that the assumption of the global state is unrealistic in big systems and he proposed to replace the “execution semantics’’ with the semantics of”nonsequential proceses’’, the notion which gave rise to the theory of occurrence nets and unfoldings. That corpus of work has be introduced originally to solve the very theoretical problem: to give precise semantics to concurrent systems. Goltz, Reisig, Nielsen, Plotkin, Winskel, Engelfreit, Montanari are among the people who have contributed to the topic.

Later on, with the rise of model checking techniques, it has been discovered that partial-order semantics (unfoldings) may be used in practice for formally verifying systems. McMillan, Esparza, Romer, Vogler, Khomenko and others have pioneered what is now can be called a “partial order approach to model checking”.

True concurrency is still a thriving field, and in my talk I hope to touch the foundations, as well as pragmatic applications of the approaches derived from the theoretical foundations of the subject.


.PDF link

Introduction to software verification via model checking.

I have found a nice set of lecture on software verification:

The course introduces the theory and practice of formal methods for the design and analysis of software systems. The course will cover the underlying logical and theoretical concepts, with focus on the algorithmic solutions, and heuristics to cope with the high computational complexity.

Unfortunately, I cannot embed videos in the post, so I will just provide links to the videolectures:

Here are the presentations, used in the lecutres: [ 1 | 2 ]