Strictifying and taming directed paths in higher dimensional automata

DOI10.1017/S0960129521000128MaRDI QIDQ5156774zbMATH OpenFDO

Authors Martin Raussen

Publication date 11 October 2021

Published in Mathematical Structures in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2006.05797

zbMATH Keywords

d-pathhigher-dimensional automatahomotopy equivalencenerve lemmaparallelserialstrictnesstameness

Mathematics Subject Classification ID

Simplicial sets and complexes in algebraic topology (55U10) Algebraic theory of languages and automata (68Q70) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Abstract: 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.

Recommendations

• Directed algebraic topology and concurrency. With a foreword by Maurice Herlihy and a preface by Samuel Mimram
• Execution spaces for simple higher dimensional automata
• Spaces of directed paths on pre-cubical sets
• scientific article; zbMATH DE number 2218901
• Simplicial models of trace spaces

Cites work

• Combinatorial algebraic topology
• Directed algebraic topology and concurrency. With a foreword by Maurice Herlihy and a preface by Samuel Mimram
• Directed algebraic topology. Models of non-reversible worlds
• Erratum to ``On the expressiveness of higher dimensional automata
• Higher algebraic K-theory: I
• Homology of spaces of directed paths on Euclidean cubical complexes
• Homotopy Type Comparison of a Space with Complexes Associated with its Open Covers
• scientific article; zbMATH DE number 1226952 (Why is no real title available?)
• scientific article; zbMATH DE number 2103273 (Why is no real title available?)
• scientific article; zbMATH DE number 863503 (Why is no real title available?)
• On the imbedding of systems of compacta in simplicial complexes
• Partial higher-dimensional automata
• Pomset Languages of Finite Step Transition Systems
• Spaces of directed paths on pre-cubical sets
• Spaces of directed paths on pre-cubical sets II
• Sur la forme des espaces topologiques et sur les points fixes des représentations
• Sur les théorèmes de de Rham
• Trace spaces in a pre-cubical complex
• Trees in partial higher dimensional automata

Cited in

(6)

• Connectivity of spaces of directed paths in geometric models for concurrent computation
• Simplicial models for trace spaces. II: General higher dimensional automata
• scientific article; zbMATH DE number 2016847 (Why is no real title available?)
• scientific article; zbMATH DE number 1868895 (Why is no real title available?)
• Towards directed collapsibility (research)
• Regular directed path and Moore flow

This page was built for publication: Strictifying and taming directed paths in higher dimensional automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5156774)