This README summarizes the core analysis tasks performed on the input Petri Net models (e.g., DOCPATIENT.pnml).
The project evaluates the net's behavior, including state-space exploration, symbolic representation, deadlock detection, and optimization over reachable markings.
The analysis is performed sequentially, beginning with explicit state-space exploration, then moving to symbolic representation using BDDs, followed by deadlock detection, and finally optimization.
Each task builds upon the previous one to provide a complete behavioral understanding of the Petri Net model.
Compute all reachable markings of the Petri Net using graph traversal techniques (BFS/DFS).
This produces the ground truth reachability set.
| Metric | Description | Example Output |
|---|---|---|
| Net Size | Number of places ` | P |
| Explicit Markings | Total number of reachable states found explicitly | Explicit reachable markings: 10 |
Represent the reachable state space using Binary Decision Diagrams (BDDs).
BDDs can encode large state sets compactly and canonically.
| Metric | Description | Example Output |
|---|---|---|
| BDD Markings | Number of unique states enumerated from the BDD | BDD enumerated markings: 10 |
The BDD result should match the explicit marking count for correctness.
Identify any deadlock markings—states where no transitions are enabled.
Deadlock analysis validates the net’s liveness.
| Method | Description | Example Output |
|---|---|---|
| Deadlock (Explicit) | Deadlock found during explicit reachability | Deadlock found (explicit): { 'P_done', 'P_free' } |
| Deadlock (BDD) | Deadlock found during symbolic (BDD-based) reachability | Deadlock found (BDD/enumeration): { 'P_done', 'P_free' } |
Both methods should identify the same marking.
Perform optimization (via ILP) over the set of reachable markings.
The objective depends on the analysis requirement, e.g.:
- Maximize total tokens
- Minimize resource usage
- Maximize number of idle components
| Metric | Description | Example Output |
|---|---|---|
| Objective | Function being optimized | Optimization result (maximize total tokens): { ... } |
| Optimal Marking | Token distribution achieving optimal value | { 'P_done': 1, 'P_docu': 1 } |
| Optimal Value | Numerical result of the objective function | value = 2 |
Run the analysis using:
python main.py /path/to/model.pnml