Day, hour and place

Friday at 2:30pm, room 3052

The calendar of events (iCal format).
In order to add the event calendar to your favorite agenda, subscribe to the calendar by given this link


Next talks

Friday October 30, 2020, 2:30PM, Salle 3052
Wojciech Czerwiński (University of Warsaw) Universality problem for unambiguous Vector Addition Systems with States

I will show that the universality problem is ExpSpace-complete for unambiguous VASS, which is in strong contrast with Ackermann-completeness of the same problem for nondeterministic VASS. I also plan to present some more results concerning the interplay between unambiguity and VASS.

(joint work with Diego Figueira and Piotr Hofman)

Friday November 6, 2020, 2:30PM, Salle 3052
Denis Kuperberg (LIP, ENS Lyon, CNRS) Recognizing Good-for-Games automata: the G2 conjecture

In the setting of regular languages of infinite words, Good-for-Games (GFG) automata can be seen as an intermediate formalism between determinism and nondeterminism, with advantages from both worlds. Indeed, like deterministic automata, GFG automata enjoy good compositional properties (useful for solving games and composing automata and trees) and easy inclusion checks. Like nondeterministic automata, they can be exponentially more succinct than deterministic automata. I will focus in this talk on the following problem: given a nondeterministic parity automaton on infinite words, is it GFG ? The complexity of this problem is one of the main remaining open questions concerning GFG automata, motivated by the potential applications that would come with an efficient algorithm. After giving the necessary context, I will explain the current understanding on this question, and describe a simple polynomial-time algorithm that is conjectured to solve the problem, but has only been proven correct if the input is a Büchi or a co-Büchi automaton.

Thursday November 12, 2020, 3:30PM, Salle 3052
Guillermo Alberto Perez (University of Antwerp) Coverability in 1-VASS with Disequality Tests

In this talk we will focus on the so-called control-state reachability problem (also called the coverability problem) for 1-dimensional vector addition systems with states (VASS). We show that this problem lies in NC: the class of problems solvable in polylogarithmic parallel time. We will also generalize the problem to allow disequality constraints on transitions (i.e., we allow transitions to be disabled if the accumulated weight is equal to a specific value). For this generalization, we show that the coverability problem is solvable in polynomial time even though a shortest run may have exponential length.

Unusual time!

Friday November 20, 2020, 2:30PM, Salle 3052
Victor Lutfalla (LIPN) TBD

Friday November 27, 2020, 2:30PM, Salle 3052
Nathan Lhote (LaBRI) Pebble Minimization of Polyregular Functions.

We show that a polyregular word-to-word function is regular if and only if its output size is at most linear in its input size. Moreover a polyregular function can be realized by: a transducer with two pebbles if and only if its output has quadratic size in its input, a transducer with three pebbles if and only if its output has cubic size in its input, etc. Moreover the characterization is decidable and, given a polyregular function, one can compute a transducer realizing it with the minimal number of pebbles. We apply the result to mso interpretations from words to words. We show that mso interpretations of dimension k exactly coincide with k-pebble transductions.

Friday December 4, 2020, 2:30PM, Salle 3052
Georg Zetzsche Rational subsets of Baumslag-Solitar groups

Friday December 11, 2020, 2:30PM, Salle 3052
Joël Ouaknine (MPI-SWS) Holonomic Techniques, Periods, and Decision Problems

Holonomic techniques have deep roots going back to Wallis, Euler, and Gauss, and have evolved in modern times as an important subfield of computer algebra, thanks in large part to the work of Zeilberger and others over the past three decades. In this talk, I will give an overview of the area, and in particular will present a select survey of known and original results on decision problems for holonomic sequences and functions. I will also discuss some surprising connections to the theory of periods and exponential periods, which are classical objects of study in algebraic geometry and number theory; in particular, I will relate the decidability of certain decision problems for holonomic sequences to deep conjectures about periods and exponential periods, notably those due to Kontsevich and Zagier.

Parts of this talk will be based on the paper “On Positivity and Minimality for Second-Order Holonomic Sequences”, .

Friday December 18, 2020, 2:30PM, Salle 3052
Damien Pous Cyclic proofs, System T and the power of contraction

Friday January 29, 2021, 2:30PM, Salle 3052
Stefan Göller (University of Kassel) TBD

Previous talks

Year 2020

Friday October 16, 2020, 2:30PM, Salle 3052
Lorenzo Clemente (Faculty of Mathematics, Informatics and Mechanics, University of Warsaw.) Bidimensional linear recursive sequences and universality of unambiguous register automata

