SMT-based Searching for k -quasi-optimal Runs in Weighted Timed Automata
Fundamenta Informaticae · 10.05.2017 · 152 (4) · 411-433
DOI: 10.3233/fi-2017-1527 ↗Kurz gefasst
Fachartikel in der Zeitschrift Fundamenta Informaticae, online erschienen am 10.05.2017. Verfasst von Bożena Woźna-Szcześniak und 2 weiteren Autor:innen. Die Arbeit wurde bisher 6-mal zitiert (Crossref).
Abstract (Originalsprache)
We investigate a quasi-optimal cost reachability problem for weighted timed automata. We use a translation to the satisfiability modulo theories (SMT) problem to solve the problem. In particular, we show how to find a run of length k ∈ IN that starts at the initial state and terminates at a state containing the target location, its total cost belongs to the interval [ c; c + 1), for some natural number c ∈ IN, and the cost of each other run of length k, which also leads from the initial state to a state containing the target location, is greater or equal to c. This kind of run is called k- quasi- optimal. We exemplify the use of our solution to the investigated problem by means of the weighted timed generic pipeline protocol and the weighted job shop scheduling problem, and we provide some preliminary experimental results.
Zitieren
APA
Woźna-Szcześniak, B., Zbrzezny, A. M., & Zbrzezny, A. (2017). SMT-based Searching for k -quasi-optimal Runs in Weighted Timed Automata. Fundamenta Informaticae, 152(4), 411-433. https://doi.org/10.3233/fi-2017-1527
Vancouver
Woźna-Szcześniak B, Zbrzezny AM, Zbrzezny A. SMT-based Searching for k -quasi-optimal Runs in Weighted Timed Automata. Fundamenta Informaticae. 2017;152(4):411-433. doi:10.3233/fi-2017-1527
BibTeX
@article{WonaSzczeniak2017,
author = {Woźna-Szcześniak, Bożena and Zbrzezny, Agnieszka M. and Zbrzezny, Andrzej},
title = {SMT-based Searching for k -quasi-optimal Runs in Weighted Timed Automata},
journal = {Fundamenta Informaticae},
year = {2017},
volume = {152},
number = {4},
pages = {411--433},
doi = {10.3233/fi-2017-1527}
}
EUVIMED