Partial Higher-dimensional Automata

Authors Uli Fahrenberg, Axel Legay



PDF
Thumbnail PDF

File

LIPIcs.CALCO.2015.101.pdf
  • Filesize: 470 kB
  • 15 pages

Document Identifiers

Author Details

Uli Fahrenberg
Axel Legay

Cite AsGet BibTex

Uli Fahrenberg and Axel Legay. Partial Higher-dimensional Automata. In 6th Conference on Algebra and Coalgebra in Computer Science (CALCO 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 35, pp. 101-115, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.CALCO.2015.101

Abstract

We propose a generalization of higher-dimensional automata, partial HDA. Unlike HDA, and also extending event structures and Petri nets, partial HDA can model phenomena such as priorities or the disabling of an event by another event. Using open maps and unfoldings, we introduce a natural notion of (higher-dimensional) bisimilarity for partial HDA and relate it to history-preserving bisimilarity and split bisimilarity. Higher-dimensional bisimilarity has a game characterization and is decidable in polynomial time.
Keywords
  • higher-dimensional automata
  • bisimulation

Metrics

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

References

  1. Marek A. Bednarczyk. Categories of asynchronous systems. PhD thesis, University of Sussex, UK, 1987. Google Scholar
  2. Jan A. Bergstra and Jan W. Klop. Process algebra for synchronous communication. Inf. Cont., 60(1-3):109-137, 1984. Google Scholar
  3. Ronald Brown and Philip J. Higgins. \afirstOn the algebra of cubes. J. Pure Appl. Alg., 21:233-260, 1981. Google Scholar
  4. Uli Fahrenberg. A category of higher-dimensional automata. In FOSSACS, volume 3441 of Lect. Notes Comput. Sci., pages 187-201. Springer, 2005. Google Scholar
  5. Uli Fahrenberg. Higher-Dimensional Automata from a Topological Viewpoint. PhD thesis, Aalborg University, Denmark, 2005. Google Scholar
  6. Uli Fahrenberg and Axel Legay. History-preserving bisimilarity for higher-dimensional automata via open maps. Electr. Notes Theor. Comput. Sci., 298:165-178, 2013. Google Scholar
  7. Uli Fahrenberg and Axel Legay. Homotopy bisimilarity for higher-dimensional automata. CoRR, abs/1409.5865, 2014. Google Scholar
  8. Lisbeth Fajstrup. Dipaths and dihomotopies in a cubical complex. Adv. Appl. Math., 35(2):188-206, 2005. Google Scholar
  9. Lisbeth Fajstrup, Éric Goubault, Emmanuel Haucourt, Samuel Mimram, and Martin Raußen. Trace spaces: An efficient new technique for state-space reduction. In Helmut Seidl, editor, ESOP, volume 7211 of Lecture Notes in Computer Science, pages 274-294. Springer, 2012. Google Scholar
  10. Lisbeth Fajstrup, Martin Raussen, and Éric Goubault. Algebraic topology and concurrency. Theor. Comput. Sci., 357(1-3):241-278, 2006. Google Scholar
  11. Philippe Gaucher. Homotopical interpretation of globular complex by multipointed d-space. Theory Appl. Categories, 22:588-621, 2009. Google Scholar
  12. Philippe Gaucher. Towards a homotopy theory of higher dimensional transition systems. Theory Appl. Categories, 25:295-341, 2011. Google Scholar
  13. Éric Goubault. Geometry and concurrency: A user’s guide. Math. Struct. Comput. Sci., 10(4):411-425, 2000. Google Scholar
  14. Éric Goubault and Thomas P. Jensen. Homology of higher dimensional automata. In Rance Cleaveland, editor, CONCUR, volume 630 of Lect. Notes Comput. Sci., pages 254-268. Springer, 1992. Google Scholar
  15. Éric Goubault and Samuel Mimram. Formal relationships between geometrical and classical models for concurrency. Electronic Notes in Theoretical Computer Science, 283:77-109, 2012. Google Scholar
  16. Marco Grandis. Directed algebraic topology: models of non-reversible worlds. New mathematical monographs. Cambridge Univ. Press, 2009. Google Scholar
  17. André Joyal, Mogens Nielsen, and Glynn Winskel. Bisimulation from open maps. Inf. Comput., 127(2):164-185, 1996. Google Scholar
  18. Dexter Kozen. Automata and Computability. Undergraduate Texts in Computer Science. Springer, 1997. Google Scholar
  19. Robin Milner. Communication and Concurrency. Prentice Hall, 1989. Google Scholar
  20. Mogens Nielsen, Gordon D. Plotkin, and Glynn Winskel. Petri nets, event structures and domains, part I. Theor. Comput. Sci., 13:85-108, 1981. Google Scholar
  21. David M.R. Park. Concurrency and automata on infinite sequences. In Peter Deussen, editor, IFIP TCS, volume 104 of Lect. Notes Comput. Sci., pages 167-183. Springer, 1981. Google Scholar
  22. Carl A. Petri. Kommunikation mit Automaten. Bonn: Institut für Instrumentelle Mathematik, Schriften des IIM Nr. 2, 1962. Google Scholar
  23. Vaughan Pratt. Modeling concurrency with geometry. In POPL, pages 311-322. ACM Press, 1991. Google Scholar
  24. Cristian Prisacariu. The glory of the past and geometrical concurrency. In Andrei Voronkov, editor, Turing-100, volume 10 of EPiC, pages 252-267. EasyChair, 2012. Google Scholar
  25. Alexander M. Rabinovich and Boris A. Trakhtenbrot. Behavior structures and nets. Fund. Inf., 11(4):357-403, 1988. Google Scholar
  26. Jean-Pierre Serre. Homologie singulière des espaces fibrés. PhD thesis, Ecole Normale Supérieure, 1951. Google Scholar
  27. Mike W. Shields. Concurrent machines. The Computer Journal, 28(5):449-465, 1985. Google Scholar
  28. Colin Stirling. Modal and temporal logics for processes. In Proc. Banff Higher Order Workshop, volume 1043 of Lect. Notes Comput. Sci., pages 149-237. Springer, 1995. Google Scholar
  29. Rob J. van Glabbeek. Bisimulations for higher dimensional automata. Email message, June 1991. URL: http://theory.stanford.edu/~rvg/hda.
  30. Rob J. van Glabbeek. \afirstOn the expressiveness of higher dimensional automata. Theor. Comput. Sci., 356(3):265-290, 2006. Google Scholar
  31. Rob J. van Glabbeek and Ursula Goltz. Refinement of actions and equivalence notions for concurrent systems. Acta Inf., 37(4/5):229-327, 2001. Google Scholar
  32. Rob J. van Glabbeek and Gordon D. Plotkin. Configuration structures, event structures and petri nets. Theor. Comput. Sci., 410(41):4111-4159, 2009. Google Scholar
  33. Rob J. van Glabbeek and Frits W. Vaandrager. Petri net models for algebraic theories of concurrency. In J. W. de Bakker, A. J. Nijman, and Philip C. Treleaven, editors, PARLE (2), volume 259 of Lect. Notes Comput. Sci., pages 224-242. Springer, 1987. Google Scholar
  34. Rob J. van Glabbeek and Frits W. Vaandrager. The difference between splitting in n and n+1. Inf. Comput., 136(2):109-142, 1997. Google Scholar
  35. Glynn Winskel and Mogens Nielsen. Models for concurrency. In Samson Abramsky, Dov M. Gabbay, and Thomas S.E. Maibaum, editors, Handbook of Logic in Computer Science, volume 4. Clarendon Press, Oxford, 1995. 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