The Complexity of the Finite Containment Problem for Petri Nets
If the reachability set of a Petri net (or, equivalently, vector addition system) is finite it can be effectively constructed. Furthermore, the finiteness is decidable. Thus, the containment and equality problem for finite reachability sets become solvable. We investigate the complexity of decisio...
| Main Author: | |
|---|---|
| Other Authors: | |
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149473 |
| _version_ | 1826192500212105216 |
|---|---|
| author | Mayr, Ernst Wilhelm |
| author2 | Meyer, Albert R. |
| author_facet | Meyer, Albert R. Mayr, Ernst Wilhelm |
| author_sort | Mayr, Ernst Wilhelm |
| collection | MIT |
| description | If the reachability set of a Petri net (or, equivalently, vector addition system) is finite it can be effectively constructed. Furthermore, the finiteness is decidable. Thus, the containment and equality problem for finite reachability sets become solvable. We investigate the complexity of decision procedures for these problems and show by reducing a bounded version of Hilbert's Tenth Problem to the finite containment problem that these two problems are extremely hard, that, in fact, the complexity of each decision procedure exceeds any primitive recursive function infinitely often. |
| first_indexed | 2024-09-23T09:17:10Z |
| id | mit-1721.1/149473 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T09:17:10Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1494732023-03-30T04:12:36Z The Complexity of the Finite Containment Problem for Petri Nets Mayr, Ernst Wilhelm Meyer, Albert R. If the reachability set of a Petri net (or, equivalently, vector addition system) is finite it can be effectively constructed. Furthermore, the finiteness is decidable. Thus, the containment and equality problem for finite reachability sets become solvable. We investigate the complexity of decision procedures for these problems and show by reducing a bounded version of Hilbert's Tenth Problem to the finite containment problem that these two problems are extremely hard, that, in fact, the complexity of each decision procedure exceeds any primitive recursive function infinitely often. 2023-03-29T15:01:15Z 2023-03-29T15:01:15Z 1977-06 https://hdl.handle.net/1721.1/149473 03427193 MIT-LCS-TR-181 application/pdf |
| spellingShingle | Mayr, Ernst Wilhelm The Complexity of the Finite Containment Problem for Petri Nets |
| title | The Complexity of the Finite Containment Problem for Petri Nets |
| title_full | The Complexity of the Finite Containment Problem for Petri Nets |
| title_fullStr | The Complexity of the Finite Containment Problem for Petri Nets |
| title_full_unstemmed | The Complexity of the Finite Containment Problem for Petri Nets |
| title_short | The Complexity of the Finite Containment Problem for Petri Nets |
| title_sort | complexity of the finite containment problem for petri nets |
| url | https://hdl.handle.net/1721.1/149473 |
| work_keys_str_mv | AT mayrernstwilhelm thecomplexityofthefinitecontainmentproblemforpetrinets AT mayrernstwilhelm complexityofthefinitecontainmentproblemforpetrinets |