Both Petri Nets and finite automata are prone to the state explosion problem. A recent line of research shows the state explosion in finite automata is captured by a notion of convexity. We outline how the result on finite automata can be exploited to suggest a new approach for studying Petri nets. Petri nets are widely used to model distributed systems. The expressive power of this formalism comes to a price: Petri nets are prone to the state explosion problem [1]. A Petri net can describe a system that may have infinitely many states, thus making it dificult to analyze and simulate the system's behavior. Given a Petri net and an initial marking, the reachability graph is a (possibly infinite) graph describing all markings of the Petri nets reachable from the initial marking by firing transitions (see Figure 1). A classical result shows that it is possible to decide whether the reachability graph is ifnite by constructing the Karp-Miller tree of the Petri net. To limit the complexity of the reachability graph, it is possible to add (topological) constraints to the Petri nets that ensure that the reachability graph is small or at least finite, while still allowing the modeling of a wide range of systems (see [ 2] for a survey). A Petri net is structurally bounded if the reachability graph is finite for every choice of the initial marking. An important special case of structurally bounded Petri nets is that of conservative Petri nets, in which after firing any transition, the total number of tokens is the same as before firing the transitions. Alternatively, we can add constraints that depend on a parameter to parameterize the size of the reachability graph as a function of . For example, a Petri net is -bounded if every marking reachable from the initial marking has the property that no place contains more than tokens. In particular, an 1-bounded Petri net is safe. Petri nets can be seen as an extension of finite automata. In automata theory, a similar state explosion occurs when we apply the powerset construction to convert a nondeterministic automaton (NFA) into a deterministic automaton (DFA) recognizing the same regular language: if an NFA has states, then the equivalent DFA can have up to 2 − 1 states (see Figure 1). While the expressive power of NFAs is the same as the expressive power of DFAs, determinism is extremely helpful in studying the properties of an automaton. Some basic problems in automata theory - such as the emptiness problem and the equivalence problem - are PSPACE complete on NFAs but can be solved in almost-linear time on DFAs. The natural question is whether for automata it is possible to follow the same path that we sketched for Petri nets - adding constraints to the topology of the considered NFAs to control the state explosion. A recent line of research in automata theory has shown that, indeed, a notion of convexity captures the complexity of the powerset construction and establishes an unexpected connection between data compression and automata theory, thus leading to Wheeler automata [3]. A Wheeler NFA is endowed with a total order on the set of all states. In Figure 2, the total order is given by the numbering of the states. First, the total order respects equally-labeled edges: for example, if we consider edges (10, 5, ) and (11, 6, ), we have 10 < 11, and consistently we have 5 < 6. Second, if we consider edges with distinct labels - such as (5, 2, ) and (11, 7, ) - we have < and consistently the end states satisfy
start (0, 0, 1, 0, 1) 5 6 (0, 1, 1, 0, 0)
(1, 1, 0, 0, 0)
6
1
2
1
4
2
1
1, 2
1, 4 1, 3
1
6
6
2 < 7. Wheeler automata admit a compressed representation that supports eficient pattern-matching
queries. This is crucial in bioinformatics, where both time-eficient and space-eficient algorithms
are required. For example, de Bruijn automata are used in genome assembly [
Surprisingly, if we start from a Wheeler NFA and we apply the powerset construction, in the worst
case the equivalent DFA does not have 2 − 1 states, but only 2 − 1 states. This paradigm was recently
extended to arbitrary automata by introducing a new parameter [
Our goal is to extend the convexity paradigm to Petri nets. This is both of theoretical and practical interest. Currently, we do not know natural classes of automata for which is — say — at most 5. At the same time, many Petri nets describing real systems have a small — intuitively, many real systems are “quasi-convex”. For example, the Petri nets modeling the manufacturing system in Figure 2 can be divided into 4 linear components (one for each component and one describing the process after the merging). Every linear component can be seen as a total order, so it is intuitively reasonable to claim that is at most 4 in our example.
We have three main objectives. First, we formalize the notion of convexity (or quasi-convexity) and we study the properties of convex Petri nets (boundness, reachability, and so on), focusing on a b d b f
g
start
a
b
e
h
8
7
8
10
11
6
3
6
9
the state explosion. Second, we show how convex Petri nets can model a broad spectrum of real
systems by providing case studies. Lastly, we study the languages recognized by convex Petri nets. We
know that finite automata recognize regular language (finite strings) and -regular languages (infinite
strings). Wheeler automata recognize an interesting subclass of regular languages — Wheeler languages
— that always admit a minimum Wheeler automata, an algebraic characterization, and a Myhill-Nerode
theorem [
Acknowledgements. This work has been partially funded by the MUR-PRIN project DREAM (20228 78 ), and the MUR-PNRR project VITALITY (00000041).