12 papers
Error-awareness Accelerates Active Automata Learning
Loes Kruger, Sebastian Junges, Jurriaan Rot
Active automata learning (AAL) algorithms can learn a behavioral model of a system from interacting with it. The primary challenge remains scaling to larger models, in particular i…
Incremental Fingerprinting in an Open World
Loes Kruger, Paul Kobialka, Andrea Pferscher +3
Network protocol fingerprinting is used to identify a protocol implementation by analyzing its input-output behavior. Traditionally, fingerprinting operates under a closed-world as…
Compositional Verification of Almost-Sure Büchi Objectives in MDPs
Marck van der Vegt, Kazuki Watanabe, Ichiro Hasuo +1
This paper studies the verification of almost-sure Büchi objectives in MDPs with a known, compositional structure based on string diagrams. In particular, we ask whether there is a…
Small Decision Trees for MDPs with Deductive Synthesis
Roman Andriushchenko, Milan Češka, Sebastian Junges +1
Markov decision processes (MDPs) describe sequential decision-making processes; MDP policies return for every state in that process an advised action. Classical algorithms can effi…
Relating Apartness and Branching Bisimulation Games
Jurriaan Rot, Sebastian Junges, Harsh Beohar
Geuvers and Jacobs (LMCS 2021) formulated the notion of apartness relation on state-based systems modelled as coalgebras. In this context apartness is formally dual to bisimilarity…
Policies Grow on Trees: Model Checking Families of MDPs
Roman Andriushchenko, Milan Češka, Sebastian Junges +1
Markov decision processes (MDPs) provide a fundamental model for sequential decision making under process uncertainty. A classical synthesis task is to compute for a given MDP a wi…
A PSPACE Algorithm for Almost-Sure Rabin Objectives in Multi-Environment MDPs
Marnix Suilen, Marck van der Vegt, Sebastian Junges
Markov Decision Processes (MDPs) model systems with uncertain transition dynamics. Multiple-environment MDPs (MEMDPs) extend MDPs. They intuitively reflect finite sets of MDPs that…
A Unifying Approach to Product Constructions for Quantitative Temporal Inference
Kazuki Watanabe, Sebastian Junges, Jurriaan Rot +1
Probabilistic programs are a powerful and convenient approach to formalise distributions over system executions. A classical verification problem for probabilistic programs is temp…
State Matching and Multiple References in Adaptive Active Automata Learning
Loes Kruger, Sebastian Junges, Jurriaan Rot
Active automata learning (AAL) is a method to infer state machines by interacting with black-box systems. Adaptive AAL aims to reduce the sample complexity of AAL by incorporating…
Compositional Value Iteration with Pareto Caching
Kazuki Watanabe, Marck van der Vegt, Sebastian Junges +1
The de-facto standard approach in MDP verification is based on value iteration (VI). We propose compositional VI, a framework for model checking compositional MDPs, that addresses…
Small Test Suites for Active Automata Learning
Loes Kruger, Sebastian Junges, Jurriaan Rot
A bottleneck in modern active automata learning is to test whether a hypothesized Mealy machine correctly describes the system under learning. The search space for possible counter…
Pareto Curves for Compositionally Model Checking String Diagrams of MDPs
Kazuki Watanabe, Marck van der Vegt, Ichiro Hasuo +2
Computing schedulers that optimize reachability probabilities in MDPs is a standard verification task. To address scalability concerns, we focus on MDPs that are compositionally de…