We study the universality and inclusion problems L(A)⊆L(B) for register automata over equality data. We show that the universality and inclusion problems can be solved in 2-EXPTIME when both automata A, B are without guessing and B is unambiguous, which improves on the recent 2-EXPSPACE upper bound by Mottet and Quaas. We proceed by reducing inclusion to universality, and then universality to the problem of counting the number of orbits of runs of the automaton. We show that the orbit-counting function satisfies a system of bidimensional linear recursive equations with polynomial coefficients (linrec), which generalises analogous recurrences for the Stirling numbers of the second kind, and then we show that universality reduces to the zeroness problem for linrec sequences. While such a counting approach is classical and has successfully been applied to unambiguous finite automata and grammars over finite alphabets, its application to register automata over infinite alphabets is novel.

We provide two algorithms to decide the zeroness problem for the linrec sequences arising from orbit-counting functions. Both algorithms rely on skew polynomials. The first algorithm performs variable elimination and has elementary complexity. The second algorithm relies on the computation of the Hermite normal form of matrices over a skew polynomial field. This yields an EXPTIME decision procedure for the zeroness problem, which in turn yields the claimed bounds for the universality and inclusion problems of register automata.

Friday October 9, 2020, 2:30PM, Salle 3052 and online on BigBlueButton
Olivier Bournez (LIX) Characterization of computability and complexity classes with difference equations

We will discuss the expressive and computational power of Ordinary Differential Equations (ODEs). We present the general theory of discrete ODEs for computation theory, we illustrate this with various examples of algorithms, and we provide several implicit characterizations of complexity and computability classes.

Friday June 26, 2020, 2:30PM, Held online, on BigBlueButton
Laure Daviaud (City University of London) About learning automata and weighted automata

In this talk, I will present algorithms to learn deterministic finite automata (due to Angluin) and weigthed automata over the usual semiring R with addition and multiplication (due to Beimel, Bergadano, Bshouty, Kushilevitz and Varricchio). I will then present some related open questions and pinpoint the difficulty that arise when trying to generalise these algorithms to any semiring.

Friday June 19, 2020, 2:30PM, Online on BigBlueButton
Sven Dziadek Weighted Logics and Weighted Simple Automata for Context-Free Languages of Infinite Words

We investigate weighted context-free languages of infinite words, a generalization of ω-context-free languages (Cohen, Gold 1977) and an extension of weighted context-free languages of finite words (Chomsky, Schützenberger 1963). As in the theory of formal grammars, these weighted languages, or ω-algebraic series, can be represented as solutions of ω-algebraic systems of equations and by weighted ω-pushdown automata.

Our results are threefold. We show that ω-algebraic systems can be transformed into Greibach normal form. Our second result proves that simple ω-pushdown automata recognize all ω-algebraic series. Simple pushdown automata do not use ε-transitions and can change the stack only by at most one symbol. We use these results to prove a logical characterization of weighted ω-context-free languages in the sense of Büchi, Elgot and Trakhtenbrot.

This is joint work with Manfred Droste and Werner Kuich.

Friday June 12, 2020, 2:30PM, Online (BigBlueButton)
Kuize Zhang On detectability of finite automata and labeled Petri nets

Abstract: Detectability is a basic property of partially observed dynamic systems. If a system satisfies such a property, then one can use an observed output sequence generated by the system to determine its internal states after some time. This property plays an important role in many problems such as state estimation and controller synthesis. Finite automata and labeled Petri nets are two widely-studied models in discrete-event systems, which consist of transitions between discrete states driven by spontaneous occurrences of events, and can be seen as abstractions of many practical systems. (A supervisory control framework for synthesising controllers in discrete-event systems was initiated by Ramadge and Wonham in the late 1980s.) In this talk, we introduce recent verification results on a particular property called strong detectability, for finite automata and labeled Petri nets, and several related further topics.

Friday June 5, 2020, 2:30PM, Online
K. S. Thejaswini (University of Warwick) The Strahler Number of a Parity Game

The Strahler number is a measure of branching complexity of rooted trees. We define the Strahler number of a parity game to be the the smallest Strahler number of the tree of any of its attractor decompositions. In this talk, we will argue that the Strahler number of a parity game is a robust, and hence arguably natural, parameter: it coincides with its alternative version based on trees of progress measures and— remarkably—with the register number defined by Lehtinen (2018). We will also look at how parity games can be solved in quasi-linear space and in time that is polynomial in the number of vertices n and linear in (d/2k)^k , where d is the number of priorities and k is the Strahler number. This complexity is quasi-polynomial because the Strahler number is at most logarithmic in the number of vertices. This significantly improves the running times and space achieved for parity games of bounded register number by Lehtinen (2018) and by Parys (2020).

