Document Open Access Logo

A Counterexample to Thiagarajan's Conjecture on Regular Event Structures

Authors Jérémie Chalopin, Victor Chepoi

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.101.pdf
  • Filesize: 0.57 MB
  • 14 pages

Document Identifiers

Author Details

Jérémie Chalopin
Victor Chepoi

Cite AsGet BibTex

Jérémie Chalopin and Victor Chepoi. A Counterexample to Thiagarajan's Conjecture on Regular Event Structures. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 101:1-101:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ICALP.2017.101

Abstract

We provide a counterexample to a conjecture by Thiagarajan (1996 and 2002) that regular prime event structures correspond exactly to those 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 natural-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 and both conjectures can be reformulated in this framework. Namely, the domains of prime event structures correspond exactly to pointed median graphs; from a geometric point of view, these domains are in bijection with pointed CAT(0) cube complexes. A necessary condition for both conjectures to be true is that domains of respective regular event structures admit a regular nice labeling. 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 a nonpositively curved square complex whose universal cover is a CAT(0) square complex containing a particular plane with an aperiodic tiling.
Keywords
  • Discrete event structures
  • Trace automata
  • Median graphs and CAT(0) cube Complexes
  • Unfoldings and universal covers

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. F. Ardila, M. Owen, and S. Sullivant. Geodesics in CAT(0) cubical complexes. Adv. Appl. Math., 48(1):142-163, 2012. Google Scholar
  2. E. Badouel, Ph. Darondeau, and J.-C. Raoult. Context-free event domains are recognizable. Inf. Comput., 149(2):134-172, 1999. Google Scholar
  3. H.-J. Bandelt and V. Chepoi. Metric graph theory and geometry: a survey. In J. E. Goodman, J. Pach, and R. Pollack, editors, Surveys on Discrete and Computational Geometry: Twenty Years Later, volume 453 of Contemp. Math., pages 49-86. AMS, Providence, RI, 2008. Google Scholar
  4. H.-J. Bandelt and J. Hedlíková. Median algebras. Discr. Math., 45(1):1-30, 1983. Google Scholar
  5. J.-P. Barthélemy and J. Constantin. Median graphs, parallelism and posets. Discr. Math., 111(1-3):49-63, 1993. Google Scholar
  6. M. A. Bednarczyk. Categories of Asynchronous Systems. PhD thesis, University of Sussex, 1987. Google Scholar
  7. M. R. Bridson and A. Haefliger. Metric Spaces of Non-Positive Curvature, volume 319 of Grundlehren der mathematischen Wissenschaften. Springer-Verlag, Berlin, 1999. Google Scholar
  8. J. Chalopin and V. Chepoi. A counterexample to Thiagarajan’s conjecture. arXiv preprint, 2016. URL: https://arxiv.org/abs/1605.08288, URL: http://arxiv.org/abs/1605.08288.
  9. V. Chepoi. Graphs of some CAT(0) complexes. Adv. Appl. Math., 24(2):125-179, 2000. Google Scholar
  10. V. Chepoi. Nice labeling problem for event structures: a counterexample. SIAM J. Comput., 41(4):715-727, 2012. Google Scholar
  11. D.Ž. Djoković. Distance-preserving subgraphs of hypercubes. J. Comb. Theory, Ser. B, 14(3):263-267, 1973. Google Scholar
  12. M. Gromov. Hyperbolic groups. In S. M. Gersten, editor, Essays in group theory, volume 8 of Math. Sci. Res. Inst. Publ., pages 75-263. Springer, New York, 1987. Google Scholar
  13. A. Hatcher. Algebraic Topology. Cambridge University Press, Cambridge,, 2002. Google Scholar
  14. J. Kari and P. Papasoglu. Deterministic aperiodic tile sets. GAFA, Geom. Funct. Anal., 9(2):353-369, 1999. Google Scholar
  15. V. Lukkarila. The 4-way deterministic tiling problem is undecidable. Theor. Comput. Sci., 410(16):1516-1533, 2009. Google Scholar
  16. R. Morin. Concurrent automata vs. asynchronous systems. In MFCS 2005, volume 3618 of LNCS, pages 686-698. Springer, 2005. Google Scholar
  17. D. E. Muller and P. E. Schupp. The theory of ends, pushdown automata, and second-order logic. Theor. Comput. Sci., 37:51-75, 1985. Google Scholar
  18. M. Nielsen, G. D. Plotkin, and G. Winskel. Petri nets, event structures and domains, part I. Theor. Comput. Sci., 13:85-108, 1981. Google Scholar
  19. M. Nielsen, G. Rozenberg, and P. S. Thiagarajan. Transition systems, event structures and unfoldings. Inf. Comput., 118(2):191-207, 1995. Google Scholar
  20. M. Nielsen and P. S. Thiagarajan. Regular event structures and finite Petri nets: the conflict-free case. In ICATPN 2002, volume 2360 of LNCS, pages 335-351. Springer, 2002. Google Scholar
  21. M. Roller. Poc sets, median algebras and group actions. Technical report, Univ. of Southampton, 1998. Google Scholar
  22. B. Rozoy and P. S. Thiagarajan. Event structures and trace monoids. Theor. Comput. Sci., 91(2):285-313, 1991. Google Scholar
  23. M. Sageev. Ends of group pairs and non-positively curved cube complexes. Proc. London Math. Soc., s3-71(2):585-617, 1995. Google Scholar
  24. M. Sageev. CAT(0) cube complexes and groups. In M. Bestvina, M. Sageev, and K. Vogtmann, editors, Geometric Group Theory, volume 21 of IAS/Park City Mathematics Series, pages 6-53. AMS, Institute for Advanced Study, 2012. Google Scholar
  25. E. W. Stark. Connections between a concrete and an abstract model of concurrent systems. In Mathematical Foundations of Programming Semantics 1989, volume 442 of LNCS, pages 53-79. Springer, 1989. Google Scholar
  26. P. S. Thiagarajan. Regular trace event structures. Technical Report BRICS RS-96-32, Computer Science Department, Aarhus University, Aarhus, Denmark, 1996. Google Scholar
  27. P. S. Thiagarajan. Regular event structures and finite Petri nets: A conjecture. In Formal and Natural Computing, volume 2300 of LNCS, pages 244-256. Springer, 2002. Google Scholar
  28. P. M. Winkler. Isometric embedding in products of complete graphs. Discr. Appl. Math., 7(2):221-225, 1984. Google Scholar
  29. G. Winskel. Events in computation. PhD thesis, Edinburgh Univ., 1980. Google Scholar
  30. G. Winskel and M. Nielsen. Models for concurrency. In S. Abramsky, Dov M. Gabbay, and T. S. E. Maibaum, editors, Handbook of Logic in Computer Science (Vol. 4), pages 1-148. Oxford University Press, 1995. Google Scholar
  31. D. T. Wise. Non-positively curved squared complexes, aperiodic tilings, and non-residually finite groups. PhD thesis, Princeton University, 1996. Google Scholar
  32. D. T. Wise. Complete square complexes. Comment. Math. Helv, 82(4):683-724, 2007. Google Scholar
  33. D. T. Wise. From Riches to Raags: 3-manifolds, Right-angled Artin Groups, and Cubical Geometry, volume 117 of CBMS Regional Conference Series in Mathematics. AMS, Providence, RI, 2012. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact