1-Safe Petri nets and special cube complexes: equivalence and applications
share
Nielsen, Plotkin, and Winskel (1981) proved that every 1-safe Petri net N unfolds into an event structure E_N. By a result of Thiagarajan (1996 and 2002), these unfoldings are exactly the trace regular event structures. Thiagarajan (1996 and 2002) conjectured that regular event structures correspond exactly to trace regular event structures. In a recent paper (Chalopin and Chepoi, 2017, 2018), we disproved this conjecture, based on the striking bijection between domains of event structures, median graphs, and CAT(0) cube complexes. On the other hand, in Chalopin and Chepoi (2018) we proved that Thiagarajan's conjecture is true for regular event structures whose domains are principal filters of universal covers of (virtually) finite special cube complexes. In the current paper, we prove the converse: to any finite 1-safe Petri net N one can associate a finite special cube complex X_N such that the domain of the event structure E_N (obtained as the unfolding of N) is a principal filter of the universal cover X_N of X_N. This establishes a bijection between 1-safe Petri nets and finite special cube complexes and provides a combinatorial characterization of trace regular event structures. Using this bijection and techniques from graph theory and geometry (MSO theory of graphs, bounded treewidth, and bounded hyperbolicity) we disprove yet another conjecture by Thiagarajan (from the paper with S. Yang from 2014) that the monadic second order logic of a 1-safe Petri net is decidable if and only if its unfolding is grid-free. Our counterexample is the trace regular event structure Ė_Z which arises from a virtually special square complex Ż. The domain of Ė_Z is grid-free (because it is hyperbolic), but the MSO theory of the event structure Ė_Z is undecidable.
READ FULL TEXT