## Automata

#### Day, hour and place

#### Contact(s)

### Next talk

### Previous talks

#### Year 2019

Automata

Friday May 17, 2019, 2:30PM, Salle 3052

**Jeremy Sproston** (Université de Turin) *Probabilistic Timed Automata with Clock-Dependent Probabilities*

Automata

Friday May 3, 2019, 2:30PM, Salle 3052

**Sam Van Gool** (Utrecht University) *Separation and covering for varieties determined by groups*

The covering problem for the variety of star-free languages was shown to be decidable by Henckell. In fact, he gave an algorithm for an equivalent problem, namely, computing the pointlike subsets of a finite semigroup with respect to the variety of aperiodic semigroups, i.e., semigroups all of whose subgroups are trivial.

In this talk, I will present the following wide generalization of Henckell's result. Let H be any decidable variety of groups. I will describe an algorithm for computing pointlike sets for the variety of semigroups all of whose subgroups are in H. The correctness proof for the algorithm uses asynchronous transducers, Schützenberger groups, and self-similarity. An application of our result is the decidability of the covering and separation problems for the variety of languages definable in first order logic with modular counting quantifiers.

This talk is based on our paper S. v. Gool & B. Steinberg, Adv. in Math. 348, 18-50 (2019).

Automata

Friday March 29, 2019, 2:30PM, Salle 3052

**Anaël Grandjean** *Points apériodiques dans la sous shifts de dimension 2*

Quelle est la complexité calculatoire de déterminer si un jeu de tuiles (espace de type fini) possède un point apériodique ? Comment se comportent les espaces de pavages ne possédant aucun point apériodique ?

Nous montrons qu’un espace de pavage 2D sans point apériodique a une structure très forte : il est “équivalent” (presque conjugué) à un espace de pavage 1D, et ce résultat s’applique aux espaces de type fini ou non. Nous en déduisons que le problème de posséder un point apériodique est co-récursivement-énumérable-complet, et que la plupart des propriétés et méthodes propres au cas 1D s’appliquent aux espaces 2D sans point apériodique. La situation en dimension supérieure semble beaucoup moins claire.

Cet exposé est issu d’une collaboration avec Benjamin Hellouin de Menibus et Pascal Vanier.

Automata

Tuesday March 26, 2019, 1PM, Salle 3052

**Francesco Dolce** (Université Paris Diderot, IRIF) *Generalized Lyndon words*

Automata

Friday March 22, 2019, 2:30PM, Salle 3052

**Reem Yassawi** (CNRS, Institut Camille Jordan - Université Lyon 1 - Claude Bernard) *Versions quantitatives du théorème de Christol*

Andrew Bridy a récemment donne une démonstration du théorème de Christol en utilisant des outils qui proviennent de la géométrie algébrique. Avec cette démonstration il majore le nombre d’états par une borne qui est optimale. Nous obtenons des bornes presque semblables par une démonstration élémentaire, et nous traçons les liens entre notre démonstration et celle de Bridy. Ceci est un travail en commun avec Boris Adamczewski.

Automata

Friday March 15, 2019, 2:30PM, Salle 3052

**Mateusz Skomra** (ÉNS Lyon) *Condition numbers of stochastic mean payoff games and what they say about nonarchimedean convex optimization*

The talk is based on joint works with X. Allamigeon, S. Gaubert, and R. D. Katz.

Automata

Friday March 8, 2019, 2:30PM, Salle 3052

**Lama Tarsissi** (Université Marne-la-Vallée, Paris Est) *Christoffel words and applications.*

Automata

Friday February 15, 2019, 2:30PM, Salle 3052

**Alexandre Vigny** (Université Paris Diderot) *Query enumeration and nowhere dense classes of graphs*

In this talk I will talk about some restrictions for which such algorithms exist: graphs with bounded degree, tree-like structures, conjunctive queries… We will more specifically consider nowhere dense classes of graphs: What are they? Why is this notion relevant? How to make algorithms from these graph properties?

Automata

Friday February 8, 2019, 2:30PM, Salle 3052

**Paul-André Melliès** (IRIF) *Higher-order parity automata*

You will find the extended abstract of the talk here: https://www.irif.fr/~mellies/papers/higher-order-parity-automata.pdf

Automata

Friday February 1, 2019, 2:30PM, Salle 3052

**Elise Vandomme** (Université Technique Tchèque de Prague) *New notions of recurrence in a multidimensional setting*

Automata

Friday January 25, 2019, 2:30PM, Salle 3052

**Nathan Grosshans** *The power of programs over monoids taken from some small varieties of finite monoids*

Automata

Friday January 18, 2019, 2:30PM, Salle 3052

**Adrien Boiret** *Learning Top-Down Tree Transducers using Myhill Nerode or Lookahead*

- first, by an extension of the Myhill-Nerode theorem on DTOP to the regular case, by defining a minimal *leftmost* earliest compatible normal form.
- second, by reducing the problem to top-down domains, by using the regular inspection as a lookahead

The merits of these methods will be discussed for possible extensions of these methods to data trees.

Automata

Friday January 11, 2019, 2:30PM, Salle 3052

**Olivier Carton** (IRIF) *Discrepancy and nested perfect necklaces*

#### Year 2018

Automata

Friday December 21, 2018, 2:30PM, Salle 3052

**Jérôme Leroux** (LaBRI) *The Reachability Problem for Petri Nets is Not Elementary*

