Decision Problems for Petri Nets and Vector Addition Systems
Petri Nets, Generalized Petri Nets, and Vector Addition Systems can represent each other and thus have common decideability problems. The graphical appeal of Petri Nets is used in a new presentation of the classical problems of boundedness (decidable) and inclusion (undecidable). Various forms of th...
| Main Author: | |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/148887 |
| _version_ | 1826197742139998208 |
|---|---|
| author | Hack, Michael |
| author_facet | Hack, Michael |
| author_sort | Hack, Michael |
| collection | MIT |
| description | Petri Nets, Generalized Petri Nets, and Vector Addition Systems can represent each other and thus have common decideability problems. The graphical appeal of Petri Nets is used in a new presentation of the classical problems of boundedness (decidable) and inclusion (undecidable). Various forms of the Reachability Problem are shown to be recursively equivalent to the Liveness Problem for Petri Nets. The decideability of these questions is still open, and some arguments both for and against the decidability of Liveness are presented. |
| first_indexed | 2024-09-23T10:52:27Z |
| id | mit-1721.1/148887 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T10:52:27Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1488872023-03-30T03:58:27Z Decision Problems for Petri Nets and Vector Addition Systems Hack, Michael Petri Nets, Generalized Petri Nets, and Vector Addition Systems can represent each other and thus have common decideability problems. The graphical appeal of Petri Nets is used in a new presentation of the classical problems of boundedness (decidable) and inclusion (undecidable). Various forms of the Reachability Problem are shown to be recursively equivalent to the Liveness Problem for Petri Nets. The decideability of these questions is still open, and some arguments both for and against the decidability of Liveness are presented. 2023-03-29T14:05:06Z 2023-03-29T14:05:06Z 1975-03 https://hdl.handle.net/1721.1/148887 01963074 MIT-LCS-TM-059 MAC-TM-058 application/pdf |
| spellingShingle | Hack, Michael Decision Problems for Petri Nets and Vector Addition Systems |
| title | Decision Problems for Petri Nets and Vector Addition Systems |
| title_full | Decision Problems for Petri Nets and Vector Addition Systems |
| title_fullStr | Decision Problems for Petri Nets and Vector Addition Systems |
| title_full_unstemmed | Decision Problems for Petri Nets and Vector Addition Systems |
| title_short | Decision Problems for Petri Nets and Vector Addition Systems |
| title_sort | decision problems for petri nets and vector addition systems |
| url | https://hdl.handle.net/1721.1/148887 |
| work_keys_str_mv | AT hackmichael decisionproblemsforpetrinetsandvectoradditionsystems |