Day, hour and place

Friday at 2:30pm, room 3052

calendar (iCal format)


Contact(s)


Next talk


Automata
Friday June 14, 2019, 2:30PM, Salle 3052
Mahsa Shirmohammadi (CNRS) tbc


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

Probabilistic timed automata are classical timed automata extended with discrete probability distributions over edges. In this talk, clock-dependent probabilistic timed automata, a variant of probabilistic timed automata in which transition probabilities can depend on clock values, will be described. Clock-dependent probabilistic timed automata allow the modelling of a continuous relationship between time passage and the likelihood of system events. We show that the problem of deciding whether the maximum probability of reaching a certain location is above a threshold is undecidable for clock-dependent probabilistic timed automata. On the other hand, we show that the maximum and minimum probability of reaching a certain location in clock-dependent probabilistic timed automata can be approximated using a region-graph-based approach.

Automata
Friday May 3, 2019, 2:30PM, Salle 3052
Sam Van Gool (Utrecht University) Separation and covering for varieties determined by groups

The separation problem for a variety of regular languages V asks to decide whether two disjoint regular languages can be separated by a language in V. The covering problem is a generalization of the separation problem to an arbitrary finite list of regular languages.

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

La théorie des espaces de pavages (sous-shifts) a été profondément façonnée par le résultat historique de Berger : un jeu de tuiles fini peut ne paver le plan que de manière apériodique. Ces points apériodiques sont au coeur de nombreuses directions de recherche du domaine, en mathématiques comme en informatique. Dans cette exposé, nous répondons aux questions suivantes en 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

A generalized lexicographical order on infinite words is defined by choosing for each position a total order on the alphabet. This allows to define generalized Lyndon words. Every word in the free monoid can be factorized in a unique way as a non-increasing factorization of generalized Lyndon words. We give new characterizations of the first and the last factor in this factorization as well as new characterization of generalized Lyndon words. We also give more specific results on two special cases: the classical one and the one arising from the alternating lexicographical order. This is a joint work with Antonio Restivo and Christophe Reutenauer.

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

Pour une suite $\mathbb{a} = (a_n)_{n≥0}$ à valeurs dans un corps fini $\mathbb{F}_q$, le théorème de Christol établit une équivalence entre $q$-automaticité de $\mathbb{a}$ ($\mathbb{a}$ calculable par un automate) et l’algebricité de la série formelle $f(x) = \sum a_n x^n$. Dans ce travail nous étudierons le nombre d’états de l’automate en fonction des paramètres du polynôme annulateur minimal de $f(x)$.

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

In this talk, we introduce a condition number of stochastic mean payoff games. To do so, we interpret these games as feasibility problems over tropically convex cones. In this setting, the condition number is defined as the maximal radius of a ball in Hilbert's projective metric that is included in the (primal or dual) feasible set. We show that this conditioning controls the number of value iterations needed to decide whether a mean payoff game is winning. In particular, we obtain a pseudopolynomial bound for the complexity of value iteration provided that the number of random positions is fixed. We also discuss the implications of these results for convex optimization problems over nonarchimedean fields and present possible directions for future research.

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.

It is known that Christoffel words are balanced words on two letters alphabet, where these words are exactly the discretization of line segments of rational slope. Christoffel words are considered also in the topic of synchronization of k process by a word on a k letter alphabet with a balance property in each letter. Some applications for k = 2, we retrieve the usual Christoffel words. While for k > 2, the situation is more complicated and lead to the Fraenkel’s conjecture that is an open conjecture for more than 40 years. In this talk, we show some tools that get us close to this conjecture. Another application to this family of words, we define a second order of balance by using some particular matrices, and we prove a recursive relation in constructing them. An interesting property can be deduced from these matrices, allowing us to give a supplementary characteristic for the Fibonnaci sequence. One more application to Christoffel words is discussed in this talk, in fact, by using all the properties of these words, we can apply them on the reconstruction of digital convex polyominoes. Since the boundary word of the digital convex polyominoe is made of Christoffel words with decreasing slopes. Hence we introduce a split operator that respects the decreasing order of the slopes and therefore the convexity is always conserved which is the first step toward this reconstruction.

Automata
Friday February 15, 2019, 2:30PM, Salle 3052
Alexandre Vigny (Université Paris Diderot) Query enumeration and nowhere dense classes of graphs

Given a query q and a relational structure D the enumeration of q over D consists in computing, one element at a time, the set q(D) of all solutions to q on D. The delay is the maximal time between two consecutive output and the preprocessing time is the time needed to produce the first solution. Ideally, we would like to have constant delay enumeration after linear preprocessing. Since this it is not always possible to achieve, we need to add restrictions to the classes of structures and/or queries we consider.

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

In this talk, I will introduce a notion of higher-order parity automaton which extends the traditional notion of parity tree automaton on infinitary ranked trees to the infinitary simply-typed lambda-calculus. Our main result is that the acceptance of an infinitary lambda-term by a higher-order parity automaton A is decidable, whenever the infinitary lambda-term is generated by a finite and simply-typed lambda-Y-term. The decidability theorem is established by combining ideas coming from automata theory, denotational semantics and infinitary rewriting theory.

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

