Infinite precedence graphs for consistency verification in P-time event graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916676318003200 |
|---|---|
| author | Zorzenon, Davide Raisch, Jörg |
| author_facet | Zorzenon, Davide Raisch, Jörg |
| contents | Precedence constraints are inequalities used to model time dependencies. In 1958, Gallai proved that a finite system of precedence constraints admits solutions if and only if the corresponding precedence graph does not contain positive-weight circuits. We show that this result extends naturally to the case of infinitely many constraints. We then analyze two specific classes of infinite precedence graphs -- $\mathbb{N}$-periodic and ultimately periodic graphs -- and prove that the existence of solutions of their related constraints can be verified in strongly polynomial time. The obtained algorithms find applications in P-time event graphs, which are a subclass of P-time Petri nets able to model production systems under cyclic schedules where tasks need to be performed within given time windows. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_05056 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Infinite precedence graphs for consistency verification in P-time event graphs Zorzenon, Davide Raisch, Jörg Systems and Control Discrete Mathematics Precedence constraints are inequalities used to model time dependencies. In 1958, Gallai proved that a finite system of precedence constraints admits solutions if and only if the corresponding precedence graph does not contain positive-weight circuits. We show that this result extends naturally to the case of infinitely many constraints. We then analyze two specific classes of infinite precedence graphs -- $\mathbb{N}$-periodic and ultimately periodic graphs -- and prove that the existence of solutions of their related constraints can be verified in strongly polynomial time. The obtained algorithms find applications in P-time event graphs, which are a subclass of P-time Petri nets able to model production systems under cyclic schedules where tasks need to be performed within given time windows. |
| title | Infinite precedence graphs for consistency verification in P-time event graphs |
| topic | Systems and Control Discrete Mathematics |
| url | https://arxiv.org/abs/2504.05056 |