Hostname: page-component-78c5997874-g7gxr Total loading time: 0 Render date: 2024-11-09T08:24:28.617Z Has data issue: false hasContentIssue false
  • English
  • Français

Languages of higher-dimensional automata

Published online by Cambridge University Press:  18 October 2021

Uli Fahrenberg Open the ORCID record for Uli Fahrenberg [Opens in a new window] ,
Christian Johansen Open the ORCID record for Christian Johansen [Opens in a new window] ,
Georg Struth Open the ORCID record for Georg Struth [Opens in a new window]  and
Krzysztof Ziemiański Open the ORCID record for Krzysztof Ziemiański [Opens in a new window]
Uli Fahrenberg*
Affiliation:
École Polytechnique, Palaiseau, France
Christian Johansen
Affiliation:
Norwegian University of Science and Technology, Norway
Georg Struth
Affiliation:
University of Sheffield, UK
Krzysztof Ziemiański
Affiliation:
University of Warsaw, Poland
*
*Corresponding author. Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We introduce languages of higher-dimensional automata (HDAs) and develop some of their properties. To this end, we define a new category of precubical sets, uniquely naturally isomorphic to the standard one, and introduce a notion of event consistency. HDAs are then finite, labeled, event-consistent precubical sets with distinguished subsets of initial and accepting cells. Their languages are sets of interval orders closed under subsumption; as a major technical step, we expose a bijection between interval orders and a subclass of HDAs. We show that any finite subsumption-closed set of interval orders is the language of an HDA, that languages of HDAs are closed under binary unions and parallel composition, and that bisimilarity implies language equivalence.

Keywords

