A counterexample to Thiagarajan's conjecture on regular event structures

DOI10.4230/LIPICS.ICALP.2017.101zbMATH Open1442.68130arXiv1605.08288MaRDI QIDQ5111433FDOQ5111433

Authors: J. Chalopin, Victor Chepoi 

Publication date: 27 May 2020

Abstract: We provide a counterexample to a conjecture by Thiagarajan (1996 and 2002) that regular event structures correspond exactly to event structures obtained as unfoldings of finite 1-safe Petri nets. The same counterexample is used to disprove a closely related conjecture by Badouel, Darondeau, and Raoult (1999) that domains of regular event structures with bounded $atural$-cliques are recognizable by finite trace automata. Event structures, trace automata, and Petri nets are fundamental models in concurrency theory. There exist nice interpretations of these structures as combinatorial and geometric objects. Namely, from a graph theoretical point of view, the domains of prime event structures correspond exactly to median graphs; from a geometric point of view, these domains are in bijection with CAT(0) cube complexes. A necessary condition for both conjectures to be true is that domains of regular event structures (with bounded $atural$-cliques) admit a regular nice labeling. To disprove these conjectures, we describe a regular event domain (with bounded $atural$-cliques) that does not admit a regular nice labeling. Our counterexample is derived from an example by Wise (1996 and 2007) of a nonpositively curved square complex whose universal cover is a CAT(0) square complex containing a particular plane with an aperiodic tiling. We prove that other counterexamples to Thiagarajan's conjecture arise from aperiodic 4-way deterministic tile sets of Kari and Papasoglu (1999) and Lukkarila (2009). On the positive side, using breakthrough results by Agol (2013) and Haglund and Wise (2008, 2012) from geometric group theory, we prove that Thiagarajan's conjecture is true for regular event structures whose domains occur as principal filters of hyperbolic CAT(0) cube complexes which are universal covers of finite nonpositively curved cube complexes.

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

Recommendations

• A counterexample to Thiagarajan's conjecture on regular event structures
• 1-safe Petri nets and special cube complexes. Equivalence and applications
• scientific article; zbMATH DE number 2087498
• scientific article; zbMATH DE number 2088670
• Nice labeling problem for event structures: a counterexample

zbMATH Keywords

CAT(0) cube complexesmedian graphsunfoldingsuniversal coverstrace automatadiscrete event structures

Mathematics Subject Classification ID

Distance in graphs (05C12) Semantics in the theory of computing (68Q55) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Quasicrystals and aperiodic tilings in discrete geometry (52C23) Monoidal categories and operads (18M99)

Cited In (5)

• 1-safe Petri nets and special cube complexes. Equivalence and applications
• Title not available (Why is that?)
• Nice labeling problem for event structures: a counterexample
• 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: A counterexample to Thiagarajan's conjecture on regular event structures

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