Friday May 29, 2020, 2:30PM, Online
Liat Peterfreund (IRIF) Weight Annotation in Information Extraction

The framework of document spanners abstracts the task of information extraction from text as a function that maps every document (a string) into a relation over the document’s spans (intervals identified by their start and end indices). For instance, the regular spanners are the closure under the Relational Algebra (RA) of the regular expressions with capture variables, and the expressive power of the regular spanners is precisely captured by the class of vset-automata - a restricted class of transducers that mark the endpoints of selected spans. In this work, we embark on the investigation of document spanners that can annotate extractions with auxiliary information such as confidence, support, and confidentiality measures. To this end, we adopt the abstraction of provenance semirings by Green et al., where tuples of a relation are annotated with the elements of a commutative semiring, and where the annotation propagates through the (positive) RA operators via the semiring operators. Hence, the proposed spanner extension, referred to as an annotator, maps every string into an annotated relation over the spans. As a specific instantiation, we explore weighted vset-automata that, similarly to weighted automata and transducers, attach semiring elements to transitions. We investigate key aspects of expressiveness, such as the closure under the positive RA, and key aspects of computational complexity, such as the enumeration of annotated answers and their ranked enumeration in the case of numeric semirings. For a number of these problems, fundamental properties of the underlying semiring, such as positivity, are crucial for establishing tractability. This is a joint work with Johannes Doleschal, Benny Kimelfeld and Wim Martens.

Friday May 22, 2020, 2:30PM, Virtual seminar on BigBlueButton
Mikołaj Bojańczyk (MIMUW) Single use transducers over infinite alphabets

Automata for infinite alphabets, despite undeniable appeal, are a bit of a theoretical mess. Almost all models are non-equivalent as language recognisers: deterministic/nondeterministic/alternating, one-way/two-way, etc. Also monoids give a different class of languages, and mso gives yet another.

In this talk, I will describe how the single-use restriction can bring some order into this zoo. The single-use restriction says that once an atom from a register is queried, then that atom disappears. Among our results: a Factorisation Forest Theorem, a Krohn-Rhodes decomposition, and a class of “regular” transducers which admits four equivalent characterisations.

Joint work with Rafał Stefański.

Friday May 15, 2020, 2:30PM, Online, on BigBlueButton (usual link, available on the mailing list)
Thomas Colcombet (IRIF) Unambiguous Separators for Tropical Tree Automata

In this paper we show that given a max-plus automaton (over trees, and with real weights) computing a function f and a min-plus automaton (similar) computing a function g such that f ⩽ g, there exists effectively an unambiguous tropical automaton computing h such that f ⩽ h ⩽ g. This generalizes a result of Lombardy and Mairesse of 2006 stating that series which are both max-plus and min-plus rational are unambiguous. This generalization goes in two directions: trees are considered instead of words, and separation is established instead of characterization (separation implies characterization). The techniques in the two proofs are very different.

Thursday May 7, 2020, 2:30PM, Online, on BigBlueButton (usual link, available on the mailing list)
Florent Koechlin Weakly-unambiguous Parikh automata and their link to holonomic series

We investigate the connection between properties of formal languages and properties of their generating series, with a focus on the class of holonomic power series.

It is a classical result that regular languages have rational generating series and that the generating series of unambiguous context-free languages are algebraic. This connection between automata theory and analytic combinatorics has been successfully exploited. For instance, Flajolet used it in the eighties to prove the inherent ambiguity of some context-free languages using criteria from complex analysis.

Settling a conjecture of Castiglione and Massazza, we establish an interesting link between unambiguous Parikh automata and holonomic power series, which also yields characterizations of inherent ambiguity and algorithmic byproducts for these automata models.

This is a joint work with Alin Bostan, Arnaud Carayol and Cyril Nicaud.

Friday April 17, 2020, 2:30PM, Online
Jan Philipp Wächter (Universität Stuttgart) An Automaton Group with PSPACE-Complete Word Problem

Finite automata pose an interesting alternative way to present groups and semigroups. Some of these automaton groups became famous for their peculiar properties and have been extensively studied. In addition to that, there exists also a line of research on the general properties of the class of automaton groups.

