Search

Two major approaches in synthesis consist in specifying either the worst case behaviour or specifying the stochastic behaviour of a system. This thesis aims at studying the interplays of sure and stochastic conditions by considering algorithms to decide the existence of strategies in Markov decision processes for combinations of objectives. These objectives are omega-regular properties expressed as parity conditions, that need to be enforced either surely, almost surely, or with some threshold probability. In this setting, relevant strategies are randomized infinite memory strategies: both infinite memory and randomization may be needed to play optimally. We provide algorithms and complexity bounds for three main problems. First, we study multiple sure objectives, and multiple almost-sure objectives. Second, we consider Boolean combinations of sure objectives and multiple almost-sure objectives. Third, we consider one sure objective, and stochastic objectives that have to hold with a given probability threshold.

We prove that the theory of Monadic Second-Order logic (MSO) of the infinite binary tree extended with qualitative path-measure quantifier is undecidable. This quantifier says that the set of infinite paths in the tree that satisfies some formula has Lebesgue-measure one. To do this we prove that the emptiness problem of qualitative universal parity tree automata is undecidable. Qualitative means that a run of a tree automaton is accepting if the set of paths in the run that satisfy the acceptance condition has Lebesgue-measure one.

International audience; Free Data Structures are finite semantic trees modulo equational axioms that are useful to represent classical data structures such as lists, multisets and sets. We study the satisfiability problem when free data structures are combined with bridging functions. We discuss the possibility to get a combination methodàmethod`methodà la Nelson-Oppen for these particular non-disjoint unions of theories. In order to handle satisfiability problems with disequalities, we investigate a form of sufficient surjectivity for the bridging functions.