1-safe Petri nets and special cube complexes. Equivalence and applications

DOI10.1145/3322095zbMATH Open1433.68243arXiv1810.03395OpenAlexW4288281500WikidataQ127470247 ScholiaQ127470247MaRDI QIDQ4972155FDOQ4972155

Authors: J. Chalopin, Victor Chepoi 

Publication date: 22 November 2019

Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)

Abstract: Nielsen, Plotkin, and Winskel (1981) proved that every 1-safe Petri net $N$ unfolds into an event structure $mathcal{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 $mathcal{E}_N$ (obtained as the unfolding of $N$) is a principal filter of the universal cover $widetilde{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 $mathcal{dotE}_Z$ which arises from a virtually special square complex $dotZ$. The domain of $mathcal{dotE}_Z$ is grid-free (because it is hyperbolic), but the MSO theory of the event structure $mathcal{dotE}_Z$ is undecidable.

Full work available at URL: https://arxiv.org/abs/1810.03395

Recommendations

• A counterexample to Thiagarajan's conjecture on regular event structures
• A counterexample to Thiagarajan's conjecture on regular event structures
• scientific article; zbMATH DE number 2087498
• scientific article; zbMATH DE number 2088670
• scientific article; zbMATH DE number 5587276

zbMATH Keywords

CAT(0) cube complexesmedian graphsunfoldingsuniversal covers1-safe Petri netscontext-free graphsspecial cube complexesMSO logictrace-regular event structures

Mathematics Subject Classification ID

Logic in computer science (03B70) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Cited In (8)

• Hyperbolic models for \(\mathrm{CAT}(0)\) spaces
• A counterexample to Thiagarajan's conjecture on regular event structures
• Rabin's theorem in the concurrency setting: a conjecture
• First-order logic axiomatization of metric graph theory
• Distributed Asynchronous Games With Causal Memory are Undecidable
• Title not available (Why is that?)
• A counterexample to Thiagarajan's conjecture on regular event structures
• Medians in median graphs and their cube complexes in linear time

This page was built for publication: 1-safe Petri nets and special cube complexes. Equivalence and applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4972155)