In one dimension, an infinite word is said to be recurrent if every prefix occurs at least twice. A straightforward extension of this definition in higher dimensions turns out to be rather unsatisfying. In this talk, we present several notions of recurrence in the multidimensional case. In particular, we are interested in words having the property to be strongly uniformly recurrent: for each direction q, every prefix occurs in that direction (i.e. in positions iq) with bounded gaps. We will provide several constructions of such words and focus on the strongly uniform recurrence in the case of square morphisms.

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

The computational model of programs over monoids, introduced by Barrington and Thérien in the late 1980s, gives a way to generalise the notion of (classical) recognition through morphisms into monoids in such a way that almost all open questions about the internal structure of the complexity class NC^1 can be reformulated as understanding what languages (and, in fact, even regular languages) can be program-recognised by monoids taken from some given variety of finite monoids. Unfortunately, for the moment, this finite semigroup theoretical approach did not help to prove any new result about the internal structure of NC^1 and, even worse, any attempt to reprove well-known results about this internal structure (like the fact that the language of words over the binary alphabet containing a number of 1s not divisible by some fixed integer greater than 1 is not in AC^0) using techniques stemming from algebraic automata theory failed. In this talk, I shall present the model of programs over monoids, explain how it relates to “small” circuit complexity classes and present some of the contributions I made during my Ph.D. thesis to the understanding of the computational power of programs over monoids, focusing on the well-known varieties of finite monoids DA and J (giving rise to “small” circuit complexity classes well within AC^0). I shall conclude with a word about ongoing work and future research directions.

Automata
Friday January 18, 2019, 2:30PM, Salle 3052
Adrien Boiret Learning Top-Down Tree Transducers using Myhill Nerode or Lookahead

We consider the problem of passive symbolic learning in the case of deterministic top-down tree transducers (DTOP). The passive learning problem deals with identifying a specific transducer in normal form from a finite set of behaviour examples. This problem is solved in word languages using the RPNI algorithm, that relies heavily on the Myhill-Nerode characterization of a minimal normal form on DFA. Its extensions to word transformations and tree languages follow the same pattern: first, a Myhill-Nerode theorem is identified, then the normal form it induces can be learnt from examples. To adapt this result in tree transducers, the Myhill-Nerode theorem requires that DTOP are considered with an inspection, i.e. an automaton that recognized the domain of the transformation. In its original form, the normalization (minimal earliest compatible normal form) and learning of DTOP is limited to deterministic top-down tree automata as inspections. In this talk, we show the challenges that an extension to regular inspections presents, and present two concurrent ways to deal with them:
  1. first, by an extension of the Myhill-Nerode theorem on DTOP to the regular case, by defining a minimal *leftmost* earliest compatible normal form.
  2. 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

M. B. Levin constructed a real number x such that the first N terms of the sequence b^n x mod 1 for n >= 1 have discrepancy $O((log N)^2/N)$. This is the lowest discrepancy known for this kind of sequences. In this talk, we present Levin's construction in terms of nested perfect necklaces, which are a variant of the classical de Bruijn sequences. For base 2 and the order being a power of 2, we give the exact number of nested perfect necklaces and an explicit method based on matrices to construct each of them.


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

Petri nets, also known as vector addition systems, are a long established and widely used model of concurrent processes. The complexity of their reachability problem is one of the most prominent open questions in the theory of verification. That the reachability problem is decidable was established by Mayr in his seminal STOC 1981 work, and the currently best upper bound is non-primitive recursive cubic-Ackermannian of Leroux and Schmitz from LICS 2015. We show that the reachability problem is not elementary. Until this work, the best lower bound has been exponential space, due to Lipton in 1976.

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

Rabin's Tree Theorem proceeds by effective translations of MSO-formulae to tree automata. We show that the operations on automata used in these translations can be organized in a deduction system based on intuitionistic linear logic (ILL). We propose a computational interpretation of this deduction system along the lines of the Curry-Howard proofs-as-programs correspondence. This interpretation, relying on the usual technology of game semantics, maps proofs to strategies in categories of two-player games generalizing the usual acceptance games of tree automata.

Automata
Friday December 7, 2018, 2:30PM, Salle 3058
Antoine Amarilli (Télécom ParisTech) Topological Sorting under Regular Constraints

We present our work on what we call the constrained topological sorting problem (CTS): given a regular language K and a directed acyclic graph G with labeled vertices, determine if G has a topological sort that forms a word in K. This natural problem applies to several settings, e.g., scheduling with costs or verifying concurrent programs. We consider the problem CTS[K] where the target language K is fixed, and study its complexity depending on K.

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

We present a survey of results obtained on symbolic dynamical systems called dendric shifts. We state and sketch the proofs (sometimes new ones) of the main results obtained on these shifts. This includes the Return Theorem and the Finite Index Basis Theorem which both put in evidence the central role played by free groups in these systems. We also present a series of applications of these results, including some on profinite semigroups and some on dimension groups.

Automata
Friday November 23, 2018, 2:30PM, Salle 3052
Sébastien Labbé (IRIF) Structure substitutive des pavages apériodiques de Jeandel-Rao

