Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2022.10
URN: urn:nbn:de:0030-drops-170732
URL: https://drops.dagstuhl.de/opus/volltexte/2022/17073/
Baier, Christel ; Funke, Florian ; Jantsch, Simon ; Karimov, Toghrul ; Lefaucheux, Engel ; Ouaknine, Joël ; Purser, David ; Whiteland, Markus A. ; Worrell, James
Parameter Synthesis for Parametric Probabilistic Dynamical Systems and Prefix-Independent Specifications
| pdf-format: |
|
Abstract
We consider the model-checking problem for parametric probabilistic dynamical systems, formalised as Markov chains with parametric transition functions, analysed under the distribution-transformer semantics (in which a Markov chain induces a sequence of distributions over states).We examine the problem of synthesising the set of parameter valuations of a parametric Markov chain such that the orbits of induced state distributions satisfy a prefix-independent ω-regular property.
Our main result establishes that in all non-degenerate instances, the feasible set of parameters is (up to a null set) semialgebraic, and can moreover be computed (in polynomial time assuming that the ambient dimension, corresponding to the number of states of the Markov chain, is fixed).
BibTeX - Entry
@InProceedings{baier_et_al:LIPIcs.CONCUR.2022.10,
author = {Baier, Christel and Funke, Florian and Jantsch, Simon and Karimov, Toghrul and Lefaucheux, Engel and Ouaknine, Jo\"{e}l and Purser, David and Whiteland, Markus A. and Worrell, James},
title = {{Parameter Synthesis for Parametric Probabilistic Dynamical Systems and Prefix-Independent Specifications}},
booktitle = {33rd International Conference on Concurrency Theory (CONCUR 2022)},
pages = {10:1--10:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-246-4},
ISSN = {1868-8969},
year = {2022},
volume = {243},
editor = {Klin, Bartek and Lasota, S{\l}awomir and Muscholl, Anca},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17073},
URN = {urn:nbn:de:0030-drops-170732},
doi = {10.4230/LIPIcs.CONCUR.2022.10},
annote = {Keywords: Model checking, parametric Markov chains, distribution transformer semantics}
}
| Keywords: | Model checking, parametric Markov chains, distribution transformer semantics | |
| Seminar: | 33rd International Conference on Concurrency Theory (CONCUR 2022) | |
| Issue date: | 2022 | |
| Date of publication: | 06.09.2022 |
