### Automates

** Date et lieu :** le vendredi à 14h30, salle 1006, Sophie Germain

** Responsables :** Wolfgang Steiner, Sylvain Perifel, Thibault Godin et Fabian Reiter

Vendredi 03 mars 2017 · 14h30 · 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.

Vendredi 10 mars 2017 · 14h30 · 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.

Vendredi 17 mars 2017 · 14h30 · Salle 1006

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

Vendredi 31 mars 2017 · 14h30 · Salle 1006

Cyril Nicaud · TBA

Vendredi 02 juin 2017 · 14h30 · Salle 1006

Michaël Cadilhac (U. Tübingen) · TBA

Vendredi 24 février 2017 · 14h30 · 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.

Vendredi 17 février 2017 · 14h30 · Salle 3052

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

Vendredi 27 janvier 2017 · 14h30 · 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.

Vendredi 20 janvier 2017 · 14h30 · 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.

Vendredi 13 janvier 2017 · 14h30 · 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.

Vendredi 06 janvier 2017 · 14h30 · 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…

Vendredi 09 décembre 2016 · 14h30 · 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.

Vendredi 02 décembre 2016 · 14h30 · 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.

Vendredi 25 novembre 2016 · 14h30 · Salle 1007

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

Vendredi 18 novembre 2016 · 14h30 · Salle 1006

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

Vendredi 04 novembre 2016 · 09h20 · 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

Vendredi 28 octobre 2016 · 14h30 · 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.

Vendredi 21 octobre 2016 · 14h30 · 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.

Vendredi 14 octobre 2016 · 14h30 · Salle 1006

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

Joint work with Olivier Carton and Olivier Serre.

Vendredi 07 octobre 2016 · 14h30 · 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.

Vendredi 30 septembre 2016 · 14h30 · 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

Vendredi 08 juillet 2016 · 14h30 · Salle 1003

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

Vendredi 17 juin 2016 · 14h30 · 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.

Vendredi 10 juin 2016 · 14h30 · Salle 1003

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

Vendredi 03 juin 2016 · 14h30 · 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.

Lundi 30 mai 2016 · 14h00 · 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.

Vendredi 27 mai 2016 · 14h30 · 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.

Vendredi 20 mai 2016 · 14h30 · 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.

Vendredi 13 mai 2016 · 14h30 · Salle 1003

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

This is joint work with Seonhee Lim.

Vendredi 15 avril 2016 · 14h30 · 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.

Vendredi 01 avril 2016 · 14h30 · 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.

Vendredi 18 mars 2016 · 14h30 · 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.

** Slides des exposés : **