Search

Higher Dimensional Automata (HDA) are higher dimensional relatives to transition systems in concurrency theory taking into account to which degree various actions commute. Mathematically, they take the form of labelled cubical complexes. It is important to know, and challenging from a geometric/topological perspective, whether the space of directed paths (executions in the model) between two vertices (states) is connected; more generally, to estimate higher connectedness of these path spaces. This paper presents an approach for such an estimation for particularly simple HDA modelling the access of a number of processors to a number of resources with given limited capacity each. It defines a spare capacity for a concurrent program with prescribed periods of access of the processors to the resources. It shows that the connectedness of spaces of directed paths can be estimated (from above) by spare capacities. Moreover, spare capacities can also be used to detect deadlocks and critical states in such a HDA. The key theoretical ingredient is a transition from the calculation of local connectedness bounds (of the upper links of vertices of an HDA) to global ones by applying a version of the nerve lemma due to Anders Bj\"orner.

Directed paths have been used by several authors to describe concurrent executions of a program. Spaces of directed paths in an appropriate state space contain executions with all possible legal schedulings. It is interesting to investigate whether one obtains different topological properties of such a space of executions if one restricts attention to schedulings with "nice" properties, eg involving synchronizations. This note shows that this is not the case, ie that one may operate with nice schedulings without inflicting any harm. Several of the results in this note had previously been obtained by Ziemianski. We attempt to make them accessible for a wider audience by giving an easier proof for these findings by an application of quite elementary results from algebraic topology; notably the nerve lemma., Comment: 21 pages, 9 figures

A directed space is a topological space $X$ together with a subspace $\vec{P}(X)\subset X^I$ of \emph{directed} paths on $X$. A symmetry of a directed space should therefore respect both the topology of the underlying space and the topology of the associated spaces $\vec{P}(X)_-^+$ of directed paths between a source ($-$) and a target ($+$) - up to homotopy. If it is, moreover, homotopic to the identity map -- in a directed sense -- such a symmetry will be called an inessential d-map, and the paper explores the algebra and topology of inessential d-maps. Comparing two d-spaces $X$ and $Y$ "up to symmetry" yields the notion of a directed homotopy equivalence between them. Under appropriate conditions, all directed homotopy equivalences are shown to satisfy a 2-out-of-3 property. Our notion of directed homotopy equivalence does not agree completely with the one defined in \cite{Goubault:17} and \cite{GFS:18}; the deviation is motivated by examples. Nevertheless, directed topological complexity, introduced in \cite{GFS:18} is shown to be invariant under our notion of directed homotopy equivalence. Finally, we show that directed homotopy equivalences result in isomorphisms on the pair component categories of directed spaces introduced in \cite{Raussen:18}.

The notion of a homotopy flow on a directed space was introduced in \cite{Raussen:07} as a coherent tool for comparing spaces of directed paths between pairs of points in that space with each other. If all parameter directed maps preserve the homotopy type of path spaces, such a flow (and these parameter maps) are called inessential. For a directed space, one may consider various categories whose objects are pairs of reachable points and whose morphisms may be induced by these inessential d-maps. Localization with respect to subcategories with these inessential d-maps as morphisms can be combined with a path space functor into the homotopy category, the quotient pair component category has as objects pair components along which the homotopy type is invariant -- for a coherent and transparent reason. This paper follows up \cite{FGHR:04,GH:07,Raussen:07} and removes some of the restrictions for their applicability. If one uses homology equivalence instead of homotopy equivalence as the basic relation, it yields an alternative to computable versions of "natural homology" introduced in \cite{DGG:15} and elaborated in \cite{Dubut:17}. It refines, for good and for evil, the stable components introduced and investigated in \cite{Ziemianski:18}.

The paper addresses certain topological aspects of Dijkstra's PV-model for parallel computations in concurrency theory. The main result is a computation of the homology of the trace space associated with PV-programs in which access and release of every resource happen without time delay., Comment: 21 pages, 4 figures. To be published in the collection of papers "A Journey through Discrete Mathematics. A Tribute to Jiri Matousek" edited by Martin Loebl, Jaroslav Nesetril and Robin Thomas, due to be published by Springer