 |
Towards an efficient conversion of Petri nets into Higher Dimensional Automata
1 : Télécom SudParis
Institut Polytechnique de Paris
2 : Laboratoire de Recherche de l'EPITA
* : Auteur correspondant
EPITA
Higher-dimensional automata (HDAs) extend classical automata by explicitly modeling concurrency through n-dimensional cells, each representing $n$ parallel events. Thanks to the cubical structure of HDAs, these cells implicitly determine their lower-dimensional faces via face maps, capturing all their interconnections.
In recent years, interest in HDAs has grown significantly,
in particular as they generalize most concurrent formalisms.
In a recently contribution, we proposed translations from Petri nets, including common features like weights, inhibitor arcs and even self-modifying nets to HDAs, along with a working implementation.
However the representation and data structures retained in this work are directly drawn from the mathematical description of HDAs and do not take advantage of the HDA's structure.
In this paper, we take initial steps toward leveraging this implicit structure.
We propose what we call the max-cell representation of an HDA: instead of storing all cells, we retain only those that are not induced by higher-dimensional ones.
This can lead to an exponential reduction in the number of cells and face maps while preserving all the information needed to reconstruct the full HDA.
To demonstrate its effectiveness, we present a new algorithm that directly translates Petri nets into max-cell HDAs.