En 2015, Jeandel et Rao ont démontré par des calculs exhaustifs faits par ordinateur que tout ensemble de tuiles de Wang de cardinalité ≤ 10 soit admettent un pavage périodique du plan Z² soit n'admettent aucun pavage du plan. De plus, ils ont trouvé un ensemble de 11 tuiles de Wang qui pavent le plan mais jamais de façon périodique. Dans cet exposé, nous présenterons une définition alternative des pavages apériodiques de Jeandel-Rao comme le codage d'une Z²-action sur le tore et nous décrivons la structure substitutive de ces pavages.

Automata
Friday November 16, 2018, 2:30PM, Salle 358
Manon Stipulanti (Université de Liège) A way to extend the Pascal triangle to words

The Pascal triangle and the corresponding Sierpinski gasket are well-studied objects. They exhibit self-similarity features and have connections with dynamical systems, cellular automata, number theory and automatic sequences in combinatorics on words. In this talk, I will first recall the well-known link between those two objects. Then I will exploit it to define Pascal-like triangles associated with different numeration systems, and their analogues of the Sierpinski gasket. This a work in collaboration with Julien Leroy and Michel Rigo (University of Liège, Belgium).

Automata
Friday November 9, 2018, 2:30PM, Salle 358
Fabian Reiter (LSV) Counter Machines and Distributed Automata: A Story about Exchanging Space and Time

I will present the equivalence of two classes of counter machines and one class of distributed automata. The considered counter machines operate on finite words, which they read from left to right while incrementing or decrementing a fixed number of counters. The two classes differ in the extra features they offer: one allows to copy counter values, whereas the other allows to compute copyless sums of counters. The considered distributed automata, on the other hand, operate on directed path graphs that represent words. All nodes of a path synchronously execute the same finite-state machine, whose state diagram must be acyclic except for self-loops, and each node receives as input the state of its direct predecessor. These devices form a subclass of linear-time one-way cellular automata.

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

We study approximation algorithms for two closely related problems: the problems of finding a short synchronizing and a short mortal word for a given prefix code. Roughly speaking, a synchronizing word is a word guaranteeing a unique interpretation, and a mortal word is a word guaranteeing no interpretation for any sequence of codewords. We concentrate on the case of finite prefix codes and consider both the cases where the code is defined by listing all its codewords and where the code is defined by an automaton recognizing the star of the code. This is a joint work with Marek Szykuła (University of Wroclaw).

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

Given any numeration system, we call 'carry propagation' at a number N the number of digits that are changed when going from the representation of N to the one of N+1 , and 'amortized carry propagation' the limit of the mean of the carry propagations at the first N integers, when N tends to infinity, and if it exists.

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

I will talk about parity games. There are at least three different recent algorithms which solve them in quasipolynomial time. In this talk, I will show that the three algorithms can be seen as solutions of one automata-theoretic problem. Using this framework, I will show tight upper and lower bounds, witnessing a quasipolynomial barrier.

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

We develop an algebraic lower bound technique in the context of non-commutative arithmetic circuits. To this end, we introduce polynomials for which the multiplication is also non-associative, and focus on their circuit complexity. We show a connection with multiplicity tree automata, leading to a general algebraic characterization. We use it to derive meta-theorems for the non-commutative case, and highlight numerous consequences in terms of lower bounds.

Automata
Wednesday June 13, 2018, 3PM, Salle 3052
Joël Ouaknine (Max Planck Institute) Program Invariants

Automated invariant generation is a fundamental challenge in program analysis and verification, going back many decades, and remains a topic of active research. In this talk I'll present a select overview and survey of work on this problem, and discuss unexpected connections to other fields including algebraic geometry, group theory, and quantum computing. (No previous knowledge of these fields will be assumed.)

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

The study on how (semi)groups grow has been highlighted since Milnor's question on the existence of groups of intermediate growth (faster than any polynomial and slower than any exponential) in 1968. A very first example of such a group was given by Grigorchuk in 1983 in terms of an automaton group, and, until Nekrashevych's very recent work, all the known examples of intermediate growth groups were automaton groups or based on automaton groups.

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

In my presentation, I am going to present joint work with Joel Allred on the complementation of Büchi automata. When constructing the complement automaton, a worst-case state-space growth of O((0.76n)^n) cannot be avoided. Experiments suggest that complementation algorithms perform better on average when they are structurally simple. We develop a simple algorithm for complementing Büchi automata, operating directly on subsets of states, structured into state-set tuples, and producing a deterministic automaton. Then a complementation procedure is applied that resembles the straightforward complementation algorithm for deterministic Büchi automata, the latter algorithm actually being a special case of our construction. Finally, we prove our construction to be optimal, i.e. having an upper bound in O((0.76n)^n), and furthermore calculate the 0.76 factor in a novel exact way.

Automata
Friday May 18, 2018, 2:30PM, Salle 3052
Irène Guessarian (IRIF) Congruence preservation, treillis et reconnaissabilite

Looking at some monoids and (semi)rings (natural numbers, integers and p- adic integers), and more generally, residually finite algebras (in a strong sense), we prove the equivalence of two ways for a function on such an algebra to behave like the operations of the algebra. The first way is to preserve congruences or stable preorders. The second way is to demand that preimages of recognizable sets belong to the lattice or the Boolean algebra generated by the preimages of recognizable sets by “derived unary operations” of the algebra (such as trans- lations, quotients,. . . ).

Automata
Friday April 20, 2018, 2:30PM, Salle 3052
Davide Mottin (Hasso Platner Institute) Graph Exploration: Graph Search made Easy