Joint work with Wojciech Czerwinski, Slawomir Lasota, Ranko Lazic, Filip Mazowiecki.

Automata

Friday December 14, 2018, 2:30PM, Salle 3052

**Colin Riba** (École Normale Supérieure de Lyon) *A Curry-Howard approach to tree automata*

Automata

Friday December 7, 2018, 2:30PM, Salle 3058

**Antoine Amarilli** (Télécom ParisTech) *Topological Sorting under Regular Constraints*

Our work shows that CTS[K] is tractable when K falls in several language families, e.g., unions of monomials, which can be used for pattern matching. However, we can show that CTS[K] is NP-hard for K = (ab)^* using a shuffle reduction technique that we can use to show hardness for more languages. We also study the special case of the constrained shuffle problem (CSh), where the input graph is a disjoint union of strings, and show that CSh[K] is additionally tractable when K is a group language or a union of district group monomials. We conjecture that a dichotomy should hold on the complexity of CTS[K] or CSh[K] depending on K, and substantiate this by proving a coarser dichotomy under a different problem phrasing which ensures that tractable languages are closed under common operators.

Automata

Friday November 30, 2018, 2:30PM, Salle 3052

**Dominique Perrin** (Université Paris-Est Marne-la-Vallée) *Groups, languages and dendric shifts*

Automata

Friday November 23, 2018, 2:30PM, Salle 3052

**Sébastien Labbé** (IRIF) *Structure substitutive des pavages apériodiques de Jeandel-Rao*

Automata

Friday November 16, 2018, 2:30PM, Salle 358

**Manon Stipulanti** (Université de Liège) *A way to extend the Pascal triangle to words*

Automata

Friday November 9, 2018, 2:30PM, Salle 358

**Fabian Reiter** (LSV) *Counter Machines and Distributed Automata: A Story about Exchanging Space and Time*

This is joint work with Olivier Carton and Bruno Guillon.

Automata

Friday October 19, 2018, 2:30PM, Salle 3052

**Andrew Rizhikov** (University Paris-Est Marne-la-Vallée) *Finding short synchronizing and mortal words for prefix codes*

Automata

Friday October 5, 2018, 2:30PM, Salle 3052

**Sam Van Gool** (University of Amsterdam, ILLC) *To be announced.*

Automata

Friday June 29, 2018, 2:30PM, Salle 3052

**Jacques Sakarovitch** (IRIF/CNRS and Telecom ParisTech) *The complexity of carry propagation for successor functions*

We address the problem of the existence of the amortized carry propagation and of its value in non-standard numeration systems of various kinds: abstract numeration systems, rational base numeration systems, greedy numeration systems and beta-numeration.

We tackle the problem by means of techniques of three different types: combinatorial, algebraic, and ergodic.

For each kind of numeration systems that we consider, the relevant method allows to establish sufficient conditions for the existence of the carry propagation and examples show that these conditions are close to be necessary.

This is a joint work with Valérie Berthé, Christiane Frougny, and Michel Rigo

Automata

Friday June 22, 2018, 2:30PM, Salle 3052

**Nathanaël Fijalkow** (LABRI) *Where the universal trees grow*

This is based on two joint works, the first with Wojtek Czerwinski, Laure Daviaud, Marcin Jurdzinski, Ranko Lazic, and Pawel Parys, and the second with Thomas Colcombet.

Automata

Friday June 15, 2018, 2:30PM, Salle 3052

**Pierre Ohlmann** (IRIF) *Unifying non-commutative arithmetic circuit lower bounds*

Automata

Wednesday June 13, 2018, 3PM, Salle 3052

**Joël Ouaknine** (Max Planck Institute) *Program Invariants*

This is joint work with Ehud Hrushovski, Amaury Pouly, and James Worrell.

Automata

Friday June 1, 2018, 2:30PM, Salle 3052

**Ines Klimann** (IRIF) *Groups generated by bireversible Mealy automata: a combinatorial explosion*

This talk originates in the following question: is it decidable if an automaton group has intermediate growth? I will show that in the case of bireversible automata, whenever there exists at least one element of infinite order, the growth of the group is necessarily exponential.

