The following paper has been accepted at the 33rd International Conference
on Concurrency Theory (CONCUR 2022), to be held in Warsaw next week:
A Kleene Theorem for Higher-Dimensional Automata
Uli Fahrenberg, Christian Johansen, Georg Struth, Krzysztof Ziemiański
(LR(D)E, NTNU Gjøvik, U of Sheffield, Warsaw U)
We prove a Kleene theorem for higher-dimensional automata (HDAs). It states
that the languages they recognise are precisely the rational
subsumption-closed sets of interval pomsets. The rational operations include
a gluing composition, for which we equip pomsets with interfaces. For our
proof, we introduce HDAs with interfaces as presheaves over labelled precube
categories and use tools inspired by algebraic topology, such as cylinders
and (co)fibrations. HDAs are a general model of non-interleaving
concurrency, which subsumes many other models in this field. Interval orders
are used as models for concurrent or distributed systems where events extend
in time. Our tools and techniques may therefore yield templates for Kleene
theorems in various models and applications.
Show replies by date