The increasing interest in social networks, knowledge graphs, protein-interaction, and many other types of networks has raised the question how users can explore such large and complex graph structures easily. In this regard, graph exploration has emerged as a complementary toolbox for graph management, graph mining, or graph visualization in which the user is a first class citizen. Graph exploration combines and expands database, data mining, and machine learning approaches with the user eye on one side and the system perspective on the other.

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

The issue of determinism versus non-determinism is central in computer science. In order to better understand this gap, the intermediary model of Good-for-Games (GFG) automata is currently being explored in its various aspects. A GFG automaton is a non-deterministic automaton on finite or infinite words, where accepting runs can be built on-the-fly on valid input words. I will recall recent advances on this model, and describe a newly introduced generalisation: width. The width of an automaton can be viewed as a measure of its amount of nondeterminism. Width generalises the notion of GFG automata, which correspond to NFAs of width 1. I will describe how GFG or deterministic automata can be built from non-deterministic automata, with width being a crucial parameter in the construction. I will finally mention results and open problems related to the computational complexity of computing GFGness or width of automata.

Automata
Friday April 6, 2018, 2:30PM, Salle 3052
Victor Marsault (LFCS, University of Edinburgh) Formal semantics of the query-language Cypher

Cypher is a query-language for property-graphs. It was originally designed and implemented as part of the Neo4j graph database, and it is currently used by several commercial database products and researchers. The semantics of Cypher queries is currently described using natural language and, as a result, it is often not well defined. This work is part of a project to define a full denotational semantics of Cypher queries. The talk will first present the main features of Cypher through examples, including the core mecanism: graph pattern-matching, and then will describe the principle of the formal semantics.

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

La formalisation et le raisonnement sur des notions non-vérifonctionnelles, telles que la croyance, le savoir ou la certitude, sont des enjeux actuels de l'intelligence artificielle. Ces notions peuvent mener à représenter et évaluer des informations subjectives et sont, en particulier, formalisées en logique modale. Motivés par la modélisation du raisonnement sur les croyances graduelles, dont l'expressivité est enrichie par rapport aux croyances classiques, mes travaux portent sur les extensions pondérées des logiques modales.

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

We present a unified translation of LTL formulas into deterministic Rabin automata, limit-deterministic Büchi automata, and nondeterministic Büchi automata. The translations yield automata of asymptotically optimal size (double or single exponential, respectively). All three translations are derived from one single Master Theorem of purely logical nature. The Master Theorem decomposes the language of a formula into a positive boolean combination of languages that can be translated into omega-automata by elementary means. In particular, the breakpoint, Safra, and ranking constructions used in other translations are not needed.

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

We study the problem of constructing approximations to a weighted automaton. Weighted finite automata (WFA) are closely related to the theory of rational series. A rational series is a function from strings to real numbers that can be computed by a WFA. This includes probability distributions generated by hidden Markov models and probabilistic automata. The relationship between rational series and WFA is analogous to the relationship between regular languages and ordinary automata. Associated with such rational series are infinite matrices called Hankel matrices which play a fundamental role in the theory of minimal WFA. In this talk I describe: (1) an effective procedure for computing the singular value decomposition (SVD) of such infinite Hankel matrices based on their finite representation in terms of WFA; (2) a new canonical form for WFA based on this SVD decomposition; and, (3) an algorithm to construct approximate minimizations of a given WFA. The goal of the approximate minimization algorithm is to start from a minimal WFA and produce a smaller WFA that is close to the given one in a certain sense. The desired size of the approximating automaton is given as input. I will give bounds describing how well the approximation emulates the behavior of the original WFA.

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 will be based on my habilitation defense talk from Nov. 27 2018, which was dedicated to the algorithmic complexity of well-quasi-orders. The latter find applications in verification, where they allow to tackle systems featuring an infinite state-space, representing for instance integer counters, the number of active threads in concurrent settings, real-time clocks, call stacks, cryptographic nonces, or the contents of communication channels.

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

Nowhere dense graph classes, introduced by Nesetril and Ossona de Mendez, are a broad family of sparse graph classes for which many algorithmic problems which are hard in general become tractable. In particular, model checking first-order logic is fixed-parameter tractable over such classes, as shown recently by Grohe, Kreutzer, and Siebertz. With the aim of finding generalizations of this result to dense graph classes, I will talk about some recent developments in the study of the connections between nowheredenseness and stability (developed by Shelah).

Automata
Friday January 19, 2018, 2:30PM, Salle 3052
Verónica Becher (Universidad de Buenos Aires and CONICET) Randomness and uniform distribution modulo one

How is algorithmic randomness related to the classical theory of uniform distribution? In this talk we consider the definition of Martin-Löf randomness for real numbers in terms of uniform distribution of sequences. We present a necessary condition for a real number to be Martin-Löf random, and a strengthening of that condition which is sufficient for Martin-Löf randomness. For this strengthening we define a notion of uniform distribution relative to the computably enumerable open subsets of the unit interval. We call the notion Sigma^0_1-uniform distribution.

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