One aspect of this research is the study of algorithmic properties of automaton groups and semigroups. While many natural algorithmic decision problems have been proven or are generally suspected to be undecidable for these classes, the word problem forms a notable exception. In the group case, it asks whether a given word in the generators is equal to the neutral element in the group in question and is well-known to be decidable for automaton groups. In fact, it was observed in a work by Steinberg published in 2015 that it can be solved in nondeterministic linear space using a straight-forward guess and check algorithm. In the same work, he conjectured that there is an automaton group with a PSPACE-complete word problem.

In a recent paper presented at STACS 2020, Armin Weiß and I could prove that there indeed is such an automaton group. To achieve this, we combined two ideas. The first one is a construction introduced by Daniele D'Angeli, Emanuele Rodaro and me to show that there is an inverse automaton semigroup with a PSPACE-complete word problem and the second one is an idea already used by Barrington in 1989 to encode NC¹ circuits in the group of even permutation over five elements. In the talk, we will discuss how Barrington's idea can be applied in the context of automaton groups, which will allow us to prove that the uniform word problem for automaton groups (were the generating automaton and, thus, the group is part of the input) is PSPACE- complete. Afterwards, we will also discuss the ideas underlying the construction to simulate a PSPACE-machine with an invertible automaton, which allow for extending the result to the non-uniform case. Finally, we will briefly look at related problems such as the compressed word problem for automaton groups.

Friday April 10, 2020, 2:30PM, Online
Javier Esparza An Efficient Normalisation Procedure for Linear Temporal Logic

Joint work with Salomon Sickert

In the mid 80s, Lichtenstein, Pnueli, and Zuck proved a classical theorem stating that every formula of LTL with past operators is equivalent to a formula of the form $\bigwedge_{i=1}^n \G\F \varphi_i \vee \F\G \psi_i $, where $\varphi_i$ and $\psi_i$ contain only past operators. Some years later, Chang, Manna, and Pnueli built on this result to derive a similar normal form for the future fragment of LTL. Both normalisation procedures had a non-elementary worst-case blow-up, and followed an involved path from LTL formulas to counter-free automata to star-free regular expressions and back to LTL. We improve on both points. We present a purely syntactic normalisation procedure from LTL to LTL, with single exponential blow-up, that can be implemented in a few dozen lines of Standard ML code. As an application, we derive a simple algorithm to translate LTL into deterministic Rabin automata. The algorithm normalises the formula, translates it into a special very weak alternating automaton, and applies a simple determinisation procedure, valid only for these special automata.

Online seminar on BigBlueButton

Friday April 3, 2020, 2:30PM, Online
Nathanaël Fijalkow (LaBRI) Assume Guarantee Synthesis for Prompt Linear Temporal Logic

An assume guarantee (AG) specification is of the form “Assumption implies Guarantee”. AG Synthesis is the following problem: given an AG specification, construct a system satisfying it.

In this talk I will discuss the case where both Assumptions and Guarantees are given by Prompt Linear Temporal Logic (Prompt LTL), which is a logic extending LTL by adding bound requirements such as “every request is answered in bounded time”.

The solution to the AG problem for Prompt LTL will be an invitation to the theory of regular cost functions.

Joint work with Bastien Maubert and Moshe Y. Vardi.

Séminaire Virtuel sur BigBlueButton

Friday March 27, 2020, 2:30PM, Salle 3052
Edwin Hamel-De Le Court To be announced.

Friday March 20, 2020, 2:30PM, Online
Pierre Ohlmann (IRIF) Controlling a random population

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

The seminar will take place virtually using the software BigBlueButton (see intranet). Detailed instructions will follow by email at 14:00.

Friday March 6, 2020, 10:30AM, Salle 3052
Stefan Milius (Friedrich-Alexander Universität Erlangen-Nürnberg) From Equational Specifications of Algebras with Structure to Varieties of Data Languages

We present a new category theoretic approach to equationally axiomatizable classes of algebras. This approach is well-suited for the treatment of algebras equipped with additional computationally relevant structure, such as ordered algebras, continuous algebras, quantitative algebras, nominal algebras, or profinite algebras. We present a generic HSP theorem and a sound and complete equational logic, which encompass numerous flavors of equational axiomizations studied in the literature. In addition, we use the generic HSP theorem as a key ingredient to obtain Eilenberg-type correspondences yielding algebraic characterizations of properties of regular machine behaviours. When instantiated for orbit-finite nominal monoids, the generic HSP theorem yields a crucial step for the proof of the first Eilenberg-type variety theorem for data languages.

Attention ! Horaire non habituel !

