Tractable Hyperproperties for MDPs

Lina Gerlach, Tobias Winkler, Erika Ábrahám, Borzoo Bonakdarpour, Sebastian Junges · 2026

Read Tractable Hyperproperties for MDPs by Lina Gerlach, Tobias Winkler, Erika Ábrahám, Borzoo Bonakdarpour, Sebastian Junges (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-06859.txt.

Description

Gerlach and four colleagues carve out a checkable corner of probabilistic hyperproperties, which compare chances across several runs of a random system. Full versions of these logics cannot be decided for Markov decision processes. The authors therefore focus on relations between event probabilities, covering reachability, safety, and repeated-visit goals that can also be combined. They give fast algorithms for some cases, hardness results for others, and a tool that beats general solvers by wide margins on shared benchmarks.

Catalog record

CREATORLina Gerlach, Tobias Winkler, Erika Ábrahám, Borzoo Bonakdarpour, Sebastian Junges
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE888861
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.06859

Browse the full library · About the Tower of Babel