The problem of querying description logic knowledge bases using database-style queries (in particular, conjunctive queries) has been a major focus of recent description logic research. An important issue that arises in this context is how to handle the case in which the data is inconsistent with the ontology. Indeed, since in classical logic an inconsistent logical theory implies every formula, inconsistency-tolerant semantics are needed to obtain meaningful answers. I will first present a practical approach for querying inconsistent DL-Lite knowledge bases using three natural semantics (AR, IAR, and brave) previously proposed in the literature and that rely on the notion of a repair, which is an inclusion-maximal subset of the data consistent with the ontology. Since these three semantics provide answers with different levels of confidence, I will then present a framework for explaining query results, to help the user to understand why a given answer was or was not obtained under one of the three semantics.

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

We study Nash equilibria in games on graphs with an imperfect monitoring based on a public signal. In such games, deviations and players responsible for those deviations can be hard to detect and track. We propose a generic epistemic game abstraction, which conveniently allows to represent the knowledge of the players about these deviations, and give a characterization of Nash equilibria in terms of winning strategies in the abstraction. We then use the abstraction to develop algorithms for some payoff functions.

Automata
Friday November 24, 2017, 2:30PM, Salle 3052
Paul Brunet (University College London) Pomset languages and concurrent Kleene algebras

Concurrent Kleene algebras (CKA) and bi-Kleene algebras support equational reasoning about computing systems with concurrent behaviours. Their natural semantics is given by series(-parallel) rational pomset languages, a standard true concurrency semantics, which is often associated with processes of Petri nets.

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

My presentation is about effective characterisations: given a representation of a regular language, decide if the language is “simple” in some specific sense. A classical example of such a characterisation is the result by Schutzenberger, McNaughton, and Papert, saying that it is decidable if a given regular language of finite words can be defined in first-order logic. Over the years, such characterisations were provided for many other natural classes of languages, especially in the case of finite and infinite words. It is often assumed that a “golden standard” for such a characterisation is to provide equations that must be satisfied in a respective algebra representing the language.

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

In this talk I will discuss the following natural question: Given a class of computational models C, does there exist two distinct inputs which give the same output for all the models in the class. I will discuss this question more precisely for weighted automata in general and for max-plus automata in particular. Weighted automata are a quantitative extension of automata which allows to compute values such as costs and probabilities. Max-plus automata are a special case of weighted automata, particularly suitable to model gain optimisation problems. We will see that in this last case, we end up with particularly intricate (and open) questions, related to finding identities in the semiring of tropical matrices.

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

We present a few results and several open problems concerning complete deterministic finite automata in which every non-empty subset of the state set occurs as the image of the whole state set under the action of a suitable input word. In particular, we give a complete description of such automata with minimal transition monoid size.

Automata
Friday October 20, 2017, 2:30PM, Salle 3058
Sylvain Perifel (IRIF) Lempel-Ziv: a “one-bit catastrophe” but not a tragedy

The robustness of the famous compression algorithm of Lempel and Ziv is still not well understood: in particular, until now it was unknown whether the addition of one bit in front of a compressible word could make it incompressible. This talk will answer that question, advertised by Jack Lutz under the name “one-bit catastrophe” and which has been around since at least 1998. We will show that a “well” compressible word remains compressible when a bit is added in front of it, but some “few” compressible words indeed become incompressible. This is a joint work with Guillaume Lagarde.

Automata
Friday October 6, 2017, 2:30PM, Salle 3058
Nahtanaël Fijalkow (University College London) Comparing the speed of semi-Markov decision processes

A Markov decision process models the interactions between a controller giving inputs and a stochastic environment. In this well-studied model, transitions are fired instantaneously. We study semi-Markov decision processes, where each transition takes some time to fire, determined by a given probabilistic distribution (for instance, an exponential distribution). The question we investigate is how to compare two semi-Markov decision processes. We introduce and study the algorithmic complexity of two relations, “being faster than”, and “being equally fast as”.

Automata
Thursday July 13, 2017, 2:30PM, Amphi Turing
Thibault Godin (IRIF) Mealy machines, automaton (semi)groups, decision problems, and random generation (PhD defence)

Dans le cadre des journées de clôture du projet MealyM (https://mealym.sciencesconf.org/)

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)

