5 papers
Active Learning of Mealy Machines with Timers
Véronique Bruyère, Bharat Garhewal, Guillermo A. Pérez +2
We present the first algorithm for query learning Mealy machines with timers in a black-box context. Our algorithm is an extension of the L# algorithm of Vaandrager et al. to a tim…
Algorithms for Markov Binomial Chains
Alejandro Alarcón Gonzalez, Niel Hens, Tim Leys +1
We study algorithms to analyze a particular class of Markov population processes that is often used in epidemiology. More specifically, Markov binomial chains are the model that ar…
Composing Reinforcement Learning Policies, with Formal Guarantees
Florent Delgrange, Guy Avni, Anna Lukina +5
We propose a novel framework to controller design in environments with a two-level structure: a known high-level graph ("map") in which each vertex is populated by a Markov decisio…
Data Structures for Finite Downsets of Natural Vectors: Theory and Practice
Michaël Cadilhac, Vanessa Flügel, Guillermo A. Pérez +1
Manipulating downward-closed sets of vectors forms the basis of so-called antichain-based algorithms in verification. In that context, the dimension of the vectors is intimately ti…
Revelations: A Decidable Class of POMDPs with Omega-Regular Objectives
Marius Belly, Nathanaël Fijalkow, Hugo Gimbert +3
Partially observable Markov decision processes (POMDPs) form a prominent model for uncertainty in sequential decision making. We are interested in constructing algorithms with theo…