Friday March 6, 2020, 2:30PM, Salle 3052
Henning Urbat (FAU Erlangen-Nürnberg) Automata Learning: An Algebraic Approach

We propose a generic framework for learning unknown formal languages of various types (e.g. finite or infinite words, weighted and nominal languages). Our approach is parametric in a monad T that represents the given type of languages and their recognizing algebraic structures. Using the concept of an automata presentation of T-algebras, we demonstrate that the task of learning a T-recognizable language can be reduced to learning an abstract form of algebraic automaton whose transitions are modeled by a functor. For the important case of adjoint automata, we devise a learning algorithm generalizing Angluin’s L*. The algorithm is phrased in terms of categorically described extension steps; we provide for a termination and complexity analysis based on a dedicated notion of finiteness. Our framework applies to structures like ω-regular languages that were not within the scope of existing categorical accounts of automata learning. In addition, it yields new generic learning algorithms for several types of languages for which no such algorithms were previously known at all, including nominal languages with name binding, and cost functions. This talk is based on joint work with Lutz Schröder.

Friday February 28, 2020, 2:30PM, Salle 3052
Marie Van Den Bogaard (ULB) Subgame Perfect Equilibria in Quantitative Reachability Games

In this talk, we consider multiplayer games on graphs. In such games, each player has his own objective, that does not necessarily clash with the objectives of the other players. In this “non zero-sum” context, equilibria are a better suited solution concept than the classical winning strategy notion. We will focus on a refinement of the well-known Nash Equilibrium concept: Subgame Perfect Equilibrium (SPE for short), where players have to play rationnally in every scenario, even the ones that deviate from the planned outcome. We will explain why this refinement is a relevant solution concept in multiplayer games and show how to handle them in quantitative reachability games, where each player wants to minimize the number of steps to reach its own target set of vertices.

Tuesday February 25, 2020, 2PM, Salle 3052
Georg Zetsche (MPI SWS) Extensions of $\omega$-Regular Languages

We consider extensions of monadic second order logic over $\omega$-words, which are obtained by adding one language that is not $\omega$-regular. We show that if the added language $L$ has a neutral letter, then the resulting logic is necessarily undecidable. A corollary is that the $\omega$-regular languages are the only decidable Boolean-closed full trio over $\omega$-words.

(Joint work with Mikołaj Bojańczyk, Edon Kelmendi, and Rafał Stefański)

Note the unusual time (14:00).

Friday February 21, 2020, 2:30PM, Salle 3052
Luc Dartois (LACL) Reversible Transducers

Transducers extend automata by adding outputs to the transition, thus computing functions over words instead of recognizing languages. Deterministic two-way transducers define the robust class of regular functions which is, among other good properties, closed under composition. However, the best known algorithms for composing two-way transducers are rather involved and cause a double exponential blow-up in the size of the input machines. This contrasts with the rather direct and polynomial construction for composing one-way machines. In this talk, I will present the class of reversible transducers, which are machines that are both deterministic and co-deterministic. This class enjoys polynomial composition complexity, even in the two-way case. Although this class is not very expressive in the one-way scenario, I will show that any two-way transducer can be made reversible through a single exponential blow-up. As a consequence, the composition of two-way transducers can be done with a single exponential blow-up in the number of states, enhancing the best known algorithm from the 60s.

Maintenu malgré les vacances, car présence attendue d'une dizaine de personnes (après sondage)

Friday February 7, 2020, 2:30PM, Salle 3052
Youssouf Oualhadj (LACL) Life is random time is not: Markov decision processes with window objectives

The window mechanism was introduced by Chatterjee et al. to strengthen classical game objectives with time bounds. It permits to synthesize system controllers that exhibit acceptable behaviors within a configurable time frame, all along their infinite execution, in contrast to the traditional objectives that only require correctness of behaviors in the limit. The window concept has proved its interest in a variety of two-player zero-sum games, thanks to the ability to reason about such time bounds in system specifications, but also the increased tractability that it usually yields.

In this work, we extend the window framework to stochastic environments by considering the fundamental threshold probability problem in Markov decision processes for window objectives. That is, given such an objective, we want to synthesize strategies that guarantee satisfying runs with a given probability. We solve this problem for the usual variants of window objectives, where either the time frame is set as a parameter, or we ask if such a time frame exists. We develop a generic approach for window-based objectives and instantiate it for the classical mean-payoff and parity objectives, already considered in games. Our work paves the way to a wide use of the window mechanism in stochastic models.

Joint work with : Thomas Brihaye, Florent Delgrange, Mickael Randour.

