Soutenance de thèse de Ekaterina ARAFAILOVA

Ekaterina Arafailova, doctorante au sein de l’équipe TASC, soutiendra sa thèse intitulée « Functional Description of Sequence Constraints and Synthesis of Combinatorial Objects »

mardi 25 septembre 2018 à 14h30 à l’IMT Atlantique dans l’amphi Besse.

La soutenance aura lieu en Anglais. / The defence will be in English and will take place on Tuesday, on the 25th of September, at 14h30, at IMT Atlantique (Nantes) in the Besse amphitheatre. 

Jury : Nicolas Beldiceanu (directeur), Rémi Douence (co encadrant), Michela Milano (Rapporteur, Università di Bologna, Bologne, Italie), Stanislav Zivny (Rapporteur, University of Oxford, Oxford, Royaume-Uni), John Hooker (Carnegie Mellon University, Pittsburgh, États-Unis), Claude Jard

Résumé :
À l’opposé de l’approche consistant à concevoir au cas par cas des contraintes et des algorithmes leur étant dédiés, l’objet de cette thèse concerne d’une part la description de familles de contraintes en termes de composition de fonctions, et d’autre part la synthèse d’objets combinatoires pour de telles contraintes. Les objets concernés sont des bornes précises, des coupes linéaires, des invariants non-linéaires et des automates finis ; leur but principal est de prendre en compte l’aspect combinatoire d’une seule contrainte ou d’une conjonction de contraintes. Ces objets sont obtenus d’une façon systématique et sont paramétrés par une ou plusieurs contraintes, par le nombre de variables dans une séquence, et par les domaines initiaux de ces variables. Cela nous permet d’obtenir des objets indépendants d’une instance considérée. Afin de synthétiser des objets combinatoires nous tirons partie de la vue déclarative de telles contraintes, basée sur les expressions régulières, ansi que la vue opérationnelle, basée sur les automates à registres et les transducteurs finis. Il y a plusieurs avantages à synthétiser des objets combinatoires par rapport à la conception d’algorithmes dédiés : 1) on peut utiliser ces formules paramétrées dans plusieurs contextes, y compris la programmation par contraintes et la programmation linéaire, ce qui est beaucoup plus difficile avec des algorithmes ; 2) la synergie entre des objets combinatoires nous donne une meilleure performance en pratique ; 3) les quantités calculées par certaines des formules peuvent être utilisées non seulement dans le contexte de l’optimisation mais aussi pour la fouille de données.

Mots- clés : programmation par contraintes, automates, transducteurs, expressions régulières, séries temporelles, objets combinatoires paramétrés, invariants linéaires et non-linéaires

*********

Abstract:
Contrary to the standard approach consisting of introducing ad hoc constraints and designing dedicated algorithms for handling their combinatorial aspect, this thesis takes another point of view. On the one hand, it focusses on describing a family of sequence constraints in a compositional way by multiple layers of functions. On the other hand, it addresses the combinatorial aspect of both a single constraint and a conjunction of such constraints by synthesising compositional combinatorial objects, namely bounds, linear inequalities, non-linear constraints and finite automata. These objects are obtained in a systematic way and are not instance-specific: they are parameterised by one or several constraints, by the number of variables in a considered sequence of variables, and by the initial domains of the variables. When synthesising such objects we draw full benefit both from the declarative view of such constraints, based on regular expressions, and from the operational view, based on finite transducers and register automata.
There are many advantages of synthesising combinatorial objects rather than designing dedicated algorithms: 1) parameterised formulae can be applied in the context of several resolution techniques such as constraint programming or linear programming, whereas algorithms are typically tailored to a specific technique; 2) combinatorial objects can be combined together to provide better performance in practice; 3) finally, the quantities computed by some formulae can not just be used in an optimisation setting, but also in the context of data mining.

Keywords: constraint programming, automata, transducers, regular expressions, time series, parameterised combinatorial objects, linear and non-linear invariants