Paper accepted for LMCS

Our paper “High-level Counterexamples for Probabilistic Automata” by Ralf Wimmer, Nils Jansen, Erika Ábrahám and Joost-Pieter Katoen was accepted for publication in the journal Logical Methods in Computer Science (LMCS). In this paper we investigate the computation of several variations of (minimal) counterexamples that are represented in PRISM’s high-level language which defines a subclass of probabilistic programs. These NP-hard problems are solved via mixed-integer linear programming (MILP). The paper encompasses proofs for correctness, completeness and the complexity of the problem as well as a thorough experimental evaluation.