Friday January 31, 2020, 2:30PM, Salle 3052
Arnaud Sangnier (IRIF) Deciding the existence of cut-off in parameterized rendez-vous networks

We study networks of processes which all execute the same finite-state protocol and communicate thanks to a rendez-vous mechanism. Given a protocol, we are interested in checking whether there exists a number, called a cut-off, such that in any networks with a bigger number of participants, there is an execution where all the entities end in some final states. We provide decidability and complexity results of this problem under various assumptions, such as absence/presence of a leader or symmetric/asymmetric rendez-vous.

This is a joint work with Florian Horn.

Friday January 17, 2020, 2:30PM, Salle 3052
Marc Zeitoun (LABRI) The star-free closure

A language of finite words is star-free when it can be built from letters using Boolean operations and concatenation. A well-known theorem of Schützenberger characterizes star-free languages as those recognized by an aperiodic monoid. Another theorem of Schützenberger gives an alternate definition: these are the languages that can be built using product, union, and, in a limited way, Kleene star (but complement is now disallowed).

These definitions can be rephrased using closure operators operating on classes of languages. In this talk, we investigate these operators and generalize the results of Schützenberger. This is joint work with Thomas Place.

Friday January 10, 2020, 2:30PM, Salle 3052
Karoliina Lehtinen Parity Games – the quasi-polynomial era

Parity games are central to the verification and synthesis of reactive systems: various model-checking, realisability and synthesis problems reduce to solving these games. Solving parity games – that is, deciding which player has a winning strategy – is one of the few problems known to be in both UP and co-UP yet not known to be in P. So far, the quest for a polynomial algorithm has lasted over 25 years.

In 2017 a major breakthrough occurred: parity games are solvable in quasi-polynomial time. Since then, several seemingly very distinct quasi-polynomial algorithms have been published, both by myself and others, and some of the novel ideas behind them have been applied to address other problems in automata theory.

In this talk, I will give an overview of these developments, including my own contribution to them, and the state-of-the art, with a slight automata-theoretic bias.

Year 2019

Tuesday December 17, 2019, 2:30PM, Salle 0010
Achim Blumensath (Masaryk University) Regular Tree Algebras

I present recent developments concerning a very general algebraic theory for languages of infinite trees which is based on the category-theoretical notion of a monad. The main result isolates a class of algebras that precisely captures the notion of regularity for such languages. In particular, we show that these algebras form a pseudo-variety and that syntactic algebras exists. If time permits I will conclude the talk with a few simple characterisation results obtained using this framework.

Noter la salle et l'horaire inhabituels.

Friday December 6, 2019, 2:30PM, Salle 3052
Wesley Fussner Residuation: Origins and Open Problems

Residuated lattices are a variety of ordered monoids whose study arises from from three directions: Algebras of ideals of rings, algebras of binary relations, and the semantics of substructural logics. This talk provides a survey of residuated lattices, discussing both their historical origins and current threads of research. We also offer an introduction to some difficult problems that arise their study, in particular connected to structure theorems for special classes of residuated lattices and their duality theory.

Friday November 29, 2019, 2:30PM, Salle 3052
Dmitry Chistikov (University of Warwick) On the complexity of linear arithmetic theories over the integers

Given a system of linear Diophantine equations, how difficult is it to determine whether it has a solution? What changes if equations are replaced with inequalities? If some of the variables are quantified universally? These and similar questions relate to the computational complexity of deciding the truth value of statements in various logics. This includes in particular Presburger arithmetic, the first-order logic over the integers with addition and order.

In this talk, I will survey constructions and ideas that underlie known answers to these questions, from classical results to recent developments, and open problems.

First, we will recall the geometry of integer linear programming and how it interacts with quantifiers. This will take us from classical results due to von zur Gathen and Sieveking (1978), Papadimitriou (1981), and others to the geometry of the set of models of quantified logical formulas. We will look at rational convex polyhedra and their discrete analogue, hybrid linear sets (joint work with Haase (2017)), and see, in particular, how the latter form a proper sub-family of ultimately periodic sets of integer points in several dimensions (the semi-linear sets, introduced by Parikh (1961)).

Second, we will discuss “sources of hardness”: which aspects of the expressive power make decision problems for logics over the integers hard. Addition and multiplication combined enable simulation of arbitrary Turing machines, and restriction of multiplication to bounded integers corresponds to resource-bounded Turing machines. How big can these bounded integers be in Presburger arithmetic? This leads to the problem of representing big numbers with small logical formulae, and we will see constructions by Fischer and Rabin (1974) and by Haase (2014). We will also look at the new “route” for expressing arithmetic progressions (in the presence of quantifier alternation) via continued fractions, recently discovered by Nguyen and Pak (2017).