Dans le cadre des journées de clôture du projet MealyM (https://mealym.sciencesconf.org/)

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.

A new classification scheme for real numbers will be given, motivated by ideas from statistical mechanics in general and work of Knauf and Fiala and Kleban in particular. Critical for this classification of real numbers will be the Diophantine properties of continued fraction expansions. Underneath this classification is a new partition function on the space of infinite sequences of zeros and ones.

Automata
Friday June 9, 2017, 2:30PM, Salle 1006
Pierre Ohlmann (ENS de Lyon) Invariant Synthesis for Linear Dynamical Systems

The Orbit Problem consists of determining, given a linear transformation $A$ on $Q^d$, together with vectors $x$ and $y$, whether the orbit of $x$ under repeated applications of $A$ can ever reach $y$.

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

Formal models for the computation of problems, say circuits, automata, Turing machines, can be naturally extended to compute word-to-word functions. But abstracting from the computation model, what does it mean to “lift” a language class to functions? We propose to address that question in a first step, developing a robust theory that incidentally revolves around the (topological) notion of continuity. In language-theoretic terms, a word-to-word function is V-continuous, for a class of languages V, if it preserves membership in V by inverse image.

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

We are interested in 2-dimensional cellular automata and more precisely in the recognition of langages in small time. The time complexity we consider is called real-time and is rather classic for the study of cellular automata. It consists of the smallest amount of time needed to read the whole imput. It has been shown that this set of langages depend on the neighborhood of the automaton. For example the two most used neighborhoods (Moore and von Neumann ones) are different with respect to this complexity. Our study deals with more generic sets of neighborhoods, round and diamond neighborhoods. We prove that all diamond neighborhoods can recognize the same langages in real time and that the round neighborhoods can recognize stricly less than the diamond ones.

Automata
Friday May 12, 2017, 2:30PM, Salle 1006
Paul-Elliot Anglès D'auriac (LACL) Higher computability and Randomness

Several notions of computability have been defined before every one agreed that Turing Machines are the good model of computation, a statement raised to the widely accepted Church-Turing Thesis. However, since then, lots of stronger computability notions have been defined and studied, for the sake of math and because it gives us new insight on some already existing fields.

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

In this talk I will give a gentle introduction to symbolic dynamics and motivate an open question in this field: which are the structures where can we construct aperiodic tilings using local rules. I will then introduce the notion of simulation of an effective dynamical system and show how these results can be used to produce aperiodic tilings in extremely complicated structures. We end the talk by presenting a novel simulation theorem which allows to show the existence of such tilings in the Grigorchuk group.

Automata
Friday April 21, 2017, 2:30PM, Salle 1006
Wolfgang Steiner (IRIF) Recognizability for sequences of morphisms

We investigate different notions of recognizability for a free monoid morphism $\sigma: A^* \to B^*$. Full recognizability occurs when each (aperiodic) two-sided sequence over $B$ admits at most one tiling with words $\sigma(a)$, $a \in A$. This is stronger than the classical notion of recognizability of a substitution $\sigma$, where the tiling must be compatible with the language of the substitution. We show that if $A$ is a two-letter alphabet, or if the incidence matrix of $\sigma$ has rank $|A|$, or if $\sigma$ is permutative, then $\sigma$ is fully recognizable. Next we investigate the classical notion of recognizability and improve earlier results of Mossé (1992) and Bezuglyi, Kwiatkowski and Medynets (2009), by showing that any substitution is recognizable for aperiodic points in its substitutive shift. Finally we define (eventual) recognizability for sequences of morphisms which define an $S$-adic shift. We prove that a sequence of morphisms on alphabets of bounded size, such that compositions of consecutive morphisms are growing on all letters, is eventually recognizable for aperiodic points. We provide examples of eventually recognizable, but not recognizable, sequences of morphisms, and sequences of morphisms which are not eventually recognizable. As an application, for a recognizable sequence of morphisms, we obtain an almost everywhere bijective correspondence between the $S$-adic shift it generates and the measurable Bratteli-Vershik dynamical system that it defines.

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

An automatic presentation (also called an FA-presentation) is a description of a relational structure using regular languages. The concept an FA-presentation arose in computer science, to fulfil a need to extend finite model theory to infinite structures. Informally, an FA-presentation consists of a regular language of abstract representatives for the elements of the structure, such that each relation (of arity $n$, say) can be recognized by a synchronous $n$-tape automaton. An FA-presentation is “unary” if the language of representatives is over a 1-letter alphabet.

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

Il y a 50 ans, Cerny a posé une conjecture combinatoire sur les automates, qui n'est toujours pas résolue. Un automate est dit synchronisé quand il existe un mot u et un état p tel que depuis n'importe quel état, si on lit u on arrive en p. Sa conjecture est que si l'automate synchronisé possède n états, alors il existe un tel u de longueur au plus (n-1)2. Dans cet exposé, nous nous intéresserons à la version probabiliste de la conjecture de Cerny : on montrera qu'un automate aléatoire est non seulement synchronisé (résultat déjà prouvé par Berlinkov), mais qu'en plus la conjecture de Cerny est vraie avec forte probabilité.

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.

On s'intéresse au parallèle entre 2 problèmes sur des modèles distincts d'automates. D'une part, les automates de Mealy (transducteurs lettre à lettre complets) qui produisent des semi-groupes engendrés par les transformations sur les mots infinis associées aux états. En 2013, Gillibert a montré que le problème de la finitude de ces semi-groupes était indécidable, en revanche la question est ouverte dans le cas où l'automate de Mealy produit un groupe. D'autre part, les automates cellulaires unidirectionnels pour lesquels la question de la décidabilité de la périodicité est ouverte. On peut montrer l'équivalence de ces problèmes. On fera un pas vers une preuve d'indécidabilité en montrant qu'il est possible de simuler du calcul Turing dans un automate cellulaire unidirectionnel réversible, rendant ainsi des problèmes de prédiction indécidables ainsi que la question de la périodicité partant d'une configuration donnée finie.

Automata
Friday March 17, 2017, 2:30PM, Salle 1006
Fabian Reiter (IRIF) Asynchronous Distributed Automata: A Characterization of the Modal Mu-Fragment

I will present the equivalence between a class of asynchronous distributed automata and a small fragment of least fixpoint logic, when restricted to finite directed graphs. More specifically, the considered logic is (a variant of) the fragment of the modal μ-calculus that allows least fixpoints but forbids greatest fixpoints. The corresponding automaton model uses a network of identical finite-state machines that communicate in an asynchronous manner and whose state diagram must be acyclic except for self-loops. As a by-product, the connection with logic also entails that the expressive power of those machines is independent of whether or not messages can be lost.

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

Given an integer base $b>1$, a set of integers is represented in base $b$ by a language over $\{0,1,\dots,b-1\}$. The set is said $b$-recognisable if its representation is a regular language. It is known that eventually periodic sets are $b$-recognisable in every base $b$, and Cobham's theorem imply the converse: no other set is $b$-recognisable in every base $b$.

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

No knowledge in arithmetic complexity will be assumed.

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

In the first part of the talk I will recall the duality approach to language recognition. To start with, I will explain the following simple fact. The elements of the syntactic monoid of a regular language $L$ over a finite alphabet $A$ are in one to one correspondence with the atoms of the finite sub-Boolean algebra of $P(A^*)$ generated by the quotients of $L$. This correspondence can be seen as an instance of Stone duality for Boolean algebras, and has lead to a topological notion of recognition for non-regular languages, the so called Boolean spaces with internal monoids.

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

A subset of natural numbers is called an IP-set if it contains an infinite increasing sequence of numbers and all its finite sums. In the talk we show how certain families of uniformly recurrent words can be used to generate IP-sets, as well as sets possessing some related additive properties.

Automata
Friday January 27, 2017, 2:30PM, Salle 3052
Nadime Francis (University of Edinburgh) Schema Mappings for Data Graphs

Schema mappings are a fundamental concept in data integration and exchange, and they have been thoroughly studied in different data models. For graph data, however, mappings have been studied in a very restricted context that, unlike real-life graph databases, completely disregards the data they store. Our main goal is to understand query answering under graph schema mappings - in particular, in exchange and integration of graph data - for graph databases that mix graph structure with data. We show that adding data querying alters the picture in a very significant way.

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.

I will discuss a notion of equivalence between two probabilistic systems introduced by Larsen and Skou in 89 called probabilistic 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.

Let $(X,T)$ be a one-dimensional invertible subshift. The 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

The evaluation of queries is a central problem in database management systems. Given a query q and a database D the evaluation of q over D consists in computing the set q(D) of all answers to q on D. An interesting case is when the query is boolean (aka the model checking problem, where the answer to the query is either a “yes” or a “no”). Even for boolean query, the problem of computing the answer (with input q and D) is already PSpace-complete. For non-boolean queries, the size of the output can blow up to |D|^r, where r is the arity of q. It is therefore not always realistic to compute the entire set of solutions. Moreover, the time needed to construct the set might not reflect the difficulty of the task.

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

The entropy of a language is a measure of its complexity and a well-studied dynamical invariant. I consider two related questions: for a given class of languages, can this parameter be computed, and what values can it take?

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

Joint work with Zoltán Ésik University of Szeged, Hungary

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

In a one-counter automaton (OCA), one can produce a letter from some finite alphabet, increment and decrement the counter by one, or compare it with constants up to some threshold. It is well-known that universality and language inclusion for OCAs are undecidable. In this paper, we consider OCAs with counter observability: Whenever the automaton produces a letter, it outputs the current counter value along with it. Hence, its language is now a set of words over an infinite alphabet. We show that universality and inclusion for that model are PSPACE-complete, thus no harder than the corresponding problems for finite automata. In fact, by establishing a link with visibly one-counter automata, we show that OCAs with counter observability are effectively determinizable and closed under all boolean operations.

Automata
Friday November 18, 2016, 2:30PM, Salle 1006
Nathan Lhote (LaBRI & ULB) Towards an algebraic theory of rational word functions

In formal language theory, several different models characterize regular languages, such as finite automata, congruences of finite index, or monadic second-order logic (MSO). Moreover, several fragments of MSO have effective characterizations based on algebraic properties, the most famous example being the Schützenberger-McNaughton and Papert theorem linking first-order logic with aperiodic congruences. When we consider transducers instead of automata, such characterizations are much more challenging, because many of the properties of regular languages do not generalize to regular word functions. In this paper we consider functions that are definable by one-way transducers (rational functions). We show that the canonical bimachine of Reutenauer and Schützenberger preserves certain algebraic properties of rational functions, similar to the syntactic congruence for languages. In particular, we give an effective characterization of functions that can be defined by an aperiodic one-way transducer.

Automata
Friday November 4, 2016, 9:20AM, Salle 3052
Lia Infinis Workshop

Program:
  • (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

More details are available here.

Automata
Friday October 28, 2016, 2:30PM, Salle 1006
Vincent Jugé (LSV, ENS de Cachan) Is the right relaxation normal form for braids automatic?

Representations of braids as isotopy classes of laminations of punctured disks are related with a family of normal forms, which we call relaxation normal forms. Roughly speaking, every braid is identified with a picture on a punctured disk, and reducing step-by-step the complexity of this picture amounts to choosing a relaxation normal form of the braid.

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

A successful idea in the area of verification is to consider finite-state abstractions of infinite-state systems. A prominent example is the fact that many language classes satisfy a Parikh's theorem, i.e. for each language, there exists a finite automaton that accepts the same language up to the order of letters. Hence, provided that the abstraction preserves pertinent properties, this allows us to work with finite-state systems, which are much easier to handle.

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

In this talk, we study a model computing relations over finite words, generalising one- and two-way transducers. The model, called two-way two-tape automaton, consists in a finite-state machine with two read-only tapes, each one with a reading head able to go both ways. We first emphasize its relation with 4-way automata, which recognize sets of two-dimensional arrays of letters called picture languages; such correspondence provides a proof of the undecidability of the model, and an example separating determinism and non-determinism. We then describe several techniques which, applied to our model, establish (non-)closure properties of the recognizable relations. Finally, the main result presented in this talk is that alternating two-way two-tape automata are not closed under complementation. The proof is a refinement of one of J. Kari for picture languages.

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 study the classical problem of conjunctive query evaluation. This problem admits multiple formulations and has been studied in numerous contexts; for example, it is a formulation of the constraint satisfaction problem, as well as the problem of deciding if there is a homomorphism from one relational structure to another (which transparently generalizes the graph homomorphism problem).

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

9h30-9h45 welcome

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

Word equations are combinatorial equalities between strings of symbols, variables and functions, which can be used to model problems in a wide range of domains. While some complexity results for the solving of specific classes of equations are known, currently there does not exist any equation solver publicly available. Recently, we have proposed the implementation of such a solver based on Boolean satisfiability that leverages existing SAT solvers for this purpose. In this paper, we propose a new representation of equations on words having fixed length, by using an enriched graph data structure. We discuss the implementation as well as experimental results obtained on a sample of equations.

Automata
Friday June 17, 2016, 2:30PM, Salle 1003
Arthur Milchior (IRIF) Deterministic Automaton and FO[<,mod] integer set

We consider deterministic automata which accept vectors of d integers for a fixed positive integer d. A deterministic automaton is then a finite representation of the sets of vectors it accepts. Many operations are particularly efficient with this representation, such as intersection of sets, testing whether two sets are equal or deciding whethersuch an automaton accepts a Presburger-definable set, that is a FO[+,<]-definable set over integers. We consider a similar problem for less expressive logics such as FO[<,0,moda] or \FO[+1,0,mod], where mod is the class of modular relations.

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

We present in this work an alternative solution to perfect-information stochastic parity games. Instead of using the framework of μ-calculus, which hides completely the algorithmic aspect, we solve it by induction on the number of absorbing states.

Automata
Friday June 3, 2016, 2:30PM, Salle 1003
Howard Straubing (Boston College) Two Variable Logic with a Between Predicate

We study an extension of FO^2[<], first-order logic interpreted in finite words in which only two variables are used. We adjoin to this language two-variable atomic formulas that say, 'the letter a appears between positions x and y'. This is, in a sense, the simplest property that is not expressible using only two variables.

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

This PhD is about two natural extensions of Finite Automata: the 2-way FA (2FA) and the 2-way transducers (2T).

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

Weighted automata (WA) extend finite-state automata defining functions from the set of words to a semiring S. Recently, cost register automata (CRA) have been introduced as an alternative model to describe any function realised by a WA by means of a deterministic machine.

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

Matrices and matrix products play a crucial role in a representation and analysis of various computational processes. Unfortunately, many simply formulated and elementary problems for matrices are inherently difficult to solve even in dimension two, and most of these problems become undecidable in general starting from dimension three or four. Let us given a finite set of square matrices (known as a generator) which is forming a multiplicative semigroup S. The classical computational problems for matrix semigroups are:
  • 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

We introduce Sturmian colorings of regular trees, which are colorings of minimal unbounded factor complexity. Then, we classify Sturmian colorings into two families, namely cyclic and acyclic ones. We characterize acyclic Sturmian colorings in a way analogous to continued faction algorithm of Sturmian words. As for cyclic Sturmian colorings, we show that the coloring is a countable union of a periodic coloring, possibly union with a regular subtree colored with one color.

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

Une tuile de Wang est un carré dont les bords sont colorés. Étant donné un ensemble fini de tuiles de Wang, on cherche à savoir s'il est possible de paver le plan discret tout entier avec ces tuiles, en mettant une tuile par case de sorte que deux tuiles adjacentes aient la même couleur sur le bord qu'elles partagent. On s'intéresse plus particulièrement aux jeux de tuiles apériodiques, ceux pour lesquels un pavage existe, mais où il est impossible de paver le plan périodiquement. Ces jeux de tuiles sont une des briques de base de la majorité des résultats en dynamique symbolique multidimensionnelle.

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

An infinite language L determines an infinite word α if every string in L is a prefix of α. If L is regular, it is known that α must be ultimately periodic; conversely, every ultimately periodic word is determined by some regular language. We investigate other classes of languages to see what infinite words they determine, focusing on languages recognized by various kinds of 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

Two intimately related new classes of games are introduced and studied: entropy games (EGs) and matrix multiplication games (MMGs). An EG is played on a finite arena by two-and-a-half players: Despot, Tribune and the non-deterministic People. Despot wants to make the set of possible People’s behaviors as small as possible, while Tribune wants to make it as large as possible. An MMG is played by two players that alternately write matrices from some predefined finite sets. One wants to maximize the growth rate of the product, and the other to minimize it. We show that in general MMGs are undecidable in quite a strong sense. On the positive side, EGs correspond to a subclass of MMGs, and we prove that such MMGs and EGs are determined, and that the optimal strategies are simple. The complexity of solving such games is in NP ∩ coNP.

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