A Lower Bound on Conservative Elementary Object Systems Coverability
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909565477453824 |
|---|---|
| author | Di Cosmo, Francesco Mal, Soumodev Prince, Tephilla |
| author_facet | Di Cosmo, Francesco Mal, Soumodev Prince, Tephilla |
| contents | Elementary Object Systems (EOS) are a form of Petri Net (PN) where tokens carry internal PN. This model has been recently proposed for analysis of robustness of Multi Agent Systems. While EOS reachability is known to be undecidable, the decidability of coverability of its conservative fragment (where the type of internal PN cannot be completely deleted and, thus, is conserved) was proved a decade ago, no study charted its complexity. Here, we take a first step in this direction, by showing how to encode $ν$PNs, a well studied form of PN enriched with data, into conservative EOS (cEOS). This yields a non-Primitive Recursive, $F_{\omega2}$ lower-bound on cEOS coverability. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_03591 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Lower Bound on Conservative Elementary Object Systems Coverability Di Cosmo, Francesco Mal, Soumodev Prince, Tephilla Computational Complexity Elementary Object Systems (EOS) are a form of Petri Net (PN) where tokens carry internal PN. This model has been recently proposed for analysis of robustness of Multi Agent Systems. While EOS reachability is known to be undecidable, the decidability of coverability of its conservative fragment (where the type of internal PN cannot be completely deleted and, thus, is conserved) was proved a decade ago, no study charted its complexity. Here, we take a first step in this direction, by showing how to encode $ν$PNs, a well studied form of PN enriched with data, into conservative EOS (cEOS). This yields a non-Primitive Recursive, $F_{\omega2}$ lower-bound on cEOS coverability. |
| title | A Lower Bound on Conservative Elementary Object Systems Coverability |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2504.03591 |