Friday November 22, 2019, 2:30PM, Salle 3052
Alexis Bes Décider (R,+,<,1) dans (R,+,<,Z)

La structure (R,+,<,Z), où R désigne l'ensemble des réels et Z le prédicat unaire “être un entier”, admet l'élimination des quantificateurs et est décidable. Elle intervient notamment dans le domaine de la spécification et la vérification de systèmes hybrides. Elle peut être étudiée via les automates, en considérant des automates de Büchi qui lisent des réels représentés dans une base entière fixée. Boigelot et al. ont démontré en particulier que la classe des relations définissables dans (R,+,<,Z) coïncide avec celle des relations reconnaissables par automate en toute base. Une autre structure intéressante est (R,+,<,1), qui est moins expressive que (R,+,<,Z) mais définit les mêmes relations bornées. On présente une caractérisation topologique des relations définissables dans (R,+,<,Z) qui sont définissables dans (R,+,<,1), et on en déduit que le problème de savoir si une relation définissable dans (R,+,<,Z) est définissable dans (R,+,<,1) est décidable. Travail en commun avec Christian Choffrut.

Friday November 15, 2019, 2:30PM, Salle 3052
Patrick Totzke Timed Basic Parallel Processes

I will talk about two fun constructions for reachability analysis of one-clock timed automata, which lead to concise logical characterizations in existential Linear Arithmetic.

The first one describes “punctual” reachability relations: reachability in exact time t. It uses a coarse interval abstraction and counting of resets via Parikh-Automata. The other is a “sweep line” construction to compute optimal time to reach in reachability games played on one-clock TA.

Together, these can be used to derive a (tight) NP complexity upper bound for the coverability and reachability problems in an interesting subclass of Timed Petri Nets, which naturally lends itself to parametrised safety checking of concurrent, real-time systems. This contrasts with known super-Ackermannian completeness, and undecidability results for unrestricted Timed Petri nets.

This is joint work with Lorenzo Clemente and Piotr Hofman, and was presented at CONCUR'19. Full details are available at

Friday November 8, 2019, 2:30PM, Salle 3052
Daniel Smertnig (University of Waterloo) Noncommutative rational Pólya series

A rational series is a noncommutative formal power series whose coefficients are recognized by a weighted finite automaton (WFA). A rational series with coefficients in a field $K$ is a Pólya series if all nonzero coefficients are contained in a finitely generated subgroup of $K^\times$. Generalizing results of Pólya (1921), Benzaghou (1970), and Bézivin (1987) for the univariate case, we show that Pólya series are precisely the ones recognized by unambiguous WFAs.

This is joint work with Jason Bell. arXiv:1906.07271

Monday October 28, 2019, 11AM, Salle 1007
Pierre Ganty (IMDEA Software Institute) Deciding language inclusion problems using quasiorders

We study the language inclusion problem L1 ⊆ L2 where L1 is regular or context-free. Our approach checks whether an overapproximation of L1 is included in L2. Such overapproximations are obtained using quasiorder relations on words where the abstraction gives the language of all words “greater than or equal to” a given input word for that quasiorder. We put forward a range of quasiorders that allow us to systematically design decision procedures for different language inclusion problems such as context-free languages into regular languages and regular languages into trace sets of one-counter nets.

Friday October 25, 2019, 2:30PM, Salle 3052
Luca Reggio (Mathematical Institute, University of Bern) Limits of finite structures: a duality theoretic perspective

A systematic approach to the study of limits of finite structures, motivated by investigations in graph theory, has been developed by Nešetřil and Ossona de Mendez starting in 2012. The basic idea consists in embedding the set of finite structures into a space of measures which is complete, so that every converging sequence of finite structures admits a limit. This limit point can be always realized as a measure.

I will explain how this embedding into a space of measures dually corresponds to enriching First-Order Logic with certain probability operators. Further, I will relate this construction to first-order quantification in logic on words.

This talk is based on joint work with M. Gehrke and T. Jakl.

Friday October 11, 2019, 2:30PM, Salle 1016
Gaëtan Douéneau-Tabot (IRIF) Pebble transducers for modeling simple programs

