Well-Formed Free-Choice Petri Nets Revisited
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911416584241152 |
|---|---|
| author | Jancar, Petr Best, Eike Devillers, Raymond Ostadal, Matej |
| author_facet | Jancar, Petr Best, Eike Devillers, Raymond Ostadal, Matej |
| contents | The theory of free-choice Petri nets is an established field, initiated in the 1970s by Commoner and Hack at MIT. We revisit well-formed free-choice nets (those admitting markings that are both live and bounded) and provide a new characterization by introducing semi-T-components. This notion is dual to that of semi-S-components, which in turn correspond to the well-known minimal siphons. By highlighting the symmetry between these dual concepts, we derive the classical coverability theorems for T- and S-components, as well as the duality theorem -- stating that a free-choice net is well-formed if and only if its reverse-dual is also well-formed -- using arguments that are as symmetric as possible. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_02352 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Well-Formed Free-Choice Petri Nets Revisited Jancar, Petr Best, Eike Devillers, Raymond Ostadal, Matej Formal Languages and Automata Theory The theory of free-choice Petri nets is an established field, initiated in the 1970s by Commoner and Hack at MIT. We revisit well-formed free-choice nets (those admitting markings that are both live and bounded) and provide a new characterization by introducing semi-T-components. This notion is dual to that of semi-S-components, which in turn correspond to the well-known minimal siphons. By highlighting the symmetry between these dual concepts, we derive the classical coverability theorems for T- and S-components, as well as the duality theorem -- stating that a free-choice net is well-formed if and only if its reverse-dual is also well-formed -- using arguments that are as symmetric as possible. |
| title | Well-Formed Free-Choice Petri Nets Revisited |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2602.02352 |