LRE, EPITA, salle KB203, elle se trouve au deuxième étage du bâtiment principal. On flèchera le chemin depuis de RdC.
Abstract : Le diagnostic et/ou la prédiction de fautes dans un systèmes à événements discrets partiellement observable constitue un objectif majeur de la gestion de tels systèmes. Dans cet exposé, nous aborderons les aspects sémantiques et algorithmiques de ces notions. Du point de vue sémantique, nous introduirons et comparerons les différentes formalisations selon que (1) le système soit contrôlable ou non, et (2) le système ait un comportement non déterministe ou probabiliste. Puis nous étudierons la décidabilité et la complexité algorithmique de problèmes liés à ces notions. Enfin si le temps le permet dans le cas contrôlable, nous exhiberons des bornes inférieures et supérieures de la taille mémoire requise par un "diagnostiqueur actif" (i.e., un contrôleur exécutant la tâche de diagnostic).
Abstract : Active automata learning (AAL) under a Minimally Adequate Teacher (MAT) has been successfully used to infer a regular language through membership and equivalence queries. This language might not be fully characterized: we are thus interested in finding any solution in a target class of possibly many regular languages. Some problems such as regular language separation or inductive invariant synthesis in the con- text of regular model checking (RMC) may indeed admit more than one answer. We therefore introduce IdMAT: a new teacher formalism answer- ing queries with respect to any language in the target class, all at once. Such a teacher—tailored towards invariant synthesis—might provide in- complete “don’t know” answers, but also inductive facts of the form “if w1 is accepted, so is w2 ”. We pair IdMAT with a novel AAL algorithm LIndA that 1. encodes all uncertainties as a unique SAT instance and does not fork, 2. leverages incremental SAT solving and UNSAT core analysis, and 3. handles counterexamples—of the simple or inductive type—in a frugal manner inspired by the Rivest-Schapire refinement technique. Joint work with Adrien Pommellet and Juliette Jacquot.