Interpreted Higher-Dimensional Automata for Concurrent Discrete-Event Control
Dylan Bellier, Gregory Faraut, Yan Monier, Philipp Schlehuber-Caissier · 2026
Read Interpreted Higher-Dimensional Automata for Concurrent Discrete-Event Control by Dylan Bellier, Gregory Faraut, Yan Monier, Philipp Schlehuber-Caissier (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-21742.txt.
Introduction
Bellier and co-authors adapt higher dimensional automata to build controllers for concurrent systems. Higher dimensional automata extend classic automata theory, but real control uses were missing. The team starts from controllers written as interpreted Petri nets. Their method turns such a net into a working closed-loop controller. Along the way, the automata view exposes vague or conflicting specs that stay hidden in the net. They prove the approach on an industrial example, linking the controller to a virtual environment and running the loop in simulation.
Catalog record
| CREATOR | Dylan Bellier, Gregory Faraut, Yan Monier, Philipp Schlehuber-Caissier |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 30961 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.21742
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Interpreted Higher-Dimensional Automata for Concurrent Discrete-Event Control Dylan Bellier, Gregory Faraut, Yan Monier, Philipp Schlehuber-Caissier Abstract In recent years the theory of Higher Dimensional Automata (HDA) has seen significant advances from a theoretical point of view, reflecting standard automata theory (for instance [ 7 ] ). There have also been first attempts to use the mathematical framework provided by HDAs to known problems, in particular Petri Net analysis (see [ 14 , 2 ] ). However real-world applications are still lacking and issues from real-world system, as concurrency, is still opened in the context of controller generation. In this work we show how the framework of HDAs can be adapted to help transforming controllers given as interpreted Petri nets (IPN) into an actual closed loop controller and how the HDA helps in identifying ambiguous or even contradictory specifications that remain “hidden” in the IPN. We demonstrate the feasibility by connecting the obtain controller to a virtual environment for closed loop control, exemplified by an industrial example. I Introduction Modern Cyber-Physical Production Systems (CPPS) are increasingly distributed and concurrent, which makes the design, by discrete-event systems (DES) formalism, and validation of controllers more challenging [ 1 ] . While formal DES methods provide strong guarantees for verification, diagnosis, and synthesis, their practical effectiveness depends on how well the chosen semantics reflects what actually happens at execution time [ 13 ] . In many industrial settings (PLC scan cycles, asynchronous I/O, communication latencies), actions that are treated as instantaneous in the model may occur effectively simultaneously, or with an order that is not under the designer’s control [ 3 ] . A common modeling choice is to represent concurrency through interleavings: concurrent events are serialized into sequences [ 3 ] . This abstraction is often sufficient for reachability-style questions, but it can hide concurrency-induced inconsistencies that only appear when multiple events occur “at the same time.” A typical example is the assignment of outputs: two events that are independent in the net (hence potentially concurrent in reality) may impose conflicting output updates, yet the conflict can remain invisible when those events are forced to occur in some order. Such issues are especially problematic when specifications are partial or loosely constrained, since multiple implementations may satisfy the interleaving model while behaving differently under concurrent executions [ 11 ] . This paper proposes a true-concurrency viewpoint for control specifications by leveraging Higher-Dimensional Automata (HDA) [ 14 ] , where higher-dimensional cells explicitly represent concurrent steps rather than encoding them as arbitrary interleavings. We introduce here an interpreted variant, called Interpreted HDA (IHDA) and based on Interpreted Petri Net (IPN) [ 4 ] , to include inputs/outputs and make the model directly usable for automation control. In IHDA, concurrency is not only represented, it becomes an analyzable object, allowing for verifications that are formulated at the level of simultaneous actions. Our main contribution is a translation from Interpreted Petri Nets (IPN) to IHDA that preserves the standard sequential behavior while explicitly generating higher-dimensional cells for admissible concurrent firings. On top of this construction, we propose a simple mechanism to detect output inconsistencies under concurrency: if a concurrent step entails incompatible output requirements (e.g., simultaneous opposite updates), the inconsistency becomes explicit in the corresponding cell constraints, and a witness execution can be extracted. We illustrate the approach on a representative manufacturing example implemented in a simulation tool, showing how IHDA helps bridge the gap between Discrete-Event System controller designed in common formalism (Automaton or Petri Net) and the concurrency effects induced by the physical execution layer. The remainder of the paper is organized as follows. In section II , we recall background on Interpreted Petri Net, while recall on HDA is in section III . The section IV is dedicated to define IHDA and the IPN to IHDA translation. This section presents also the inconsistency detection principle. Finally, section V presents a case study of manufacturing system designed in a simulation tool. II Interpreted Petri Nets Interpreted Petri Nets (IPNs) are a well known formalism in the control and automatisation community in order to use Petri nets as effective plant controllers. To this end, the Petri net is extended with input and output signals allowing to interface it with the physical plant [ 4 , 12 ] . The inputs and outputs of IPNs are often directly associated to a sensor or an actuator. In this work take a slightly more generic approach. We use sets of atomic propositions (APs) as input and output, as it is standard when working with (input-output) automata [ 5 , 9 ] or in the context of reactive synthesis [ 8 ] . An atomic proposition correspond to a Boolean variable and transitions in automata can be labelled by Boolean functions over these propositions rather than simple letters. While this does not change the expressiveness of the automaton, it greatly increases practical usability. Here we take a similar approach for defining the inputs and outputs of the IPN. To keep notions concise, we will use a subset of the Boolean functions called cubes. A cube is a Boolean function which uses only conjunctions, atomic propositions and their negations (i.e. no disjunction). They are generated by the grammar c\Coloneqq ap\mid\neg ap\mid c\land c with c being a cube and ap being a atomic proposition. Finally we call a cube that uses all of the atomic propositions (each of the APs is associates to \top or \bot ) a valuation. This restriction, that makes the presentation easier, can however easily be removed in the future. Formally we have: Definition 1 An Interpreted Petri Net (IPN) Q=\left\{G,M_{0},I,O,\lambda_{pn}\right\} where (G,M_{0}) is a standard marked Petri net with G=(P,T) being the places and transition and • I is a finite set of atomic input propositions, • O is a finite set of atomic output propositions, • \lambda_{pn} being the labeling function. The labeling function \lambda_{pn} associates to each place in the original net a cube over the outputs and to each transition a pair of cubes, one over the inputs and one over the outputs, denoted \lambda_{pn}(t)[0] / \lambda_{pn}(t)[1] for the input/output condition. A standard Petri net in this context is unweighted, uncolored and without inhibitor arcs or any other extension. This is a deliberate choice in order to keep the definitions compact. A straightforward adaption of many of these extensions is however possible, as only the construction of the corresponding HDA (see Section III ) needs to be changed and dedicated constructions for many of these techniques are introduced in [ 2 ] . The firing of transitions in such a Petri net is conditioned by the inputs. That is a transition t can only fire when (as for a conventional Petri net) all preplaces \mathchoice{\mathop{}\kern 0.0pt\mathopen{\vphantom{{}^{\bullet}{t}}}}{\mathop{}\kern 0.0pt\mathopen{\vphantom{{}^{\bullet}{t}}}}{\mathop{}\kern 0.0pt\mathopen{\vphantom{{}^{\bullet}{t}}}}{\mathop{}\kern 0.0pt\mathopen{\vphantom{{}^{\bullet}{t}}}}^{\bullet}{t} have at least one token and the current valuation of the inputs is compatible with \lambda_{pn}(t)[0] . Formally, the input is given as a valuation over the input propositions, denoted i , and it is compatible with a transition t iff i\models\lambda_{pn}(t)[0] . An interpreted execution of such a Petri net transforms a stream of input valuations into a stream of output valuations. We interpret the combination of these two streams as infinite words: