DROPS

Document

Applications of Combinatorial Topology to Computer Science (Dagstuhl Seminar 12121)

Authors: Lisbeth Fajstrup, Dmitry Feichtner-Kozlov, and Maurice Herlihy

Published in: Dagstuhl Reports, Volume 2, Issue 3 (2012)

Abstract

This report documents the program of Dagstuhl Seminar 12121 "Applications of Combinatorial Topology to Computer Science". The seminar brought together researchers working on applications of combinatorial topology to various fields of computer science. The goal was to foster communication across these fields by providing researchers in each field the opportunity to explain their research programs to the others. The fields covered included distributed computing, persistent homology, semantics of concurrency, and sensor networks.

Cite as

Lisbeth Fajstrup, Dmitry Feichtner-Kozlov, and Maurice Herlihy. Applications of Combinatorial Topology to Computer Science (Dagstuhl Seminar 12121). In Dagstuhl Reports, Volume 2, Issue 3, pp. 50-66, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@Article{fajstrup_et_al:DagRep.2.3.50,
  author =	{Fajstrup, Lisbeth and Feichtner-Kozlov, Dmitry and Herlihy, Maurice},
  title =	{{Applications of Combinatorial Topology to Computer Science (Dagstuhl Seminar 12121)}},
  pages =	{50--66},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2012},
  volume =	{2},
  number =	{3},
  editor =	{Fajstrup, Lisbeth and Feichtner-Kozlov, Dmitry and Herlihy, Maurice},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.2.3.50},
  URN =		{urn:nbn:de:0030-drops-35363},
  doi =		{10.4230/DagRep.2.3.50},
  annote =	{Keywords: Combinatorial topology, Distributed computing, Persistent homology, Program semantics, Sensor networks}
}

Document

DOI: 10.4230/DagSemProc.04351.13

Dihomotopy Classes of Dipaths in the Geometric Realization of a Cubical Set: from Discrete to Continuous and back again

Authors: Lisbeth Fajstrup

Published in: Dagstuhl Seminar Proceedings, Volume 4351, Spatial Representation: Discrete vs. Continuous Computational Models (2005)

Abstract

The geometric models of concurrency - Dijkstra's PV-models and V. Pratt's Higher Dimensional Automata - rely on a translation of discrete or algebraic information to geometry. In both these cases, the translation is the geometric realisation of a semi cubical complex, which is then a locally partially ordered space, an lpo space. The aim is to use the algebraic topology machinery, suitably adapted to the fact that there is a preferred time direction. Then the results - for instance dihomotopy classes of dipaths, which model the number of inequivalent computations should be used on the discrete model and give the corresponding discrete objects. We prove that this is in fact the case for the models considered: Each dipath is dihomottopic to a combinatorial dipath and if two combinatorial dipaths are dihomotopic, then they are combinatorially equivalent. Moreover, the notions of dihomotopy (LF., E. Goubault, M. Raussen) and d-homotopy (M. Grandis) are proven to be equivalent for these models - hence the Van Kampen theorem is available for dihomotopy. Finally we give an idea of how many spaces have a local po-structure given by cubes. The answer is, that any cubicalized space has such a structure after at most one subdivision. In particular, all triangulable spaces have a cubical local po-structure.

Cite as

Lisbeth Fajstrup. Dihomotopy Classes of Dipaths in the Geometric Realization of a Cubical Set: from Discrete to Continuous and back again. In Spatial Representation: Discrete vs. Continuous Computational Models. Dagstuhl Seminar Proceedings, Volume 4351, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{fajstrup:DagSemProc.04351.13,
  author =	{Fajstrup, Lisbeth},
  title =	{{Dihomotopy Classes of Dipaths in the Geometric Realization of a Cubical Set: from Discrete to Continuous and back again}},
  booktitle =	{Spatial Representation: Discrete vs. Continuous Computational Models},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4351},
  editor =	{Ralph Kopperman and Michael B. Smyth and Dieter Spreen and Julian Webster},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04351.13},
  URN =		{urn:nbn:de:0030-drops-1328},
  doi =		{10.4230/DagSemProc.04351.13},
  annote =	{Keywords: Cubical Complex , Higher Dimensional Automaton , Ditopology}
}

Search Results

Documents authored by Fajstrup, Lisbeth

Applications of Combinatorial Topology to Computer Science (Dagstuhl Seminar 12121)

Abstract

Cite as

Dihomotopy Classes of Dipaths in the Geometric Realization of a Cubical Set: from Discrete to Continuous and back again

Abstract

Cite as

Thanks for your feedback!

Could not send message