Skip to Main content Skip to Navigation
Conference papers

Trees in Partial Higher Dimensional Automata

Abstract : In this paper, we give a new definition of partial Higher Dimension Automata using lax functors. This definition is simpler and more natural from a categorical point of view, but also matches more clearly the intuition that pHDA are Higher Dimensional Automata with some missing faces. We then focus on trees. Originally, for example in transition systems, trees are defined as those systems that have a unique path property. To understand what kind of unique property is needed in pHDA, we start by looking at trees as colimits of paths. This definition tells us that trees are exactly the pHDA with the unique path property modulo a notion of homotopy, and without any shortcuts. This property allows us to prove two interesting characterisations of trees: trees are exactly those pHDA that are an unfolding of another pHDA; and trees are exactly the cofibrant objects, much as in the language of Quillen’s model structure. In particular, this last characterisation gives the pre- misses of a new understanding of concurrency theory using homotopy theory.
Complete list of metadata

https://hal.inria.fr/hal-02374933
Contributor : Jérémy Dubut <>
Submitted on : Thursday, November 21, 2019 - 5:41:20 PM
Last modification on : Monday, May 17, 2021 - 12:00:05 PM

Links full text

Identifiers

Citation

Jérémy Dubut. Trees in Partial Higher Dimensional Automata. Foundations of Software Science and Computation Structures - 22nd International Conference, FOSSACS 2019, Apr 2019, Prague, Czech Republic. pp.224-241, ⟨10.1007/978-3-030-17127-8_13⟩. ⟨hal-02374933⟩

Share

Metrics

Record views

62