A counterexample to Thiagarajan's conjecture on regular event structures

DOI10.1016/j.jcss.2020.05.001zbMath1442.68131OpenAlexW2963488576WikidataQ123010995 ScholiaQ123010995MaRDI QIDQ2186822

Jérémie Chalopin, Victor Chepoi

Publication date: 9 June 2020

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/7419/

zbMATH Keywords

aperiodic tilingsmedian graphsuniversal coversCAT(0) cube complexesevent domainsregular event structurestrace labelingsvirtually special cube complexes

Mathematics Subject Classification ID

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

Related Items

First-order logic axiomatization of metric graph theory, Distance and routing labeling schemes for cube-free median graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The virtual Haken conjecture (with an appendix by Ian Agol, Daniel Groves and Jason Manning).
• On embeddings of CAT(0) cube complexes into products of trees via colouring their hyperplanes
• Geodesics in CAT(0) cubical complexes
• Median graphs, parallelism and posets
• Isometric embedding in products of complete graphs
• The 4-way deterministic tiling problem is undecidable
• The theory of ends, pushdown automata, and second-order logic
• Petri nets, event structures and domains. I
• Event structures and trace monoids
• Context-free event domains are recognizable
• Deterministic aperiodic tile sets
• Concrete domains
• Median algebras
• Transition systems, event structures, and unfoldings
• A combination theorem for special cube complexes.
• Graphs of some CAT(0) complexes
• On the recognition problem for virtually special cube complexes
• Complete square complexes.
• Special cube complexes
• Probabilistic event structures and domains
• Undecidability and nonperiodicity for tilings of the plane
• Distance-preserving subgraphs of hypercubes
• Weak hyperbolicity of cube complexes and quasi-arboreal groups
• Nice Labeling Problem for Event Structures: A Counterexample
• Metric Ternary Distributive Semi-Lattices
• Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
• Embedding Topological Median Algebras in Products of Dendrons
• Ends of Group Pairs and Non-Positively Curved Cube Complexes
• 1-Safe Petri Nets and Special Cube Complexes
• A counterexample to Thiagarajan's conjecture on regular event structures
• Mathematical Foundations of Computer Science 2005
• The undecidability of the domino problem
• Connections between a concrete and an abstract model of concurrent systems