Several models of automata with outputs (known as transducers) have been defined over the years to describe various classes of “regular-like” functions. Such classes generally have good decidability properties, and they have been shown especially relevant for program verification or synthesis. In this talk, we shall investigate pebble transducers, i.e. finite-state machines that can drop nested marks on their input. We provide various correspondences between these models and transducers that use registers, and we solve related membership problems. These results can be understood as techniques for program optimization, that can be useful in practice. This talk is based on joint work with P. Gastin and E. Filiot.

Friday July 5, 2019, 2:30PM, Salle 1001
Mahsa Shirmohammadi (CNRS) Büchi Objectives in Countable MDPs

We study countably infinite Markov decision processes with Büchi objectives, which ask to visit a given subset of states infinitely often. A question left open by T.P. Hill in 1979 is whether there always exist ε-optimal Markov strategies, i.e., strategies that base decisions only on the current state and the number of steps taken so far. We provide a negative answer to this question by constructing a non-trivial counterexample. On the other hand, we show that Markov strategies with only 1 bit of extra memory are sufficient. This work is in collaboration with Stefan Kiefer, Richard Mayr and Patrick Totzke, and is going to be presented in ICALP 2019. A full version is at

Friday June 14, 2019, 2:30PM, Salle 3052
Engel Lefaucheux (Max-Planck Institute for Software Systems, Saarbrucken) Simple Priced Timed Games are not That Simple

Priced timed games are two-player zero-sum games played on priced timed automata (whose locations and transitions are labeled by weights modeling the price of spending time in a state and executing an action, respectively). The goals of the players are to minimise or maximise the price to reach a target location. While one can compute the optimal values that the players can achieve (and their associated optimal strategies) when the weights are all positive, this problem with arbitrary integer weights remains open. In this talk, I will explain what makes this case more difficult and show how to solve the problem for a subclass of priced timed games (the so-called simple priced timed games).

Friday June 7, 2019, 2:30PM, Salle 3052
Jean-Éric Pin (IRIF) Un théorème de Mahler pour les fonctions de mots. (Jean-Eric Pin et Christophe Reutenauer)

Soit $p$ un nombre premier et soit $G_p$ la variété de tous les langages reconnus par un $p$-groupe fini (i.e. un groupe d'ordre une puissance de $p$). On donne deux façons de construire toutes les fonctions $f$ de $A^*$ dans $B^*$ (et même dans $F(B)$, le groupe libre de base $B$) qui possèdent la propriété suivante: si $L$ est une partie de $F(B)$ reconnue par un $p$-groupe fini, alors $f^{-1}(L)$ a la même propriété. Ce résultat découle d'une version non-commutative des séries de Newton et d'un célèbre théorème de Mahler en analyse $p$-adique.

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.

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).

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.

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.

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.

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.

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.

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?

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:

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.

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.

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.

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

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.

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.

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. 

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.

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.

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).

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.

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).

Friday October 5, 2018, 2:30PM, Salle 3052
Sam Van Gool (University of Amsterdam, ILLC) To be announced.

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

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.

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.

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.

Date inhabituelle : Mercredi

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.)

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.

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,. . . ).

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.

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.

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.

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.

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.

Séminaire de pôle

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.

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.

Précédée d'une réunion d'équipe à 13:45.

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).

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

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.

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.

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

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.

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.

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.

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.

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”.

Réunion mensuelle de l'équipe automates à 13:45 dans la même salle

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 (

Manuscrit disponible ici :

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 (

Manuscrit disponible ici :

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)

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.

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.

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.

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.

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.)

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.

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.

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.

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é.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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

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.

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.

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.

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.

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

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

More details are available here.

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.

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.

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.

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.

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

Démonstration du logiciel Vaucuson-R

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.

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.

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.

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.

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.

Hall F, 5ème étage, thèse disponible à l'adresse

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.

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.

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.

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.

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.

Monday March 21, 2016, 10AM, LABRI
Colloque En L'honneur De Marcel-Paul Schützenberger (21-25/03/2016) Programme

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.

Friday March 11, 2016, 2:30PM, Salle 0010
Anna-Carla Rousso (IRIF) To be announced.

Friday March 4, 2016, 2:30PM, Salle 0010
Thierry Bousch (Paris Sud) La Tour d'Hanoï, revue par Dudeney

Friday January 22, 2016, 2:30PM, Salle 0010
Laurent Bartholdi (ENS) To be announced.

Friday January 15, 2016, 2:30PM, Salle 0010
Viktoriya Ozornova (Universität Bremen) Factorability structures

Friday January 8, 2016, 2:30PM, Salle 0010
Antoine Amarilli (Télécom ParisTech) Provenance Circuits for Trees and Treelike Instances