Course director: Emmanuel Haucourt

Emmanuel Haucourt (professional web page)

In view of studying concurrency in a continuous setting, we introduce topology, geometry, and order theory needed to define a semantics of a restriction of the language introduced by E. W. Dijkstra.

French. However, questions asked in english will be answered in english.

Lecture 1

A QUICK OVERVIEW OF CONCURRENCY THEORY

PARALLEL AUTOMATA META LANGUAGE: Syntax, Control Flow Graph, Abstract Machine

CONSERVATIVE PROGRAMS: Potential Functions, Discrete Models

Lecture 2

AN ALGEBRAIC TOPOLOGY TEASER: Categories, Topology, Functors, Connectedness

METRIC SPACES: Functor terminology, Categories of metric spaces, Metric graphs

LOCALLY ORDERED METRIC GRAPHS: Partially ordered spaces, Ordered atlases, Basic properties, Ordered atlas on metric graphs

Lecture 3

MODELS: Cartesian product, From discrete to geometric models, Examples, Geometric vs Discrete, The motivating theorem, From geometric to smooth models

HOMOTOPY OF PATHS: Undirected case, Directed case, Relation to geometric models

INDEPENDANCE: Syntactical independence, Model independence, Observational independence, Comparison

Lecture 4

ISOTHETIC REGIONS: Boolean structure, Additional operators

FACTORING ISOTHETIC REGIONS: Free commutative monoids, Monoids of homogeneous languages, Homogeneous languages and isothetic regions

Lecture 5

FUNDAMENTAL CATEGORY: Abstract setting, Directed path functor, Natural congruences, Basic properties and computations

CATEGORY OF COMPONENTS: Motivation, Loop-free categories, Systems of weak isomorphisms, Construction, Properties, Examples, Finite connected loop-free categories

• Fajstrup, L., Goubault, É., Haucourt, E., Mimram, S., and Raussen, 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 Raussen, M. Algebraic Topology and Concurrency.
  Theoretical Computer Science 357(1):241–278, 2006. Presented at Mathematical Foundations of Computer Science in 1998 (London).
• Haucourt, E. The geometry of conservative programs.
  Mathematical Structures in Computer Science, 2018.

• 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.

More advanced books:

• Mac Lane, S. Categories for the Working Mathematician (2nd ed.). Springer, 1998.
• Riehl, E. Category Theory in Context. Dover, 2016.

Models of programming languages: domains, categories, and games (2.2)

Distributed algorithms on shared memory (2.18.2).

8 march 2024, 8h45 - 11h45, Sophie Germain building, room 1002.

8h45 - 11h45, Sophie Germain building, room 1002

8, 15 december 2023

12, 19, 26 january 2024

2, 9, 16 february 2024