Closure and decision properties for higher-dimensional automata
In 20th international colloquium on theoretical aspects of computing (ICTAC’23)
Abstract
A Myhill-Nerode theorem for higher-dimensional automata
In Application and theory of petri nets and concurrency (PETRI NETS)
Abstract We establish a Myhill-Nerode type theorem for higher-dimensional automata (HDAs), stating that a language is regular precisely if it has finite prefix quotient. HDAs extend standard automata with additional structure, making it possible to distinguish between interleavings and concurrency. We also introduce deterministic HDAs and show that not all HDAs are determinizable, that is, there exist regular languages that cannot be recognised by a deterministic HDA. Using our theorem, we develop an internal characterisation of deterministic languages.
Catoids and modal convolution algebras
In Algebra Universalis
Abstract We show how modal quantales arise as convolution algebras $Q^X$ of functions from catoids $X$, that is, multisemigroups with a source map $\ell$ and a target map $r$, into modal quantales $Q$, which can be seen as weight or value algebras. In the tradition of boolean algebras with operators we study modal correspondences between algebraic laws in $X$, $Q$ and $Q^X$. The class of catoids we introduce generalises Schweizer and Sklar’s function systems and object-free categories to a setting isomorphic to algebras of ternary relations, as they are used for boolean algebras with operators and substructural logics.
A Kleene theorem for higher-dimensional automata
In 33rd international conference on concurrency theory (CONCUR 2022)
Abstract 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.
Posets with interfaces as a model for concurrency
In Information and Computation
Abstract We introduce posets with interfaces (iposets) and generalise their standard serial composition to a new gluing composition. In the partial order semantics of concurrency, interfaces and gluing allow modelling events that extend in time and across components. Alternatively, taking a decompositional view, interfaces allow cutting through events, while serial composition may only cut through edges of a poset. We show that iposets under gluing composition form a category, which generalises the monoid of posets under serial composition up to isomorphism.