Jeudi 9 décembre 2016, 14 heure 30, 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.
Jeudi 2 décembre 2016, 14 heure 30, 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.
Jeudi 25 novembre 2016, 14 heure 30, Salle 1007
Benedikt Bollig (LSV, ENS de Cachan) One-Counter Automata with Counter Observability
Jeudi 18 novembre 2016, 14 heure 30, Salle 1006
Nathan Lhote (LaBRI & ULB) Towards an algebraic theory of rational word functions
Jeudi 4 novembre 2016, 9 heure 20, Salle 3052
Lia Infinis Workshop
Jeudi 28 octobre 2016, 14 heure 30, 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.
Jeudi 21 octobre 2016, 14 heure 30, 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.
Jeudi 14 octobre 2016, 14 heure 30, Salle 1006
Léo Exibard Alternating Two-way Two-tape Automata
Joint work with Olivier Carton and Olivier Serre.
Jeudi 7 octobre 2016, 14 heure 30, 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.
Jeudi 30 septembre 2016, 14 heure 30, 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
Jeudi 8 juillet 2016, 14 heure 30, Salle 1003
Sylvain Hallé (Université du Québec à Chicoutimi) Solving Equations on Words with Morphisms and Antimorphisms
Jeudi 17 juin 2016, 14 heure 30, 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.
Jeudi 10 juin 2016, 14 heure 30, Salle 1003
Bruno Karelovic (IRIF) Perfect-information Stochastic Priority Games
Jeudi 3 juin 2016, 14 heure 30, 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.
Dimanche 30 mai 2016, 14 heure 0, 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.
Jeudi 27 mai 2016, 14 heure 30, 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.
Jeudi 20 mai 2016, 14 heure 30, Salle 1003
Igor Potapov (University of Liverpool) Matrix Semigroups and Related Automata Problems
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.
Jeudi 13 mai 2016, 14 heure 30, Salle 1003
Dong Han Kim (Dongguk University, Corée du Sud) Sturmian colorings on regular trees
This is joint work with Seonhee Lim.
Jeudi 15 avril 2016, 14 heure 30, 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.
Jeudi 1 avril 2016, 14 heure 30, 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.
Dimanche 21 mars 2016, 10 heure 0, LABRI
Colloque En L'honneur De Marcel-Paul Schützenberger (21-25/03/2016) Programme
Jeudi 18 mars 2016, 14 heure 30, 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.
Jeudi 11 mars 2016, 14 heure 30, Salle 0010
Anna-Carla Rousso (IRIF) Non encore annoncé
Jeudi 4 mars 2016, 14 heure 30, Salle 0010
Thierry Bousch (Paris Sud) La Tour d'Hanoï, revue par Dudeney
Jeudi 22 janvier 2016, 14 heure 30, Salle 0010
Laurent Bartholdi (ENS) Non encore annoncé
Jeudi 15 janvier 2016, 14 heure 30, Salle 0010
Viktoriya Ozornova (Universität Bremen) Factorability structures
Jeudi 8 janvier 2016, 14 heure 30, Salle 0010
Antoine Amarilli (Télécom ParisTech) Provenance Circuits for Trees and Treelike Instances