(This work will be presented at ICALP'18.)

Automata

Friday May 25, 2018, 2:30PM, Salle 3052

**Ulrich Ultes-Nitsche** (University of Fribourg) *A Simple and Optimal Complementation Algorithm for Büchi-Automata*

Automata

Friday May 18, 2018, 2:30PM, Salle 3052

**Irène Guessarian** (IRIF) *Congruence preservation, treillis et reconnaissabilite*

Automata

Friday April 20, 2018, 2:30PM, Salle 3052

**Davide Mottin** (Hasso Platner Institute) *Graph Exploration: Graph Search made Easy*

The talk shows how graph exploration can considerably support any analysis on graphs in a fresh and exciting manner, by combining interactive methods, personalized results, adaptive structures, and scalable algorithms. I describe the recent efforts for a graph exploration stack which supports interactivity, personalization, adaptivity, and scalability through intuitive and efficient techniques we recently proposed. The current methods show encouraging results in reducing the effort of experts and novice users in finding the information of interests through example-based approaches, personalized summaries, and active learning theories. Finally, I present the vision for the future in graph exploration research and show the chief challenges in databases, data analysis, and machine learning.

Automata

Friday April 13, 2018, 2:30PM, Salle 3052

**Denis Kuperberg** (ÉNS Lyon) *Width of non-deterministic automata*

Automata

Friday April 6, 2018, 2:30PM, Salle 3052

**Victor Marsault** (LFCS, University of Edinburgh) *Formal semantics of the query-language Cypher*

Automata

Friday March 30, 2018, 2:30PM, Salle 3052

**Bénédicte Legastelois** (LIP6) *Extension pondérée des logiques modales dans le cadre des croyances graduelles*

Dans le cadre général des logiques modales, je propose d'abord une sémantique proportionnelle pour des opérateurs modaux pondérés, basée sur des modèles de Kripke classiques. J'étudie ensuite la définition d'axiomes modaux pondérés étendant les axiomes classiques et propose une typologie les répartissant en quatre catégories, selon l'enrichissement du cas classique qu'ils produisent et leur correspondance avec la contrainte associée sur la relation d'accessibilité.

D'autre part, je m'intéresse à une formalisation des croyances graduelles, basée sur la conception représentationaliste des croyances et reposant sur un modèle ensembliste flou. J'en étudie plusieurs aspects, comme les propriétés arithmétiques et l'application de la négation.

Automata

Friday March 23, 2018, 2:30PM, Salle 3052

**Javier Esparza** (Technical University of Munich) *One Theorem to Rule Them All: A Unified Translation of LTL into omega-Automata*

Joint work with Jan Kretinsky and Salomon Sickert.

Automata

Friday February 16, 2018, 2:30PM, Salle 3052

**Prakash Panangaden** (McGill University) *A canonical form for weighted automata and applications to approximate minimization*

This is joint work with Borja Balle and Doina Precup and was presented at LICS 2015 in Kyoto.

Automata

Friday February 9, 2018, 2:30PM, Salle 3052

**Sylvain Schmitz** (LSV) *Algorithmic Complexity of Well-Quasi-Orders*

The talk gives an overview of the complexity questions arising from the use of well-quasi-orders, including the definition of complexity classes suitable for problems with non-elementary complexity and proof techniques for upper bounds. I will mostly focus on the ideas behind the first known complexity upper bound for reachability in vector addition systems and Petri nets.

Automata

Friday February 2, 2018, 2:30PM, Salle 3052

**Szymon Toruńczyk** (MIMUW) *Sparsity and Stability*

Automata

Friday January 19, 2018, 2:30PM, Salle 3052

**Verónica Becher** (Universidad de Buenos Aires and CONICET) *Randomness and uniform distribution modulo one*

This is joint work with Serge Grigorieff and Theodore Slaman.

#### Year 2017

Automata

Friday December 8, 2017, 2:30PM, Salle 3058

**Camille Bourgaux** (Télécom ParisTech) *Computing and explaining ontology-mediated query answers over inconsistent data*

Automata

Friday December 1, 2017, 2:30PM, Salle 3058

**Patricia Bouyer** (LSV, CNRS et ENS Cachan) *Nash equilibria in games on graphs with public signal monitoring*

Automata

Friday November 24, 2017, 2:30PM, Salle 3052

**Paul Brunet** (University College London) *Pomset languages and concurrent Kleene algebras*

In the first part of the talk, I will present an automaton model designed to describe such languages of pomset, which satisfies a Kleene-like theorem. The main difference with previous constructions is that from expressions to automata, we use Brzozowski derivatives.

In a second part, I will use Petri nets to reduce the problem of containment of languages of pomsets to the equivalence of finite state automata. In doing so, we prove decidabilty as well as provide tight complexity bounds.

I will finish the presentation by briefly presenting a recent proof of completness, showing that two series-rational expressions are equivalent according to the laws of CKA exactly when their pomset semantics are equal.

Joint work with Damien Pous, Georg Struth, Tobias Kappé, Bas Luttik, Alexandra Silva, and Fabio Zanasi

Automata

Friday November 17, 2017, 2:30PM, Salle 3058

**Michał Skrzypczak** (University of Warsaw) *Deciding complexity of languages via games*

The aim of my talk is to survey a number of examples in which it is not possible to provide algebraic representation of the considered languages; but instead characterisations can be obtained by a well-designed game of infinite duration. Using these examples, I will try to argue that game-based approach is the natural replacement for algebraic framework in the cases where algebraic representations are not available.

Automata

Friday November 10, 2017, 2:30PM, Salle 3058

**Laure Daviaud** (University of Warwick) *Max-plus automata and tropical identities*

Automata

Friday October 27, 2017, 2:30PM, Salle 3058

**Mikhail V. Volkov** (Ural Federal University, Russie) *Completely reachable automata: an interplay between semigroups, automata, and trees*

Automata

Friday October 20, 2017, 2:30PM, Salle 3058

**Sylvain Perifel** (IRIF) *Lempel-Ziv: a “one-bit catastrophe” but not a tragedy*

Automata

Friday October 6, 2017, 2:30PM, Salle 3058

**Nahtanaël Fijalkow** (University College London) *Comparing the speed of semi-Markov decision processes*

Automata

Thursday July 13, 2017, 2:30PM, Amphi Turing

**Thibault Godin** (IRIF) *Mealy machines, automaton (semi)groups, decision problems, and random generation (PhD defence)*

Manuscrit disponible ici : https://www.irif.fr/_media/users/godin/these30-06-17.pdf

Automata

Monday July 10, 2017, 2:30PM, Amphi Turing

**Matthieu Picantin** (IRIF) *Automates, (semi)groupes et dualités (soutenance d'habilitation)*

Manuscrit disponible ici : https://mealym.sciencesconf.org/data/program/HdR.pdf

Automata

Friday July 7, 2017, 2PM, 0010

**Bruno Karelović** (IRIF) *Analyse Quantitative des Systèmes Stochastiques - Jeux de Priorité et Population de Chaînes de Markov (soutenance de thèse)*

Automata

Friday June 16, 2017, 2:30PM, Salle 1006

**Thomas Garrity** *Classifying real numbers using continued fractions and thermodynamics.*

Automata

Friday June 9, 2017, 2:30PM, Salle 1006

**Pierre Ohlmann** (ENS de Lyon) *Invariant Synthesis for Linear Dynamical Systems*

We will investigate this problem with a different point of view: is it possible to synthesise suitable invariants, that is, subsets of $Q^d$ that contain $x$ but not $y$. Such invariants provide natural certificates for negative instances of the Orbit Problem. We will show that semialgebraic invariants exist in all reasonable cases. A more recent (yet unpublished) result is that existence of semilinear invariants is decidable.

This is a joint work with Nathanaël Fijalkow, Joël Ouaknine, Amaury Pouly and James Worrell, published in STACS 2017.

Automata

Friday June 2, 2017, 2:30PM, Salle 1006

**Michaël Cadilhac** (U. Tübingen) *Continuity & Transductions, a theory of composability*

In a second step, we focus on transducers, i.e., automata with letter output. We study the problem of deciding whether a given transducer realizes a V-continuous function, for some classical classes V (e.g., aperiodic languages, group languages, piecewise-testable, …).

If time allows, we will also see when there exists a correlation between the transducer structure (i.e., its transition monoid), and its computing a continuous function.

Joint work with Olivier Carton, Andreas Krebs, Michael Ludwig, Charles Paperman.

Automata

Friday May 19, 2017, 2:30PM, Salle 1006

**Anaël Grandjean** (LIRMM) *Small complexity classes for cellular automata, dealing with diamond and round neighborhood*

Automata

Friday May 12, 2017, 2:30PM, Salle 1006

**Paul-Elliot Anglès D'auriac** (LACL) *Higher computability and Randomness*

In this talk, we will see two ways to extend usual computability: by defining a more powerful model, or in a more set theoretic fashion. The first method is used to define Infinite Time Turing Machine, a model where Turing Machines are allowed to compute throught infinite time (that is, throught the ordinals instead of the integers). It has a lot of links with admissibility theory. The second method is used to define alpha-recursion, where alpha is any admissible ordinal. It is an abstract and very general definition of computation. Even if it has a very set-theoretic basis, it reflects the idea of computation and contains the notions of Turing Machine and Infinite Time Turing Machines computabilities. It also includes Higher Computability.

By investigating which properties on the extensions are needed to lift theorems to the new setting, we are able to isolate the important properties of the classical case. We also apply these generalized recursion theories to define randomness, in the same way that we did in the classical case: a string is said to be random if it has no exceptionnal properties, in a computable sense. Our new definition of computation then gives use new definition of randomness.

(No prior knowledge on set theory is assumed.)

Automata

Friday May 5, 2017, 2:30PM, Salle 1006

**Sebastián Barbieri** (ENS Lyon) *Symbolic dynamics and simulation theorems*

Automata

Friday April 21, 2017, 2:30PM, Salle 1006

**Wolfgang Steiner** (IRIF) *Recognizability for sequences of morphisms*

This is joint work with Valérie Berthé, Jörg Thuswaldner and Reem Yassawi.

Automata

Friday April 7, 2017, 2:30PM, Salle 1006

**Alan J. Cain** (U. Nova Lisbon) *Automatic presentations for algebraic and relational structures*

In this talk, I will introduce and survey automatic presentations, with particular attention to connections with decidability and logic. I will then discuss work with Nik Ruskuc (Univ. of St Andrews, UK) and Richard Thomas (Univ. of Leicester, UK) on algebraic and combinatorial structures that admit automatic presentations or unary automatic presentations. The main focus will be on results that characterize the structures of some type (for example, groups, trees, or partially ordered sets) that admit automatic presentations.

Automata

Friday March 31, 2017, 2:30PM, Salle 1006

**Cyril Nicaud** (LIGM) *Synchronisation d'automates aléatoires*

Automata

Friday March 24, 2017, 2:30PM, Salle 1006

**Martin Delacourt** (U. Orléans) *Des automates cellulaires unidirectionnels permutifs et du problème de la finitude pour les groupes d'automates.*

Automata

Friday March 17, 2017, 2:30PM, Salle 1006

**Fabian Reiter** (IRIF) *Asynchronous Distributed Automata: A Characterization of the Modal Mu-Fragment*

Automata

Friday March 10, 2017, 2:30PM, Salle 1006

**Victor Marsault** (University of Liège) *An efficient algorithm to decide the periodicity of $b$-recognisable sets using MSDF convention*

We are interested in deciding whether a $b$-recognisable set of integers (given as a finite automaton) is eventually periodic. Honkala showed in 1986 that this problem is decidable and recent developments give efficient decision algorithms. However, they only work when the integers are written with the least significant digit first.

In this work, we consider here the natural order of digits (Most Significant Digit First) and give a quasi-linear algorithm to solve the problem in this case.

Automata

Friday March 3, 2017, 2:30PM, Salle 3052

**Guillaume Lagarde** (IRIF) *Non-commutative lower bounds*

We still don't know an explicit polynomial that requires non-commutative circuits of size at least superpolynomial.
However, the context of non commutativity seems to be convenient to get such lower bound because the rigidity of the non-commutativity implies a lot of constraints about the ways to compute.
It is in this context that Nisan, in 1991, provides an exponential lower bound against the non commutative Algebraic Branching Programs computing the permanent, the very first one in arithmetic complexity. We show that this result can be naturally seen as a particular case of a theorem about circuits with *unique parse tree*, and show some extensions to get closer to lower bounds for general NC circuits.

Two joint works: with Guillaume Malod and Sylvain Perifel; with Nutan Limaye and Srikanth Srinivasan.

Automata

Friday February 24, 2017, 2:30PM, Salle 3052

**Daniela Petrisan** (IRIF) *Quantifiers on languages and topological recognisers*

A fundamental tool in studying the connection between algebraic recognisers, say classes of monoids, and fragments of logics on words is the availability of constructions on monoids which mirror the action of quantifiers, such as block products or other kinds of semidirect products. In the second part of the talk I will discuss generalisations of these techniques beyond the case of regular languages and present a general recipe for obtaining constructions on the topological recognisers introduced above that correspond to operations on languages possibly specified by transducers.

This talk is based on joint work with Mai Gehrke and Luca Reggio.

Automata

Friday February 17, 2017, 2:30PM, Salle 3052

**Svetlana Puzynina** (IRIF) *Additive combinatorics generated by uniformly recurrent words*

Automata

Friday January 27, 2017, 2:30PM, Salle 3052

**Nadime Francis** (University of Edinburgh) *Schema Mappings for Data Graphs*

As the model, we use data graphs: a theoretical abstraction of property graphs employed by graph database implementations. We start by showing a very strong negative result: using the simplest form of nontrivial navigation in mappings makes answering even simple queries that mix navigation and data undecidable. This result suggests that for the purposes of integration and exchange, schema mappings ought to exclude recursively defined navigation over target data. For such mappings and analogs of regular path queries that take data into account, query answering becomes decidable, although intractable. To restore tractability without imposing further restrictions on queries, we propose a new approach based on the use of null values that resemble usual nulls of relational DBMSs, as opposed to marked nulls one typically uses in integration and exchange tasks. If one moves away from path queries and considers more complex patterns, query answering becomes undecidable again, even for the simplest possible mappings.

Automata

Friday January 20, 2017, 2:30PM, Salle 3052

**Nathanaël Fijalkow** (Alan Turing Institute) *Logical characterization of Probabilistic Simulation and Bisimulation.*

In particular, I will look at logical characterizations for this notion: the goal is to describe a logic such that two systems are bisimilar if and only if they satisfy the same formulas. This question goes all the way back to Hennessey and Millner for non probabilistic transition systems.

I will develop topological tools and give very general logical characterization results for probabilistic simulation and bisimulation.

Automata

Friday January 13, 2017, 2:30PM, Salle 1006

**Reem Yassawi** (IRIF) *Extended symmetries of some higher dimensional shift spaces.*

*symmetry*group of $(X,T)$ is the group of all shift-commuting homeomorphisms $X$. In the larger

*reversing*symmetry group of $(X,T)$, we also consider homeomorphisms $\Phi$ of $X$ where $\Phi \circ T= T^{-1}\circ \Phi$, also called

*lip conjugacies*. We define a generalisation of the reversing symmetry group for higher dimensional shifts, and we find this

*extended*symmetry group for two prototypical higher dimensional shifts, namely the chair substitution shift and the Ledrappier shift. Joint work with M. Baake and J.A.G Roberts.

–––––

**French version:**

*Les automorphismes généralisés des sous shifts.*

Soit $(X,\mathbb Z^d)$ un soushift inversible. Nous définissons le groupe des

*automorphismes généralisés*: c'est le normalisateur du groupe engendré par le shift dans le groupe d'homéomorphismes de $X$. Nous trouvons les automorphismes généralisés de deux shifts prototyiques: le pavage de la chaise et le soushift Ledrappier. En collaboration avec M. Baake et J.A.G Roberts.

Automata

Friday January 6, 2017, 2:30PM, Salle 1006

**Alexandre Vigny** (IMJ-PRG) *Query enumeration and Nowhere-dense graphs*

In this talk we will discuss query enumeration, that is outputting the solutions one by one. Two parameters enter in play, the delay and the preprocessing time. The delay is the maximal time between two consecutive output and the preprocessing time is the time needed to produce the first solution. We will investigate cases where the delay is constant (does not depend on the size of the database) and the preprocessing is linear (in the size of the database) i.e. constant delay enumeration after linear preprocessing. This is not always possible as this implies a linear model-checking. We will therefore add restriction to the classes of databases and/or queries such as bounded degree databases, tree-like structures, conjunctive queries…

#### Year 2016

Automata

Friday December 9, 2016, 2:30PM, Salle 1006

**Benjamin Hellouin** (IRIF) *Computing the entropy of mixing tilings*

In 1D tilings (subshifts) of finite type, we have known how to compute the entropy for 30 years, and the method gives an algebraic characterisation of possible values. In higher dimension, a surprise came in 2007: not only is the entropy not computable in general, but any upper-semi-computable real number appears as entropy - a weak computational condition. Since then new works have shown that entropy becomes computable again with aditionnal mixing hypotheses. We do not know yet where the border between computable and uncomputable lies.

In this talk, I will explore the case of general subshifts (not of finite type) in any dimension, hoping to shed some light on the finite type case. I relate the computational difficulty of computing the entropy to the difficulty of deciding if a word belongs to the language. I exhibit a threshold in the mixing rate where the difficulty of the problem jumps suddenly, the very phenomenon that is expected in the finite type case.

This is a joint work with Silvère Gangloff and Cristobal Rojas.

Automata

Friday December 2, 2016, 2:30PM, Salle 1006

**Christian Choffrut** (IRIF) *Some equational theories of labeled posets*

We equip the collection of labeled posets (partially ordered sets), abbreviated l.p., with different operations: series product (concatenation of l.p), parallel product (disjoint union of posets), omega-power (concatenation of an omega sequence of the same poset) and omega-product (concatenation of an omega sequence of possibly different posets, which has therefore infinite arity). We select four subsets of these operations and show that in each case the equational theory is axiomatizable. We characterize the free algebras in the corresponding varieties, both algebraically as classes which are closed under the above operations as well as combinatorially as classes of partially ordered subsets. We also study the decidability issues when the question makes sense.

Nous munissons la collection des posets étiquetés (ensembles partiellement), en abrégé p.e., de différentes opérations: lproduit série (concaténation de p.e.), produit parallèle (union disjointe de p.e.), omega puissance (concaténation d'une omega suite du même p.e.) et omega produit (concaténation d'une omega suite de p.e., éventuellement différents, donc d'arité infinie. Nous distinguons quatre sous-ensembles parmi les opérations ci-dessus et nous montrons que dans chaque cas la théorie équationnelle est axiomatisable. Nous caractérisons les algèbres libres dans les variétiés correspondante aussi bien algébriquement en tant classes d'algèbres fermées pour les opérations ci-dessus et combinatoriquement en tant que classes de structures ordonnées. Nous étudions aussi les problèmes de décidabilité quand ils ont un sens.

Automata

Friday November 25, 2016, 2:30PM, Salle 1007

**Benedikt Bollig** (LSV, ENS de Cachan) *One-Counter Automata with Counter Observability*

Automata

Friday November 18, 2016, 2:30PM, Salle 1006

**Nathan Lhote** (LaBRI & ULB) *Towards an algebraic theory of rational word functions*

Automata

Friday November 4, 2016, 9:20AM, Salle 3052

**Lia Infinis** *Workshop*

- (09h20 - 09h30) Opening
- (09h30 - 10h00) Serge Grigorieff : “Algorithmic randomness and uniform distribution modulo one”
- (10h00 - 10h30) Stéphane Demri : “Reasoning about data repetitions with counter systems”
- (10h30 - 11h00) Coffee Break
- (11h00 - 11h30) Michel Habib : “A nice graph problem coming from biology: the study of read networks”
- (11h30 - 12h00) Delia Kesner : “Completeness of Call-by-Need (A fresh view)”
- (12h00 - 12h30) Pierre Vial : “Infinite Intersection Types as Sequences: a New Answer to Klop's Problem”
- (12h30 - 14h00) Lunch (Buffon Restaurant - 17 rue Hélène Brion - Paris 13ème)
- (14h00 - 14h30) Verónica Becher : “Finite-state independence and normal sequences”
- (14h30 - 15h00) Brigitte Vallée : “Towards the random generation of arithmetical objects”
- (15h00 - 15h30) Valérie Berthé : “Dynamical systems and their trajectories”
- (15h30 - 16h00) Coffee Break
- (16h00 - 16h30) Nicolás Alvarez : “Incompressible sequences on subshifts of finite type”
- (16h30 - 17h00) Eugene Asarin : “Entropy Games”
- (17h00 - 18h00) Discussion about the future of LIA INFINIS

Automata

Friday October 28, 2016, 2:30PM, Salle 1006

**Vincent Jugé** (LSV, ENS de Cachan) *Is the right relaxation normal form for braids automatic?*

We will study the right relaxation normal form, which belongs to this family of normal forms. We will show that it is regular, and that it is synchronously bi-automatic if and only if the braid group has 3 punctures or less.

Automata

Friday October 21, 2016, 2:30PM, Salle 1006

**Georg Zetzsche** (LSV, ENS de Cachan) *Subword Based Abstractions of Formal Languages*

While Parikh-style abstractions have been studied very intensely over the last decades, recent years have seen an increasing interest in abstractions based on the subword ordering. Examples include the set of (non necessarily contiguous) subwords of members of a language (the downward closure), or their superwords (the upward closure). Whereas it is well-known that these closures are regular for any language, it is often not obvious how to compute them. Another type of subword based abstractions are piecewise testable separators. Here, a separators acts as an abstraction of a pair of languages.

This talk will present approaches to computing closures, deciding separability by piecewise testable languages, and a (perhaps surprising) connection between these problems. If time permits, complexity issues will be discussed as well.

Automata

Friday October 14, 2016, 2:30PM, Salle 1006

**Léo Exibard** *Alternating Two-way Two-tape Automata*

Joint work with Olivier Carton and Olivier Serre.

Automata

Friday October 7, 2016, 2:30PM, Salle 1006

**Hubie Chen** *One Hierarchy Spawns Another: Graph Deconstructions and the Complexity Classification of Conjunctive Queries*

We here restrict the problem according to the set of permissible queries; the particular formulation we work with is the relational homomorphism problem over a class of structures A, wherein each instance must be a pair of structures such that the first structure is an element of A. We present a comprehensive complexity classification of these problems, which strongly links graph-theoretic properties of A to the complexity of the corresponding homomorphism problem. In particular, we define a binary relation on graph classes and completely describe the resulting hierarchy given by this relation. This binary relation is defined in terms of a notion which we call graph deconstruction and which is a variant of the well-known notion of tree decomposition. We then use this graph hierarchy to infer a complexity hierarchy of homomorphism problems which is comprehensive up to a computationally very weak notion of reduction, namely, a parameterized form of quantifier-free reductions. We obtain a significantly refined complexity classification of left-hand side restricted homomorphism problems, as well as a unifying, modular, and conceptually clean treatment of existing complexity classifications, such as the classifications by Grohe-Schwentick-Segoufin (STOC 2001) and Grohe (FOCS 2003, JACM 2007).

After presenting this new advance, we will compare this line of research with another that aims to classify the complexity of the homomorphism problem where the second (target) structure is fixed, and that is currently being studied using universal-algebraic methods. We will also make some remarks on two intriguing variants, injective homomorphism (also called embedding) and surjective homomorphism.

This talk is mostly based on joint work with Moritz Müller that appeared in CSL-LICS ’14. In theory, the talk will be presented in a self-contained fashion, and will not assume prior knowledge of any of the studied notions.

Automata

Friday September 30, 2016, 2:30PM, 1006

**Équipe automate** *Journée de rentrée*

9h45 Svetlana Puzynina 10h15 Sebastian Schoener 10h30 Célia Borlido 11h Thibault Godin 11h45 Benjamin Hellouin 12h15 Thomas Garrity

14h Olivier Carton 14h30 Sylvain Lombardy (LaBRI)– Démonstration du logiciel Vaucuson-R 15h30 Pablo Rotondo

Automata

Friday July 8, 2016, 2:30PM, Salle 1003

**Sylvain Hallé** (Université du Québec à Chicoutimi) *Solving Equations on Words with Morphisms and Antimorphisms*

Automata

Friday June 17, 2016, 2:30PM, Salle 1003

**Arthur Milchior** (IRIF) *Deterministic Automaton and FO[<,mod] integer set*

We state that it is decidable in time O(nlog(n)) whether a set of vectors accepted by a given finite deterministic automaton can be defined in the less expressive logic. The case of dimension 1 was already proven by Marsault and Sakarovitch. If the first algorithms gives a positive answer, the second one computes in time O(n^{3}log(n)) an existential formula in this logic that defines the same set. This improves the 2EXP time algorithm that can be easily obtained by combining the results of Leroux and Choffrut.

In this talk, it is intended to: -Introduce automata reading vectors of integers, -Present the logic FO[<,0,mod] over integers -Introduce classical tools relating automata to numbers. -Give an idea of how they can be applied to the above-mentionned problem.

Automata

Friday June 10, 2016, 2:30PM, Salle 1003

**Bruno Karelovic** (IRIF) *Perfect-information Stochastic Priority Games*

Automata

Friday June 3, 2016, 2:30PM, Salle 1003

**Howard Straubing** (Boston College) *Two Variable Logic with a Between Predicate*

We present several logics, both first-order and temporal, that have the same expressive power, and find matching lower and upper bounds for the complexity of satisfiability for each of these formulations. We also give an effective algebraic characterization of the properties expressible in this logic. This enables us to prove, among many other things, that our new logic has strictly less expressive power than full first-order logic FO[<].

This is joint work with Andreas Krebs, Kamal Lodaya, and Paritosh Pandya, and will be presented at LICS2016.

Automata

Monday May 30, 2016, 2PM, Salle des thèse (halle aux farines)

**Bruno Guillon** (IRIF - Universitá degli Studi di Milano) *Soutenance de Thèse : Two-wayness: Automata and Transducers*

The 2FA are computably equivalent to FA, even in their nondeterministic (2NFA) variant. However, in the Descriptional Complexity area, some questions remain. Raised by Sakoda and Sipser in 1978, the question of the cost of the simulation of 2NFA by 2DFA is still open. In this manuscript I give an answer in a restricted case in which the nondeterministic choices of the 2NFA may occur at the border of the input only (2ONFA). I show that every 2ONFA can be simulated by a 2DFA of subexponential (but superpolynomial) size. Under the assumptions L=NL, this cost is reduced to the polynomial level. Moreover, I prove that the complementation, and the simulation by a halting 2ONFA is polynomial.

Classical transducers (1-way) are well-known and admit nice characterizations (rational relations, logic). But their 2-way variant (2T) is still unknown, especially the nondeterministic case. In this area, my manuscript gives a new contribution: a algebraic characterization of the relations accepted by 2NT when both the input and output alphabets are unary. It can be reformulated as follows: each unary 2NT is equivalent to a sweeping (and even rotating) 2T. I also show that the assumptions made on the size of the alphabets are required.

The study of word relations, as algebraic object, and their transitive closure is another subject considered in my phd. When the relation belongs to some low level class, we are able to set the complexity of its transitive closure. This quickly becomes uncomputable when higher classes are considered.

Automata

Friday May 27, 2016, 2:30PM, Salle 1003

**Laure Daviaud** (LIP – ENS Lyon) *A Generalised Twinning Property for Minimisation of Cost Register Automata*

Regarding unambiguous WA over a group G, they can equivalently be described by a CRA whose registers take their values in G, and are updated by operations of the form X:=Y.c, with c in G and X,Y registers.

In this talk, I will give a characterisation of unambiguous weighted automata which are equivalent to cost register automata using at most k registers, for a given k. To this end, I will generalise two notions originally introduced by Choffrut for finite-state transducers: a twinning property and a bounded variation property, here parametrised by an integer k and that characterise WA/functions computing by a CRA using at most k registers.

This is a joint work with Pierre-Alain Reynier and Jean-Marc Talbot.

Automata

Friday May 20, 2016, 2:30PM, Salle 1003

**Igor Potapov** (University of Liverpool) *Matrix Semigroups and Related Automata Problems*

- Membership (Decide whether a given matrix M belong to a semigroup S) and special cases such as: Identity (i.e if M is the identity matrix) and Mortality (i.e if M is the zero matrix) problems
- Vector reachability (Decide for a given vectors u and v whether exist a matrix M in S such that Mu=v)
- Scalar reachability (Decide for a given vectors u, v and a scalar L whether exist a matrix M in S such that uMv=L)
- Freeness (Decide whether every matrix product in S is unique, i.e. whether it is a code)

The undecidability proofs in matrix semigroups are mainly based on various techniques and methods for embedding universal computations into matrix products. The case of dimension two is the most intriguing since there is some evidence that if these problems are undecidable, then this cannot be proved using any previously known constructions. Due to a severe lack of methods and techniques the status of decision problems for 2×2 matrices (like membership, vector reachability, freeness) is remaining to be a long standing open problem. More recently, a new approach of translating numerical problems of 2×2 integer matrices into variety of combinatorial and computational problems on words and automata over group alphabet and studying their transformations as specific rewriting systems have led to a few results on decidability and complexity for some subclasses.

Automata

Friday May 13, 2016, 2:30PM, Salle 1003

**Dong Han Kim** (Dongguk University, Corée du Sud) *Sturmian colorings on regular trees*

This is joint work with Seonhee Lim.

Automata

Friday April 15, 2016, 2:30PM, Salle 1003

**Emmanuel Jeandel** (LORIA) *Un jeu apériodique de 11 tuiles*

Le premier jeu de tuiles apériodique trouvé par Berger avait 20426 tuiles, et le nombre de tuiles nécessaire a baissé progressivement jusqu'à ce que Culik obtienne en 1996 un jeu de 13 tuiles en utilisant une méthode due à Kari.

Avec Michael Rao, nous avons trouvé avec l'aide de plusieurs ordinateurs un jeu apériodique de 11 tuiles. Ce nombre est optimal : il n'existe pas de jeu apériodique de moins de 11 tuiles. Une des principales difficultés de cette recherche guidée par ordinateur est que nous cherchons une aiguille dans une botte de foin indécidable : il n'existe pas d'algorithme qui décide si un jeu de tuiles est apériodique.

Après une brève introduction au problème, je présenterai l'ensemble de 11 tuiles, ainsi que les techniques de théorie des automates et de systèmes de transitions qui ont permis de prouver (a) qu'il est apériodique, et (b) que c'est le plus petit.

Automata

Friday April 1, 2016, 2:30PM, Salle 1003

**Tim Smith** (LIGM Paris Est) *Determination and Prediction of Infinite Words by Automata*

Next, we consider prediction of infinite words by automata. In the classic problem of sequence prediction, a predictor receives a sequence of values from an emitter and tries to guess the next value before it appears. The predictor masters the emitter if there is a point after which all of the predictor's guesses are correct. We study the case in which the predictor is an automaton and the emitted values are drawn from a finite set; i.e., the emitted sequence is an infinite word.

The automata we consider are finite automata, pushdown automata, stack automata (a generalization of pushdown automata), and multihead finite automata, and we relate them to purely periodic words, ultimately periodic words, and multilinear words.

Automata

Monday March 21, 2016, 10AM, LABRI

**Colloque En L'honneur De Marcel-Paul Schützenberger (21-25/03/2016)** *Programme*

Automata

Friday March 18, 2016, 2:30PM, Salle 1003

**Eugene Asarin** (IRIF) *Entropy games and matrix multiplication games*

Joint work with Julien Cervelle, Aldric Degorre, Cătălin Dima, Florian Horn, and Victor Kozyakin.

Automata

Friday March 11, 2016, 2:30PM, Salle 0010

**Anna-Carla Rousso** (IRIF) *To be announced.*

Automata

Friday March 4, 2016, 2:30PM, Salle 0010

**Thierry Bousch** (Paris Sud) *La Tour d'Hanoï, revue par Dudeney*

Automata

Friday January 22, 2016, 2:30PM, Salle 0010

**Laurent Bartholdi** (ENS) *To be announced.*

Automata

Friday January 15, 2016, 2:30PM, Salle 0010

**Viktoriya Ozornova** (Universität Bremen) *Factorability structures*

Automata

Friday January 8, 2016, 2:30PM, Salle 0010

**Antoine Amarilli** (Télécom ParisTech) *Provenance Circuits for Trees and Treelike Instances*