Oriented combinatorial topology and concurrency

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionResearchpeer-review

Abstract

Higher dimensional automata (HDA) provide valuable models of concurrent processes.Much current research related to HDA aims to further develop algebraic topological notionsrequired to analyse HDA in order to determine computer scientific properties includingdeadlock, safety, unreachable states, etc. It is well-known that classical algebraic topologywill not suffice since the sequences of actions represented by (1-dimensional) paths need tobe monotone with respect to a multi-dimensional coordinate system (the coordinate systemmight be thought of as time, or its coordinates can be thought of separately as progress withrespect to particular processes). The extent to which higher dimensional paths inherit anorientation as a result of either the coordinate system, or the definition of homotopy, variesaccording to the precise notions of directed algebraic topology that are utilised. This paperconsiders an extreme position in which all higher dimensional paths, like 1-dimensionalpaths, are oriented and can only be composed when orientations are compatible. This pointof view has arisen both from software engineering considerations and from considerationsof the history of classical combinatorial topology.
LanguageEnglish
Title of host publicationPreliminary Proceedings of the Workshop on Geometry and Topology in Concurrency Theory
EditorsPatrick Cousot, Lisbeth Fajstrup, Eric Goubault, Maurice Herlihy, Alexander Kurtz, Martin Raussen, Vladimir Sassone
Place of PublicationDenmark
PublisherBRICS: Basic Research in Computer Science
Pages51-54
Number of pages4
VolumeNS-03-01
Publication statusPublished - 2003
EventGeometry and Topology in Concurrency Theory - Marseille, France
Duration: 6 Sep 20036 Sep 2003

Publication series

NameBRICS Notes Series
PublisherBRICS: Basic Research in Computer Science
No.1
Volume03
ISSN (Electronic)0909-3206

Conference

ConferenceGeometry and Topology in Concurrency Theory
Abbreviated titleGETCO'03
CountryFrance
CityMarseille
Period6/09/036/09/03

Fingerprint

Topology
Software engineering

Cite this

Johnson, M., & Verity, D. (2003). Oriented combinatorial topology and concurrency. In P. Cousot, L. Fajstrup, E. Goubault, M. Herlihy, A. Kurtz, M. Raussen, & V. Sassone (Eds.), Preliminary Proceedings of the Workshop on Geometry and Topology in Concurrency Theory (Vol. NS-03-01, pp. 51-54). (BRICS Notes Series; Vol. 03, No. 1). Denmark: BRICS: Basic Research in Computer Science.
Johnson, Michael ; Verity, Dominic. / Oriented combinatorial topology and concurrency. Preliminary Proceedings of the Workshop on Geometry and Topology in Concurrency Theory. editor / Patrick Cousot ; Lisbeth Fajstrup ; Eric Goubault ; Maurice Herlihy ; Alexander Kurtz ; Martin Raussen ; Vladimir Sassone. Vol. NS-03-01 Denmark : BRICS: Basic Research in Computer Science, 2003. pp. 51-54 (BRICS Notes Series; 1).
@inproceedings{c93f3d8ae6b94b0683a122a1ef33f59a,
title = "Oriented combinatorial topology and concurrency",
abstract = "Higher dimensional automata (HDA) provide valuable models of concurrent processes.Much current research related to HDA aims to further develop algebraic topological notionsrequired to analyse HDA in order to determine computer scientific properties includingdeadlock, safety, unreachable states, etc. It is well-known that classical algebraic topologywill not suffice since the sequences of actions represented by (1-dimensional) paths need tobe monotone with respect to a multi-dimensional coordinate system (the coordinate systemmight be thought of as time, or its coordinates can be thought of separately as progress withrespect to particular processes). The extent to which higher dimensional paths inherit anorientation as a result of either the coordinate system, or the definition of homotopy, variesaccording to the precise notions of directed algebraic topology that are utilised. This paperconsiders an extreme position in which all higher dimensional paths, like 1-dimensionalpaths, are oriented and can only be composed when orientations are compatible. This pointof view has arisen both from software engineering considerations and from considerationsof the history of classical combinatorial topology.",
author = "Michael Johnson and Dominic Verity",
year = "2003",
language = "English",
volume = "NS-03-01",
series = "BRICS Notes Series",
publisher = "BRICS: Basic Research in Computer Science",
number = "1",
pages = "51--54",
editor = "Patrick Cousot and Lisbeth Fajstrup and Eric Goubault and Maurice Herlihy and Alexander Kurtz and Martin Raussen and Vladimir Sassone",
booktitle = "Preliminary Proceedings of the Workshop on Geometry and Topology in Concurrency Theory",

}

