TY - GEN
T1 - Dual-priced modal transition systems with time durations
AU - Beneš, Nikola
AU - Křetínský, Jan
AU - Guldstrand Larsen, Kim
AU - Møller, Mikael H.
AU - Srba, Jiří
PY - 2012
Y1 - 2012
N2 - Modal transition systems are a well-established specification formalism for a high-level modelling of component-based software systems. We present a novel extension of the formalism called modal transition systems with durations where time durations are modelled as controllable or uncontrollable intervals. We further equip the model with two kinds of quantitative aspects: each action has its own running cost per time unit, and actions may require several hardware components of different costs. We ask the question, given a fixed budget for the hardware components, what is the implementation with the cheapest long-run average reward. We give an algorithm for computing such optimal implementations via a reduction to a new extension of mean payoff games with time durations and analyse the complexity of the algorithm.
AB - Modal transition systems are a well-established specification formalism for a high-level modelling of component-based software systems. We present a novel extension of the formalism called modal transition systems with durations where time durations are modelled as controllable or uncontrollable intervals. We further equip the model with two kinds of quantitative aspects: each action has its own running cost per time unit, and actions may require several hardware components of different costs. We ask the question, given a fixed budget for the hardware components, what is the implementation with the cheapest long-run average reward. We give an algorithm for computing such optimal implementations via a reduction to a new extension of mean payoff games with time durations and analyse the complexity of the algorithm.
UR - http://www.scopus.com/inward/record.url?scp=84858311241&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-28717-6_12
DO - 10.1007/978-3-642-28717-6_12
M3 - Conference contribution
AN - SCOPUS:84858311241
SN - 9783642287169
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 122
EP - 137
BT - Logic for Programming, Artificial Intelligence, and Reasoning - 18th International Conference, LPAR-18, Proceedings
T2 - 18th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning, LPAR-18
Y2 - 11 March 2012 through 15 March 2012
ER -