Certificates and Witnesses for Multi-objective ω \omega -regular Queries in Markov Decision Processes
Christel Baier, Calvin Chau, Volodymyr Drobitko, Simon Jantsch, Sascha Klüppelholz · 2025
Read Certificates and Witnesses for Multi-objective ω \omega -regular Queries in Markov Decision Processes by Christel Baier, Calvin Chau, Volodymyr Drobitko, Simon Jantsch, Sascha Klüppelholz (2025) 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-2508-17859.txt.
Introduction
Christel Baier and four co-authors create checkable proof objects for multi-goal checks of uncertain systems, in a paper from 2025. Probabilistic model checking verifies systems against several possibly conflicting goals at once. Trusting the tool's bare yes or no is risky, so evidence matters.
They improve certificates for splitting systems into end components and for reachability claims, so others can verify results independently. Minimal witness subsystems are found through integer programming formulations. For plain Markov chains with temporal logic goals, a smarter automaton method needs only single-exponential space instead of double. An implementation and experiments show the approach works in practice.
Catalog record
| CREATOR | Christel Baier, Calvin Chau, Volodymyr Drobitko, Simon Jantsch, Sascha Klüppelholz |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 24 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-17859
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Certificates and Witnesses for Multi-objective ω \omega -regular Queries in Markov Decision Processes Thanks: The authors were supported by the German Federal Ministry of Education and Research (BMBF) within the project SEMECO Q1 (03ZU1210AG) and by the German Research Foundation (DFG) through the Cluster of Excellence EXC 2050/1 (CeTI, project ID 390696704, as part of Germany’s Excellence Strategy) and the DFG Grant 389792660 as part of TRR 248 (Foundations of Perspicuous Software System). Christel Baier, Calvin Chau, Volodymyr Drobitko, Simon Jantsch, Sascha Klüppelholz Abstract Multi-objective probabilistic model checking is a powerful technique for verifying stochastic systems against multiple (potentially conflicting) properties. To enhance the trustworthiness and explainability of model checking tools, we present independently checkable certificates and witnesses for multi-objective ω \omega -regular queries in Markov decision processes. For the certification, we extend and improve existing certificates for the decomposition of maximal end components and reachability properties. We then derive mixed-integer linear programs (MILPs) for finding minimal witnessing subsystems . For the special case of Markov chains and LTL properties, we use unambiguous Büchi automata to find witnesses, resulting in an algorithm that requires single-exponential space. Existing approaches based on deterministic automata require doubly-exponential space in the worst case. Finally, we consider the practical computation of our certificates and witnesses and provide an implementation of the developed techniques, along with an experimental evaluation, demonstrating the efficacy of our techniques. 1 Introduction Probabilistic model checking (PMC) is a well-established approach for analysing and formally verifying stochastic systems, e.g. randomized algorithms or security systems [ kwiatkowsa_prism_2012 , hartmanns_quantitative_2019 ] . Model checkers, like Prism [ kwiatkowska_prism_2011-1 ] or Storm [ hensel_probabilistic_2022 ] , receive a probabilistic model of the system and formal specification and output whether the specification is satisfied. Unsurprisingly, as with any complex software, model checkers have been observed to contain bugs [ wimmer_demand_2008 ] . In the context of verifying (safety-critical) systems, this raises the question of how to ensure that model checking results can be trusted. An approach for mitigating this issue are certifying algorithms [ mcconnell_certifying_2011 ] which also return a certificate accompanying the result. This can be used to independently verify the correctness of the result. Another challenge for PMC is the explication of verification results. When a system fails to meet the specification, it is desirable to obtain diagnostic information that allows the user to understand the behavior and debug the system. Indeed, counterexample traces are a crucial feature of classical model checking techniques in practice. A canonical notion of explication does not exist for PMC, e.g. sets of paths [ han_counterexample_2009-1 , aljazzar_generation_2009-1 ] or subsystems [ jansen_hierarchical_2011 , wimmer_minimal_2012 , jansen_counterexamples_2015 , funke_farkas_2020 ] have been considered. Witnessing subsystems are parts of the system that on their own violate (or satisfy) the specification and can therefore serve as useful explications. This work addresses the certification and computation of witnesses for multi-objective \omega -regular queries in Markov decision processes (MDPs) [ puterman_markov_1994 ] . MDPs are the standard model for systems with stochastic and nondeterministic behavior. Further, multi-objective \omega -regular queries are expressive formalisms, enabling the specification of multiple (possibly conflicting) requirements [ etessami_multi-objective_2008 ] . For instance, for a server system one might specify that “every request is served with probability greater than 0.9 ” while “the probability of failure is less than 0.01 ” [ etessami_multi-objective_2008 , forejt_quantitative_2011 ] . To provide certificates, we revisit the steps of the verification procedure for these queries (e.g. [ forejt_quantitative_2011 ] ) and make them certifying. More precisely, we devise certificates for the classification of end components based on the properties they satisfy. Further, we improve on the certification of the decomposition into maximal end components (MECs) [ de_alfaro_formal_1997 ] from [ jantsch_certificates_2022 ] , using recent ideas from [ chatterjee_fixed_2025 ] , and provide a first implementation thereof. The MEC decomposition is a common preprocessing step in PMC, and its certification is thus interesting on its own. In combination with previous work on multi-objective reachability queries [ baier_certificates_2024 ] , this allows us to devise sound and complete certificates for \omega -regular queries. Our certificates can then be used to independently validate that a query is indeed satisfied (or violated), thereby enhancing trust in the verification process. As in the setting of reachability queries [ funke_farkas_2020 , jantsch_certificates_2022 , baier_certificates_2024 ] , we show that our certificates induce witnessing subsystems . Since small witnesses highlight critical parts of the MDP and might be easier to understand, we present algorithms based on mixed-integer linear programs (MILPs) for computing minimal witnessing subsystems . For the special case of discrete-time Markov chains (DTMCs) and LTL properties, we devise a novel algorithm for computing minimal witnesses based on unambiguous Büchi automata (UBAs). Checking DTMCs against probabilistic LTL specifications is PSPACE -complete [ baier_markov_2023-1 ] , implying that minimal witnesses can be computed in PSPACE by enumerating and checking all subsystems. As this is impractical, previous approaches relied on computing deterministic Rabin automata (DRAs) [ jansen_counterexamples_2015 ] , requiring doubly-exponential space. Instead, we define a single-exponential MILP based on the product of the DTMC with a UBA for the LTL property, building on results for model checking DTMCs against UBAs [ baier_markov_2023-1 ] , which is possible in PTIME . Proofs are in the appendix and the implementation and data are given in [ baier_2025_15680332 ] . Contributions. • We devise certificates for the satisfaction (resp. violation) of Rabin properties in end components and improve the certification of the MEC decomposition ( ) from [ jantsch_certificates_2022 ] based on ideas from [ chatterjee_fixed_2025 ] . • In we present certificates for multi-objective queries with \omega -regular properties in MDPs which are composed of the aforementioned certificates and the certificates for multi-objective reachability from [ baier_certificates_2024 ] . We also discuss the computation of the latter via the algorithm of [ forejt_pareto_2012 ] . • presents techniques for computing minimal witnessing subsystems for multi-objective \omega -regular queries, supporting various minimality criteria. • For LTL queries in DTMCs, we give a single-exponential algorithm for computing minimal witnessing subsystems, utilizing unambiguous Büchi automata ( ). • All presented techniques are implemented in an efficient C ++ tool built on top of Storm , for which we provide an experimental evaluation ( ). Related work. Multi-objective queries in MDPs have been extensively studied, e.g. in [ etessami_multi-objective_2008 , forejt_quantitative_2011 , forejt_pareto_2012 , randour_percentile_2015 , quatmann_verification_2023 ] . Techniques for verifying multi-objective \omega -regular queries based on LPs are presented in [ etessami_multi-objective_2008 , forejt_quantitative_2011 ] , where [ forejt_quantitative_2011 ] considers queries with rewards. The works of [ forejt_pareto_2012 , quatmann_verification_2023 ] consider the verification of multi-objective queries via value iteration. Queries with mean-payoff objectives have been studied in [ 10.1109/LICS.2011.10 ] . In [ randour_percentile_2015 ] complexity results for percentile queries are established. Certifying verification algorithms have not been considered in the mentioned works. Farkas certificates [ funke_farkas_2020 , jantsch_certificates_2022 ] certify single constraints on reachability probabilities in MDPs. They are solutions to linear inequalities, derived from known LP characterizations [ puterman_markov_1994 ] , and can also be used to obtain minimal witnessing subsystems . Certificates for the MEC decomposition are presented in [ jantsch_certificates_2022 ] , however without implementation. The work