Bertrand et al. (2017) introduced a model of parameterised
systems, where each agent is represented by a finite state system, and
studied the following control problem: for any number of agents, does
there exist a controller able to bring all agents to a target state? They
showed that the problem is decidable and EXPTIME-complete in the
adversarial setting, and posed as an open problem the stochastic setting,
where the agent is represented by a Markov decision process. In this
paper, we show that the stochastic control problem is decidable. Our
solution makes significant uses of well quasi orders, of the max-flow min-
cut theorem, and of the theory of regular cost functions.

Afin d’étudier les propriétés combinatoires des suites infinies, une approche fructueuse consiste à étudier un sous-shift, i.e. un ensemble fermé de suites, invariant par l’action du shift (décalage), associé à ces suites. La théorie des systèmes dynamiques fournit alors des outils pertinents.
Une question classique consiste alors à étudier les symétries de ces systèmes dynamiques, i.e. les auto-conjugaison du système. Dans ce contexte, Morse et Hedlund ont montré que ces auto-conjugaisons correspondent aux automates cellulaires préservant le sous-shift.
Le groupe engendré par ces transformations est toujours dénombrable en général difficile à décrire.
Dans cet exposé, nous présenterons un survol de récentes avancées dans l’étude de ce groupe et notamment ses relations avec la complexité du système symbolique.

Énumérer des objets est une tâche courante en informatique,  que ça soit pour les compter, trouver une solution optimale ou constituer une librairie d’objets intéressants.  Un problème typique est de devoir gérer la répétition d’objets identiques (donc inutiles) lors du processus d’énumération. La seule difficulté dans l’énumération des modèles d’une formule DNF est de cette nature. Cela a pour conséquence que les algorithmes habituels utilisent un temps linéaire en la taille de la formule par modèle. Les modèles pouvant être exponentiellement plus petit que la formule, on voudrait donc obtenir un temps linéaire (ou polynomial) en chaque modèle. Nous conjecturons que de tels algorithmes n’existent pas. Néanmoins nous allons montrer comment on peut relâcher le problème ou restreindre les entrées et ainsi proposer plusieurs techniques pour générer ces modèles en temps sous linéaire (par solution générée) voire en temps constant.

In this talk, we will show how one can augment classes of Boolean
circuits used in knowledge compilation so that one can efficiently check that
they are equivalent to a given CNF formula. We will show that it can be applied
to define Cook-Reckhow proof systems for #SAT and maxSAT and how one can use
this idea to output certificates from existing tools solving #SAT.

Un grand nombre d’automates cellulaires ont été donnés sous forme de table de transition construite à la main. La méthodologie des “champs cellulaires” donne les principes de conception modulaire et de génération de la table de transition en dernière étape, comme c’est le cas pour le code source d’un langage de programmation de haut niveau et leur fichier exécutable binaire. Nous vérifions si les tables ainsi générées peuvent être optimisées pour être aussi petites que leurs contreparties construites à la main. Ceci est fait dans le cas particulier d’un automate cellulaire qui résout le problème de synchronisation des fusiliers (Firing Squad Synchronization problem en anglais) en utilisant des champs cellulaires. Nous étudions la structure interne de cette solution et ainsi que des notions de réduction dans la même veine que la minimisation des automates finis déterministe. La comparaison est faite avec la solution “à la main” de Noguchi.

The valued constraint satisfaction problem (VCSP) is a framework for describing and studying many classes of discrete optimisation problems. It is an optimisation version of the constraint satisfaction problem (CSP), where the goal is to decide whether one can assign labels to variables under some given set of constraints. The VCSP captures both Max CSP-type problems, where one wants to optimise the number of satisfied constraints, and integer programming-type problems, where one adds an objective function to an ordinary CSP to indicate the desirability of each solution.

I will talk about algorithms and hardness results for VCSPs where we restrict the types of cost functions that are allowed to appear in the description of an instance. The algorithms that I consider are based on linear programming (LP), in particular LP relaxations in the Sherali-Adams hierarchy. It turns out that for large classes of VCSPs, there is a complete dichotomy between problems that can be solved by this type of algorithm and problems that can encode NP-hard problems.

Les sous-shifts sont des coloriages de $\mathbb{Z}^d$ verifiant des contraintes locales. Très tôt l’étude de sous-shifts en dimension supérieure à 2 a vu deux notions apparaître naturellement : l’apériodicité et l’indécidabilité. Nous explorons ces deux notions dans ce manuscrit, la seconde par le prisme de différentes notions de complexité, puis nous introduisons un nouveau regard sur les sous-shifts par le biais d’analogies avec la théorie des groupes.

Les sous-shifts sans point périodique, dits apériodiques, ont fait leur apparition avec la construction de Berger prouvant l’indécidabilité de la pavabilité du plan avec le formalisme des tuiles de Wang. Les sous-shifts apériodiques
ont ensuite été l’ingrédient principal de la plupart des constructions. Dans ce document nous nous intéressons
à la notion duale qui consiste à contenir un point apériodique. Nous montrons que les sous-shifts contenant un
point apériodique en contiennent toujours avec une apériodicité régulière : dans des boules concentriques
dont le rayon ne dépend que de la période.

La complexité dans les sous-shifts peut prendre plusieurs formes. Nous illustrons ici les différents liens qui unissent certaines de ces notions de complexité : complexité de Kolmogorov, complexité des configurations via le spectre des degrés Turing, ainsi que complexité au sens du nombre de motifs.

Nous introduisons en fin de manuscrit des analogies avec la théorie des groupes qui nous permettent d’énoncer
des analogues aux théorèmes de Higman dans le cadre des sous-shifts.