English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

We provide a counterexample to a conjecture by Thiagarajan (1996 and 2002)that regular event structures correspond exactly to event structures obtainedas unfoldings of finite 1-safe Petri nets. The same counterexample is used todisprove a closely related conjecture by Badouel, Darondeau, and Raoult (1999)that domains of regular event structures with bounded $\natural$-cliques arerecognizable by finite trace automata. Event structures, trace automata, andPetri nets are fundamental models in concurrency theory. There exist niceinterpretations of these structures as combinatorial and geometric objects.Namely, from a graph theoretical point of view, the domains of prime eventstructures 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 ofregular event structures (with bounded $\natural$-cliques) admit a regular nicelabeling. To disprove these conjectures, we describe a regular event domain(with bounded $\natural$-cliques) that does not admit a regular nice labeling.Our counterexample is derived from an example by Wise (1996 and 2007) of anonpositively curved square complex whose universal cover is a CAT(0) squarecomplex containing a particular plane with an aperiodic tiling. We prove thatother counterexamples to Thiagarajan's conjecture arise from aperiodic 4-waydeterministic tile sets of Kari and Papasoglu (1999) and Lukkarila (2009).  On the positive side, using breakthrough results by Agol (2013) and Haglundand Wise (2008, 2012) from geometric group theory, we prove that Thiagarajan'sconjecture is true for regular event structures whose domains occur asprincipal filters of hyperbolic CAT(0) cube complexes which are universalcovers of finite nonpositively curved cube complexes.

A counterexample to Thiagarajan's conjecture on regular event structures