Johnson, M & Verity, D 2003, Oriented combinatorial topology and concurrency. in P Cousot, L Fajstrup, E Goubault, M Herlihy, A Kurtz, M Raussen & V Sassone (eds), Preliminary Proceedings of the Workshop on Geometry and Topology in Concurrency Theory. vol. NS-03-01, BRICS Notes Series, no. 1, vol. 03, BRICS: Basic Research in Computer Science, Denmark, pp. 51-54, Geometry and Topology in Concurrency Theory, Marseille, France, 6/09/03.

Oriented combinatorial topology and concurrency. / Johnson, Michael; Verity, Dominic.

Preliminary Proceedings of the Workshop on Geometry and Topology in Concurrency Theory. ed. / Patrick Cousot; Lisbeth Fajstrup; Eric Goubault; Maurice Herlihy; Alexander Kurtz; Martin Raussen; Vladimir Sassone. Vol. NS-03-01 Denmark : BRICS: Basic Research in Computer Science, 2003. p. 51-54 (BRICS Notes Series; Vol. 03, No. 1).

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionResearchpeer-review

TY - GEN

T1 - Oriented combinatorial topology and concurrency

AU - Johnson, Michael

AU - Verity, Dominic

PY - 2003

Y1 - 2003

N2 - Higher dimensional automata (HDA) provide valuable models of concurrent processes.Much current research related to HDA aims to further develop algebraic topological notionsrequired to analyse HDA in order to determine computer scientific properties includingdeadlock, safety, unreachable states, etc. It is well-known that classical algebraic topologywill not suffice since the sequences of actions represented by (1-dimensional) paths need tobe monotone with respect to a multi-dimensional coordinate system (the coordinate systemmight be thought of as time, or its coordinates can be thought of separately as progress withrespect to particular processes). The extent to which higher dimensional paths inherit anorientation as a result of either the coordinate system, or the definition of homotopy, variesaccording to the precise notions of directed algebraic topology that are utilised. This paperconsiders an extreme position in which all higher dimensional paths, like 1-dimensionalpaths, are oriented and can only be composed when orientations are compatible. This pointof view has arisen both from software engineering considerations and from considerationsof the history of classical combinatorial topology.

AB - Higher dimensional automata (HDA) provide valuable models of concurrent processes.Much current research related to HDA aims to further develop algebraic topological notionsrequired to analyse HDA in order to determine computer scientific properties includingdeadlock, safety, unreachable states, etc. It is well-known that classical algebraic topologywill not suffice since the sequences of actions represented by (1-dimensional) paths need tobe monotone with respect to a multi-dimensional coordinate system (the coordinate systemmight be thought of as time, or its coordinates can be thought of separately as progress withrespect to particular processes). The extent to which higher dimensional paths inherit anorientation as a result of either the coordinate system, or the definition of homotopy, variesaccording to the precise notions of directed algebraic topology that are utilised. This paperconsiders an extreme position in which all higher dimensional paths, like 1-dimensionalpaths, are oriented and can only be composed when orientations are compatible. This pointof view has arisen both from software engineering considerations and from considerationsof the history of classical combinatorial topology.

M3 - Conference proceeding contribution

VL - NS-03-01

T3 - BRICS Notes Series

SP - 51

EP - 54

BT - Preliminary Proceedings of the Workshop on Geometry and Topology in Concurrency Theory

A2 - Cousot, Patrick

A2 - Fajstrup, Lisbeth

A2 - Goubault, Eric

A2 - Herlihy, Maurice

A2 - Kurtz, Alexander

A2 - Raussen, Martin

A2 - Sassone, Vladimir

PB - BRICS: Basic Research in Computer Science

CY - Denmark

ER -

Johnson M, Verity D. Oriented combinatorial topology and concurrency. In Cousot P, Fajstrup L, Goubault E, Herlihy M, Kurtz A, Raussen M, Sassone V, editors, Preliminary Proceedings of the Workshop on Geometry and Topology in Concurrency Theory. Vol. NS-03-01. Denmark: BRICS: Basic Research in Computer Science. 2003. p. 51-54. (BRICS Notes Series; 1).