Course director: Emmanuel Haucourt
Starting from a restriction of the language introduced by E. W. Dijkstra, we explain how directed algebraic topology can be applied to the study of concurrency.
What kind of concurrency in this course?
Restricted Dijkstra PV language
Precubical sets as a generalization of graphs
Control-flow graph, conservative programs, and precubical control flow
Locally ordered spaces
Directed realization of graphs and precubical sets
Isothetic regions
The fundamental category
Seifert and van Kampen theorem for the fundamental category [optional]
The category of components
Factorization
Some other topological models
French by default. However, questions asked in english will be answered in english.
Slides and (rather obsolete) lecture notes can be found here.
Fajstrup, L., Goubault, É., Haucourt, E., Mimram, S., and Raußen, M.
Directed Algebraic Topology and Concurrency. Springer 2016.
Brown, R. Topology and Groupoids. BookSurge. 2006.
Higgins, P. J. Categories and Groupoids. Van Nostrand-Reinhold 1975.
Hansen, P. B. The Origin of Concurrent Programming:
From Semaphores to Remote
Procedure Calls. Springer 2002.
Dijkstra, E. W. Cooperating Sequential Processes. In Genuys, F. (ed.)
Programming Languages: NATO Advanced Study Institute. Academic Press 1968.
Fajstrup, L., Goubault, É., and Raußen, M. Algebraic Topology and Concurrency.
Theoretical Computer Science 357(1):241–278 2006.
Presented at Mathematical Foundations of Computer Science in 1998 (London).
Awodey, S. Category Theory. Clarendon Press. Oxford 2006.
Leinster, T. Basic Category Theory. Cambridge University Press 2014.
Roman, S. An Introduction to the Language of Category theory. Birkhäuser 2017.
Semantics (2.2), Concurrent algorithms (2.18.2).
It is useful, though not strictly necessary, to have attended courses (similar to)
1-15 (Semantics) and 1-16 (Concurrency).
R. Amadio | Univ. Paris Diderot | PPS |
E. Goubault | École Polytechnique | LIX |
E. Haucourt | École Polytechnique | LIX |
J. Leifer | INRIA | Rocquencourt |
E. Lozes | ENS Cachan | LSV |
F. Valencia | École Polytechnique | LIX |