Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2312.10764 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915781795643392 |
|---|---|
| author | Zorzenon, Davide Raisch, Jörg |
| author_facet | Zorzenon, Davide Raisch, Jörg |
| contents | P-time event graphs are discrete event systems able to model cyclic production systems where tasks need to be performed within given time windows. Consistency is the property of admitting an infinite execution of such tasks that does not violate any temporal constraints. In this paper, we solve the long-standing problem of characterizing the decidability of consistency by showing that, assuming unary encoding of the initial marking, this property can be verified in strongly polynomial time. The proof is based on a reduction to the problem of detecting paths with infinite weight in infinite weighted digraphs called N-periodic graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_10764 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Consistency of P-time event graphs is decidable in polynomial time (extended version) Zorzenon, Davide Raisch, Jörg Logic in Computer Science Discrete Mathematics Systems and Control P-time event graphs are discrete event systems able to model cyclic production systems where tasks need to be performed within given time windows. Consistency is the property of admitting an infinite execution of such tasks that does not violate any temporal constraints. In this paper, we solve the long-standing problem of characterizing the decidability of consistency by showing that, assuming unary encoding of the initial marking, this property can be verified in strongly polynomial time. The proof is based on a reduction to the problem of detecting paths with infinite weight in infinite weighted digraphs called N-periodic graphs. |
| title | Consistency of P-time event graphs is decidable in polynomial time (extended version) |
| topic | Logic in Computer Science Discrete Mathematics Systems and Control |
| url | https://arxiv.org/abs/2312.10764 |