Higher-dimensional automatonconcurrency theorypomsetdirected topology
Type
Paper
Information
Mathematical Structures in Computer Science , Volume 31 , Issue 5 , May 2021 , pp. 575 - 613
Check for updates
Copyright
© The Author(s), 2021. Published by Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Awodey, S. (2018). A cubical model of homotopy type theory. Annals of Pure and Applied Logic 169 (12) 1270–1294.CrossRefGoogle Scholar
Bednarczyk, M. A. (1987). Categories of Asynchronous Systems. PhD thesis, University of Sussex, UK.Google Scholar
Bezem, M., Coquand, T. and Huber, S. (2013). A model of type theory in cubical sets. In: Matthes, R. and Schubert, A. (eds.) TYPES, vol. 26. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 107–128.Google Scholar
Bezem, M., Coquand, T. and Huber, S. (2019). The univalence axiom in cubical sets. Journal of Automated Reasoning 63 (2) 159–171.CrossRefGoogle Scholar
Ésik, Z. and Németh, Z. L. (2004). Higher dimensional automata. Journal of Automata, Languages and Combinatorics 9 (1) 3–29.Google Scholar
Fahrenberg, U. (2005a). Bisimulation for higher-dimensional automata. A geometric interpretation. Research report R-2005-01, Department of Mathematical Sciences, Aalborg University, 2005. Extended version of [Fahrenberg, 2005c].Google Scholar
Fahrenberg, U. (2005b). Higher-Dimensional Automata from a Topological Viewpoint. PhD thesis, Aalborg University, Denmark.Google Scholar
Fahrenberg, U. (2005c) A category of higher-dimensional automata. In: Sassone, V. (ed.) FoSSaCS, vol. 3441. Lecture Notes in Computer Science. Springer, 187–201. See also [Fahrenberg, 2005a].CrossRefGoogle Scholar
Fahrenberg, U., Johansen, C., Struth, G. and Thapa, R. B. (2020). Generating posets beyond N. In: Fahrenberg, U., Jipsen, P. and Winter, M. (eds.) RAMiCS, vol. 12062. Lecture Notes in Computer Science. Springer, 82–99.CrossRefGoogle Scholar
Fahrenberg, U., Johansen, C., Trotter, C. and Ziemiański, K. (2021). Sculptures in concurrency. Logical Methods in Computer Science 17 (2).Google Scholar
Fajstrup, L. (2005). Dipaths and dihomotopies in a cubical complex. Advances in Applied Mathematics 35 (2) 188–206.CrossRefGoogle Scholar
Fajstrup, L., Goubault, E., Haucourt, E., Mimram, S. and Raussen, M. (2016). Directed Algebraic Topology and Concurrency. Springer, 2016.CrossRefGoogle Scholar
Fajstrup, L., Raussen, M. and Goubault, É. (2006). Algebraic topology and concurrency. Theoretical Computer Science 357 (1-3) 241–278.CrossRefGoogle Scholar
Fanchon, J. and Morin, R. (2002). Regular sets of pomsets with autoconcurrency. In: Brim, L., Jančar, P., Křetínský, M. and Kučera, A. (eds.) CONCUR, vol. 2421 of Lecture Notes in Computer Science. Springer, 402–417.CrossRefGoogle Scholar
Fishburn, P. C. (1970). Intransitive indifference with unequal indifference intervals. Journal of Mathematical Psychology 7 (1) 144–149.CrossRefGoogle Scholar
Fishburn, P. C. (1985). Interval Orders and Interval Graphs: A Study of Partially Ordered Sets. Wiley.CrossRefGoogle Scholar
Gischer, J. L. (1988). The equational theory of pomsets. Theoretical Computer Science 61 199–224.CrossRefGoogle Scholar
Grabowski, J. (1981). On partial languages. Fundamenta Informaticae 4 (2) 427.CrossRefGoogle Scholar
Grandis, M. (2009). Directed Algebraic Topology: Models of Non-Reversible Worlds . New Mathematical Monographs. Cambridge Univ. Press.Google Scholar
Grandis, M. and Mauri, L. (1990). Cubical sets and their site. Theory and Applications of Categories 11 (8) 185–211.Google Scholar
Herlihy, M. and Wing, J. M. (1990). Linearizability: A correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems 12 (3) 463–492.CrossRefGoogle Scholar
Janicki, R. and Koutny, M. (1993). Structure of concurrency. Theoretical Computer Science 112 (1) 5–52.CrossRefGoogle Scholar
Janicki, R. and Yin, X. (2017). Modeling concurrency with interval traces. Information and Computation 253 78–108.CrossRefGoogle Scholar
Johansen, C. (2015). ST-structures. Journal of Logical Algebra Methods Programming 85 (6) 1201–1233.CrossRefGoogle Scholar
Joyal, A., Nielsen, M. and Winskel, G. (1996). Bisimulation from open maps. Information and Computation 127 (2) 164–185.CrossRefGoogle Scholar
Lamport, L. (1986a). The mutual exclusion problem: Part I - A theory of interprocess communication. Journal of ACM 33 (2) 313–326.CrossRefGoogle Scholar
Lamport, L. (1986b). On interprocess communication. Part I: Basic formalism. Distributed Computing 1 (2) 77–85.CrossRefGoogle Scholar
Lane, S. M. (1998). Categories for the Working Mathematician, Second edition. Springer.Google Scholar
Milner, R. (1989). Communication and Concurrency. Prentice Hall.Google Scholar
Nielsen, M., Plotkin, G. D. and Winskel, G. (1981). Petri nets, event structures and domains, part I. Theoretical Computer Science 13 85–108.CrossRefGoogle Scholar
nLab authors. Simplex category (2021).Google Scholar
Petri, C. A. (1962). Kommunikation mit Automaten. Number 2 in Schriften des IIM. Institut für Instrumentelle Mathematik, Bonn,.Google Scholar
Pratt, V. R. (1986). Modeling concurrency with partial orders. Journal of Parallel Programming 15 (1), 33–71.CrossRefGoogle Scholar
Pratt, V. R. (1991). Modeling concurrency with geometry. In: POPL, New York City, ACM Press, 311–322.CrossRefGoogle Scholar
Pratt, V. R. (1995). Chu spaces and their interpretation as concurrent objects. In: van Leeuwen, J. (ed.) Computer Science Today: Recent Trends and Developments, vol. 1000. Lecture Notes in Computer Science. Springer, 392–405.CrossRefGoogle Scholar
Pratt, V. R. (2000). Higher dimensional automata revisited. Mathematical Structures in Computer Science 10 (4) 525–548.CrossRefGoogle Scholar
Pratt, V. R. (2003). Transition and cancellation in concurrency and branching time. Mathematical Structures in Computer Science 13 (4) 485–529.CrossRefGoogle Scholar
Serre, J.-P. (1951). Homologie singulière des espaces fibrés. PhD thesis, Ecole Normale Supérieure, Paris, France.CrossRefGoogle Scholar
Shields, M. W. (1985). Concurrent machines. Computer Journal 28 (5) 449–465.CrossRefGoogle Scholar
van Glabbeek, R. J. (1991). Bisimulations for higher dimensional automata. Email message.Google Scholar
van Glabbeek, R. J. (1996). History preserving process graphs. Unpublished draft.Google Scholar
van Glabbeek, R. J. (2006a). On the expressiveness of higher dimensional automata. Theoretical Computer Science 356 (3) 265–290. See also [van Glabbeek, 2006b].CrossRefGoogle Scholar
van Glabbeek, R. J. (2006b). Erratum to “On the expressiveness of higher dimensional automata”. Theoretical Computer Science 368 (1–2) 168–194.CrossRefGoogle Scholar
van Glabbeek, R. J. and Goltz, U. (2001). Refinement of actions and equivalence notions for concurrent systems. Acta Informatica 37 (4/5) 229–327.CrossRefGoogle Scholar
van Glabbeek, R. J. and Plotkin, G. D. (1995). Configuration structures. In: LICS. IEEE Computer Society, 199–209.CrossRefGoogle Scholar
van Glabbeek, R. J. and Plotkin, G. D. (2009). Configuration structures, event structures and Petri nets. Theoretical Computer Science 410 (41) 4111–4159.CrossRefGoogle Scholar
Vogler, W. (1991). Failures semantics based on interval semiwords is a congruence for refinement. Distributed Computing 4 139–162.CrossRefGoogle Scholar
Vogler, W. (1992). Modular Construction and Partial Order Semantics of Petri Nets, vol. 625. Lecture Notes in Computer Science. Springer.CrossRefGoogle Scholar
Winkowski, J. (1977). An algebraic characterization of the behaviour of non-sequential systems. Information Processing Letters 6 (4) 105–109.CrossRefGoogle Scholar
Winskel, G. and Nielsen, M. (1995). Models for concurrency. In: Abramsky, S., Gabbay, D. M. and Maibaum, T. S.E. (eds.) Handbook of Logic in Computer Science, vol. 4. Oxford, Clarendon Press.Google Scholar
Ziemiański, K. (2017). Spaces of directed paths on pre-cubical sets. Applicable Algebra in Engineering, Communication and Computing 28 (6) 497–525.CrossRefGoogle Scholar
Ziemiański, K. (2020). Spaces of directed paths on pre-cubical sets II. Journal of Applied and Computational Topology 4 45–78.CrossRefGoogle Scholar