Prochain Exposé
Mercredi 17 octobre, 14h en salle Aurigny
Filip Mazowiecki
When is Containment Decidable for Probabilistic Automata?
The containment problem for quantitative automata is the natural quantitative generalisation of the classical language inclusion problem for Boolean automata. We study it for probabilistic automata, where it is known to be undecidable in general. We restrict our study to the class of probabilistic automata with bounded ambiguity. There, we show decidability (subject to Schanuel's conjecture) when one of the automata is assumed to be unambiguous while the other one is allowed to be finitely ambiguous. Furthermore, we show that this is close to the most general decidable fragment of this problem by proving that it is already undecidable if one of the automata is allowed to be linearly ambiguous.
Exposés des semaines suivantes
Vos propositions sont les bienvenues !
Jeudi 15 novembre, 14h en salle Aurigny
Nathan Lhote
Logics for Transductions
Logics over words such as Monadic Second-Order Logic, or Linear Temporal Logic provide a way to specify properties of systems in a high-level formalism, close to natural language. From such formulas one would like to decide properties such as satisfiability, model-checking or synthesis problems, and the tight links between logics and automata have provided effective procedures to do so. We present several attempts to generalize some well-known results from languages to transductions (i.e. functions from words to words).
