Attractor Basins in Concurrent Systems
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910586850246656 |
|---|---|
| author | Samboni, Giann Karlo Aguirre Haar, Stefan Paulevé, Loic Schwoon, Stefan Würdemann, Nick |
| author_facet | Samboni, Giann Karlo Aguirre Haar, Stefan Paulevé, Loic Schwoon, Stefan Würdemann, Nick |
| contents | A crucial question in analyzing a concurrent system is to determine its long-run behaviour, and in particular, whether there are irreversible choices in its evolution, leading into parts of the reachability space from which there is no return to other parts. Casting this problem in the unifying framework of safe Petri nets, our previous work has provided techniques for identifying attractors, i.e. terminal strongly connected components of the reachability space. What we aim at is to determine the attraction basins associated to those attractors; that is, those states from where all infinite runs are doomed to end in the given attractor, as opposed to those that are free to evolve differently. Here, we provide a solution for the case of safe Petri nets. Our algorithm uses net unfoldings and provides a map of all of those configurations (concurrent executions of the system) that lead onto cliff-edges, i.e. any maximal extension for those configurations lies in some basin that is considered fatal. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_01079 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Attractor Basins in Concurrent Systems Samboni, Giann Karlo Aguirre Haar, Stefan Paulevé, Loic Schwoon, Stefan Würdemann, Nick Formal Languages and Automata Theory F.4 A crucial question in analyzing a concurrent system is to determine its long-run behaviour, and in particular, whether there are irreversible choices in its evolution, leading into parts of the reachability space from which there is no return to other parts. Casting this problem in the unifying framework of safe Petri nets, our previous work has provided techniques for identifying attractors, i.e. terminal strongly connected components of the reachability space. What we aim at is to determine the attraction basins associated to those attractors; that is, those states from where all infinite runs are doomed to end in the given attractor, as opposed to those that are free to evolve differently. Here, we provide a solution for the case of safe Petri nets. Our algorithm uses net unfoldings and provides a map of all of those configurations (concurrent executions of the system) that lead onto cliff-edges, i.e. any maximal extension for those configurations lies in some basin that is considered fatal. |
| title | Attractor Basins in Concurrent Systems |
| topic | Formal Languages and Automata Theory F.4 |
| url | https://arxiv.org/abs/2409.01079 |