Abstract
When modeling concurrent or cyber-physical systems, non-functional requirements such as time are important to consider. In order to improve the timing aspects of a model, it is necessary to have some notion of what it means for a process to be faster than another, which can guide the stepwise refinement of the model. To this end we study a faster-than relation for semi-Markov decision processes and compare it to standard notions for relating systems. We consider the compositional aspects of this relation, and show that the faster-than relation is not a precongruence with respect to parallel composition, hence giving rise to so-called parallel timing anomalies. We take the first steps toward understanding this problem by identifying decidable conditions sufficient to avoid parallel timing anomalies in the absence of non-determinism.
| Original language | English |
|---|---|
| Journal | Electronic Proceedings in Theoretical Computer Science, EPTCS |
| Volume | 312 |
| Pages (from-to) | 29-42 |
| Number of pages | 14 |
| ISSN | 2075-2180 |
| DOIs | |
| Publication status | Published - 20 Jan 2020 |
| Event | 16th Workshop on Quantitative Aspects of Programming Languages and Systems, QAPL 2019 - Prague, Czech Republic Duration: 7 Apr 2019 → … |
Conference
| Conference | 16th Workshop on Quantitative Aspects of Programming Languages and Systems, QAPL 2019 |
|---|---|
| Country/Territory | Czech Republic |
| City | Prague |
| Period | 07/04/2019 → … |
Bibliographical note
Funding Information:Acknowledgements. Mathias R. Pedersen was supported by the ASAP project (no. 4181-00360) funded by the Danish Council for Independent Research. Kim G. Larsen was supported by the ERC Advanced Grant LASSO (no. 867096).
Publisher Copyright:
© M.R. Pedersen, G. Bacci, & K.G. Larsen.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.