Weak consistency of P-time event graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915781690785792 |
|---|---|
| author | Zorzenon, Davide Balun, Jiří Raisch, Jörg |
| author_facet | Zorzenon, Davide Balun, Jiří Raisch, Jörg |
| contents | P-time event graphs (P-TEGs) are event graphs where the residence time of tokens in places is bounded by specified time windows. In this paper, we define a new property of PTEGs, called weak consistency. In weakly consistent P-TEGs, the amount of times a transition can fire before the first violation of a time constraint can be made as large as desired. We show the practical implications of this property and, based on previous results in graph theory, we formulate an algorithm of strongly polynomial time complexity that verifies it. From this algorithm, it is possible to determine, in pseudo-polynomial time, the maximum number of firings before the first constraint violation in a P-TEG. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2206_00478 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Weak consistency of P-time event graphs Zorzenon, Davide Balun, Jiří Raisch, Jörg Systems and Control Discrete Mathematics P-time event graphs (P-TEGs) are event graphs where the residence time of tokens in places is bounded by specified time windows. In this paper, we define a new property of PTEGs, called weak consistency. In weakly consistent P-TEGs, the amount of times a transition can fire before the first violation of a time constraint can be made as large as desired. We show the practical implications of this property and, based on previous results in graph theory, we formulate an algorithm of strongly polynomial time complexity that verifies it. From this algorithm, it is possible to determine, in pseudo-polynomial time, the maximum number of firings before the first constraint violation in a P-TEG. |
| title | Weak consistency of P-time event graphs |
| topic | Systems and Control Discrete Mathematics |
| url | https://arxiv.org/abs/2206.00478 |