Sound over-approximation of probabilities
(2020) In Acta Cybernetica 24(3). p.269-285- Abstract
Safety analysis of high confidence systems requires guaranteed bounds on the probabilities of events of interest. Establishing the correctness of algorithms that aim to compute such bounds is challenging. We address this problem in three steps. First, we use monadic transition systems (MTS) in the category of sets as a framework for modeling discrete time systems. MTS can capture different types of system behaviors, but we focus on a combination of non-deterministic and probabilistic behaviors that often arises when modeling complex systems. Second, we use the category of posets and monotonic maps as a setting to define and compare approximations. In particular, for the MTS of interest, we consider approximations of their configurations... (More)
Safety analysis of high confidence systems requires guaranteed bounds on the probabilities of events of interest. Establishing the correctness of algorithms that aim to compute such bounds is challenging. We address this problem in three steps. First, we use monadic transition systems (MTS) in the category of sets as a framework for modeling discrete time systems. MTS can capture different types of system behaviors, but we focus on a combination of non-deterministic and probabilistic behaviors that often arises when modeling complex systems. Second, we use the category of posets and monotonic maps as a setting to define and compare approximations. In particular, for the MTS of interest, we consider approximations of their configurations based on complete lattices. Third, by restricting to finite lattices, we obtain algorithms that compute over-approximations, i.e., bounds from above within some partial order of approximants, of the system configuration after n steps. Interestingly, finite lattices of “interval probabilities” may fail to accurately approximate configurations that are both non-deterministic and probabilistic, even for deterministic (and continuous) system dynamics. However, better choices of finite lattices are available.
(Less)
- author
- Moggi, Eugenio ; Taha, Walid and Thunberg, Johan LU
- publishing date
- 2020
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- Approximation, Intervals, Monads, Probabilities
- in
- Acta Cybernetica
- volume
- 24
- issue
- 3
- pages
- 17 pages
- publisher
- University of Szeged, Institute of Informatics
- external identifiers
-
- scopus:85085269748
- ISSN
- 0324-721X
- DOI
- 10.14232/ACTACYB.24.3.2020.2
- language
- English
- LU publication?
- no
- additional info
- Publisher Copyright: © 2020 University of Szeged, Institute of Informatics. All rights reserved.
- id
- d61212cf-7d6e-4bec-ae21-73ae6139a995
- date added to LUP
- 2024-09-05 12:26:59
- date last changed
- 2025-04-04 14:43:13
@article{d61212cf-7d6e-4bec-ae21-73ae6139a995,
abstract = {{<p>Safety analysis of high confidence systems requires guaranteed bounds on the probabilities of events of interest. Establishing the correctness of algorithms that aim to compute such bounds is challenging. We address this problem in three steps. First, we use monadic transition systems (MTS) in the category of sets as a framework for modeling discrete time systems. MTS can capture different types of system behaviors, but we focus on a combination of non-deterministic and probabilistic behaviors that often arises when modeling complex systems. Second, we use the category of posets and monotonic maps as a setting to define and compare approximations. In particular, for the MTS of interest, we consider approximations of their configurations based on complete lattices. Third, by restricting to finite lattices, we obtain algorithms that compute over-approximations, i.e., bounds from above within some partial order of approximants, of the system configuration after n steps. Interestingly, finite lattices of “interval probabilities” may fail to accurately approximate configurations that are both non-deterministic and probabilistic, even for deterministic (and continuous) system dynamics. However, better choices of finite lattices are available.</p>}},
author = {{Moggi, Eugenio and Taha, Walid and Thunberg, Johan}},
issn = {{0324-721X}},
keywords = {{Approximation; Intervals; Monads; Probabilities}},
language = {{eng}},
number = {{3}},
pages = {{269--285}},
publisher = {{University of Szeged, Institute of Informatics}},
series = {{Acta Cybernetica}},
title = {{Sound over-approximation of probabilities}},
url = {{http://dx.doi.org/10.14232/ACTACYB.24.3.2020.2}},
doi = {{10.14232/ACTACYB.24.3.2020.2}},
volume = {{24}},
year = {{2020}},
}