Report Number: CS-TR-90-1342
Institution: Stanford University, Department of Computer Science
Title: Modeling concurrency with geometry
Author: Pratt, Vaughan
Date: November 1990
Abstract: The phenomena of branching time and true or noninterleaving concurrency find their respective homes in automata and schedules. But these two models of computation are formally equivalent via Birkhoff duality, an equivalence we expound on here in tutorial detail. So why should these phenomena prefer one over the other? We identify dimension as the culprit: 1-dimensional automata are skeletons permitting only interleaving concurrency, whereas rrue n-fold concurrency resides in transitions of dimension n. The truly concurrent automaton dual to a schedule is not a skeletal distributive lattice but a solid one! We introduce true nondeterminism and define it as monoidal homotopy; from this perspective nondeterminism in ordinary automata arises from forking and joining creating nontrivial homotopy. The automaton dual to a poset schedule is simply connected whereas that dual to an event structure schedule need not be, according to monoidal homotopy though not to group homotopy. We conclude with a formal definition of higher dimensional automaton as an n-complex or n-category, whose two essential axioms are associativity of concatenation within dimension and an interchange principle between dimensions.
http://i.stanford.edu/pub/cstr/reports/cs/tr/90/1342/CS-TR-90-1342.pdf