This paper describes the applicability of relation-algebraic methods to state space analysis of Petri nets. It provides an in-depth summary of relation-algebraic methods--an area in which the authors, particularly Fronk, have already published numerous works. The paper builds mainly on these existing works, and this consolidation of them is a substantial contribution.

The introduction allows readers who are not very familiar with Petri nets to update their knowledge. Nevertheless, some background in formal models and Petri nets is required, in order to understand the motivation of the work.

As the authors state, the reachability problem is generally nondeterministic polynomial time (NP) complete and complexity can be polynomial for specific net classes. Thus, their objective is to evaluate the applicability of relation-algebraic concepts in this context. This is done mathematically, in approximately 20 pages, where the authors consolidate results from previous work to present a coherent picture. The evaluation sounds convincing; as most tools and examples are publicly available, interested readers will be able to reproduce some of the results presented. The reduction of token sizes in some examples appears rather arbitrary. This is also one of the key findings in the evaluation summary (Section 8.5): “relation algebra is both space efficient and of high performance if the number of tokens is kept small.”

Overall, Fronk and Kehden’s approach is (still) exponential and is best suited for a specific set of problems in reachability analysis, such as “finding a pair of markings such that two places are marked simultaneously, or finding home states.” Both the text passages and formulas are clearly written and pleasant to read. I recommend it to anyone who needs an overview of the state of the art in Petri nets as a modeling method.