## Automata

#### Day, hour and place

Friday at 2:00pm, room 3052

The calendar of events (iCal format).

In order to add the event calendar to your favorite agenda, subscribe to the calendar by using this link.

#### Contact(s)

The recordings of past seminars are at your disposal. Beware that these are password-protected, please contact the automata seminar staff to get a password.

### Next talks

Automata

Friday October 11, 2024, 2PM, Salle 3052

**Mihir Vahanwala** (MPI-SWS, Saarbrücken) *On the Monadic Second-Order Theory of Arithmetic Predicates*

- The MSO theory of (Nat; <, Pow-2, Pow-3) is decidable.

- The MSO theory of (Nat; <, Pow-2, Pow-3, Pow-6) is decidable.

- The MSO theory of (Nat; <, Pow-2, Pow-3, Pow-5) is decidable subject to Schanuel's conjecture.

- The MSO theory of (Nat; <, Squares, Pow-4) is decidable.

- The MSO theory of (Nat; <; Squares, Pow-2) is Turing-equivalent to the MSO theory of (Nat; <, S), where S is the unary predicate corresponding to the binary expansion of s = sqrt(2). As s is widely believed to be a weakly normal number, the corresponding MSO theory is in turn expected to be decidable.

The talk will give an overview of our techniques in general, and the automata theory and algebra that enable the above results in particular.

Automata

Friday October 18, 2024, 2PM, Salle 3071

**Fabian Reiter** (LIGM) *Locality via Alternation?*

I will start with an attempt to use logic to extend standard complexity theory to the distributed setting. It turns out that several classical concepts generalize well, including the polynomial hierarchy (and hence the complexity classes P and NP), the Cook-Levin theorem (which identifies Boolean satisfiability as a complete problem for NP), and Fagin's theorem (which characterizes NP as the problems expressible in existential second-order logic). But perhaps more surprisingly, separating complexity classes becomes easier in the general case: when extended to multiple computers, the polynomial hierarchy is provably infinite, while it remains notoriously open whether the same holds in the case of a single computer.

In the second part of the talk, I will use the previous results to address a central question in distributed computing: which problems are purely local, which problems are inherently global, and which problems lie between these extremes? The idea will be to measure locality using quantifier alternation, the key concept underlying the polynomial hierarchy.

The talk is based on my paper “A LOCAL View of the Polynomial Hierarchy”. - Proceedings version: https://doi.org/10.1145/3662158.3662774 - Full version: https://arxiv.org/abs/2305.09538

Automata

Friday October 25, 2024, 2PM, Salle 3052

**Isa Vialard** *Measuring well quasi-orders*

One main challenge is to compute the ordinal invariants of complex well quasi-orders built from simpler well quasi-orders through classical operation, such as the Cartesian product, and high-order constructions, like the finite words embedding. In my thesis, I computed compositionally the maximal order type of the direct product, the width of the multiset embedding, and the height and width of the multiset ordering. Furthermore, I compute the width of the Cartesian product in restricted cases and studied the ordinal measures of the finite powerset.In the process, I developed several tools and techniques, notably a game-theoretical approach to computing width using the notion of quasi-incomparable families of subsets. To tackle the width of the multiset ordering, I introduced and studied a fourth ordinal invariant, the friendly order type.

Automata

Friday November 8, 2024, 2PM, Salle 3052

**Benjamin Bordais** *To be announced.*

Automata

Friday November 15, 2024, 2PM, Salle 3052

**Luc Dartois** *To be announced.*

Automata

Friday November 22, 2024, 2PM, Salle 3052

**Pierre Letouzey** (IRIF) *To be announced.*

Automata

Friday November 29, 2024, 2PM, Salle 3052

**Olivier Carton** *Rauzy dimension and finite state dimension*

Automata

Friday December 13, 2024, 2PM, Salle 3052

**Vincent Michielini** (University of Warsaw) *Complexity of Maslov's Class K-bar*

This is a joint work with Oskar Fiuk and Dr Hab Emanuel Kieroński, both from Wrocław.

[*] the formula phi, written in NNF, is in K-bar if there exists a sequence ∀x1, …., ∀xk of universally quantified variables, not in the scope of any existential one, such that, for every atom of phi, the sequence of its variables either i) admits at most one unique variable, ii) ends with an existential variable, or iii) is exactly the sequence ∀x1, …., ∀xk. Yes, this is complicated. Don't worry, I'll give nice examples.

### Previous talks

#### Year 2024

Automata

Wednesday July 10, 2024, 2PM, Salle 3052

**Martin Zimmermann** *History-deterministic Pushdown Automata*

History-deterministic pushdown automata live up to that promise: their expressiveness lies strictly between that of deterministic and nondeterministic automata while solving games with history-deterministic winning conditions is EXPTIME-complete, while it is undecidable for nondeterministic pushdown automata.

But where there is light, there must be shadow: history-deterministic pushdown automata have poor closure properties and checking whether a pushdown automaton is history-deterministic is undecidable.

To end on a high note, we present several open problems related to history-deterministic pushdown automata.

Based on joint work with Ismaël Jecker, Shibashis Guha and Karoliina Lehtinen.

Automata

Friday June 28, 2024, 2PM, Salle 3052

**Lucas Larroque** *Normalisations of Existential Rules: Not so Innocuous!*

Automata

Friday June 21, 2024, 2PM, 3052

**Marc Zeitoun** *Nested temporal hierarchies of regular languages*

First, I will present these various characterizations. Then, I will introduce a general approach that encompasses all known results and allows us to obtain new ones. This approach relies on the use of an “operator” whose repeated application yields a hierarchy of classes of regular languages. Finally, I will present some results about this new hierarchy, in particular its relationship with the so-called concatenation hierarchy. This is joint work with Thomas Place.

Automata

Friday June 14, 2024, 2PM, Salle 3052

**Sylvain Schmitz** *On the Length of Strongly Monotone Descending Chains over ℕᵈ*

Automata

Friday June 7, 2024, 2PM, Zoom (+ Salle 3052)

**Lê Thành Dũng (Tito) Nguyễn** *Computing the polynomial degree of size-to-height increase for macro tree transducers*

Automata

Friday May 31, 2024, 2PM, Salle 3052

**Thomas Colcombet** *Bisimulation invariant MSO over finite transition systems*

Our proof techniques involve developing an algebraic theory of infinite regular trees, in particular establishing on the way that recognizable languages of regular trees coincide (over regular trees) with MSO definable language of trees.

Automata

Friday May 24, 2024, 2PM, Salle 3052

**Sreejith A V** *Decomposition results for algebras that recognize countable words*

Automata

Friday May 17, 2024, 2PM, Salle 3052

**Laure Daviaud** *Weighted automata: a la carte!*

Automata

Friday April 19, 2024, 2PM, Salle 3052

**Florent Capelli** *Direct Access For Conjunctive Queries with Negation*

- ArXiv version: https://arxiv.org/abs/2310.15800 - Published version: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2024.13

Automata

Friday April 12, 2024, 2PM, Salle 3052

**Guillaume Lagarde** *The complexity of learning temporal formulas from examples*

Automata

Friday March 29, 2024, 2PM, Salle 3052

**Leonid Libkin** *Embedded finite models and finitely representable databases: a forgotten area ready for a comeback*

Automata

Friday March 22, 2024, 2PM, Salle 3052

**Quentin Aristote** *Active Learning of Deterministic Transducers with Outputs in Arbitrary Monoids*

Automata

Friday March 8, 2024, 2PM, Salle 3052

**Rémi Morvan** (LaBRI) *Automatic relations through the prism of graph colourability and algebraic language theory*

**automatic (aka synchronous)**relations, defined as the binary relations of finite words that can be recognized by finite-state synchronous automata. We study two orthogonal approaches.

**- Graph theoretic properties:** we show that given an automatic graph (a graph defined by an automatic relation), the problem of whether the graph can be **regularly 2-coloured** (meaning that it can be 2-coloured, and for every colour, the set of words having this colour is a regular language) is surprisingly undecidable; this results yields the undecidability of the **separation problem of automatic relations** by a subclass of recognizable relations.

**- Language-theoretic properties:** on the contrary, we show that most of the reasonable language-theoretic properties of automatic relations are decidable. We develop an **algebraic theory for automatic relations**, called “synchronous algebras”, which are to relations as monoids are to languages. The three pillars of algebraic language theory hold in our settings, namely (1) all relations admit a syntactic synchronous algebra, which is finite if and only if the relation is automatic, (2) classes of automatic relations with nice closure properties (called pseudovarieties) are in natural correspondence with pseudovarieties of finite synchronous algebras and (3) the latter are exactly the classes of finite synchronous algebras which can be described by “profinite dependencies”, a generalization of classical profinite equations. Building on these results, we show how algebraic characterizations of pseudovarieties of regular languages can be lifted to the pseudovarieties of synchronous relations that they induce.

The graph-colourability part the talk is based on a joint work with Pablo Barceló and Diego Figueira published at MFCS '23.

Automata

Monday March 4, 2024, 4PM, Salle 3052

**Yann Strozecki** (DAVID, UVSQ) *A tutorial on enumeration complexity: defining tractability*

The focus is on understanding incremental polynomial time and polynomial delay which are the classes containing most problems. In particular we present an attempt to classify which saturation problems naturally in incremental polynomial time are in fact in polynomial delay and give separation and collapses for general classes. We also briefly present low complexity classes and way to completely avoid exhaustive enumeration, through compact representation and approximation of the solution set.

Automata

Friday March 1, 2024, 2PM, Salle 3052

**Benjamin Bordais** *From Local to Global Optimality in Concurrent Parity Games*

This is a joint work with my former PhD advisors Patricia Bouyer and Stéphane Le Roux, and it is based on a paper published in CSL 2024.

Automata

Thursday February 29, 2024, 2PM, Salle 3052

**Ivan Varzinczak** *An Introduction to Defeasible Description Logics*

Speaker's short CV: Ivan Varzinczak is an associate professor at Université Paris 8. He holds a PhD (2006) in artificial intelligence from Université Paul Sabatier, France. Ivan has co-authored over 75 peer-reviewed publications on logic-based approaches to knowledge representation and reasoning in AI. In 2019 he defended his habilitation at Université d'Artois, France. Ivan is an associate editor of Artificial Intelligence and of the Journal of Artificial Intelligence Research and chairman of the steering committee of the International Workshop on Nonmonotonic Reasoning. In 2022, he served as program chair of the 12th International Symposium on Foundations of Information and Knowledge Systems (FoIKS). He has had several visiting researcher appointments and taught courses and tutorials worldwide, including two courses at ESSLLI and two tutorials at IJCAI.

Automata

Friday February 23, 2024, 2PM, Salle 3052

**Sven Dziadek** (Inria Paris) *Acceptance Conditions for Weighted ω-Automata*

I will introduce the theory and detail those challenges.

Joint work with Uli Fahrenberg.

Automata

Friday February 16, 2024, 2PM, Salle 3052

**Dakotah Lambert** *Constraint-driven analysis of formal languages*

Automata

Friday February 2, 2024, 2PM, Salle 3052

**Laetitia Laversa** *k-synchronizability for distributed systems*

Automata

Friday January 26, 2024, 2PM, Salle 3052

**Thomas Schwentick** (TU Dortmund) *Work-efficient constant-time parallel dynamic and static algorithms*

The talk gives a short introduction to Dynamic Complexity and presents a recent and ongoing line of research that tries to bring Dynamic Complexity closer to Dynamic Algorithms through the study of constant-time parallel dynamic algorithms. It also takes a look at constant-time parallel “static” algorithms.

Automata

Friday January 12, 2024, 2PM, Salle 3052

**Jon Rawski** *Learning (Sub)regular string functions*

#### Year 2023

Automata

Friday December 15, 2023, 2PM, Salle 3052

**Chana Weil-Kennedy** (IMDEA) *Parameterized Analysis of Concurrent Systems*

Automata

Friday December 8, 2023, 2PM, Salle 3052

**Anantha Padmanabha** *Consistent Query Answering under Primary Keys*

The conjecture is open in general and has been open for more than two decades. In this talk we will introduce two new algorithms that we have devised, one based on fix-point computation and the other based on bipartite matching. We will also see how these algorithms can be used to prove the dichotomy for the cases that were previously open.

These results were obtained in collaboration with Diego Figueira, Luc Segoufin and Cristina Sirangelo and combine the results that were presented at ICDT 2023 and what will be presented at PODS 2024.

Automata

Friday November 24, 2023, 2PM, Salle 3052

**Mikołaj Bojańczyk** *A structural characterisation of MSO transductions on bounded treewidth*

Automata

Friday November 17, 2023, 2PM, Salle 3052

**Emily Clement** *Robustness of timed automata*

Automata

Friday November 10, 2023, 2PM, Salle 3052

**Sam Van Gool** *Modal unification and de Bruijn graph homomorphisms*

Instantiating this construction to the neXt-fragment of Linear Temporal Logic (LTL-X), the unifiability problem for LTL-X becomes equivalent to the following purely graph-theoretic problem. Given a finite edge-colored graph G, decide whether or not G is the homomorphic image, also called “folding”, of a de Bruijn graph B_n for some n. (Here, the de Bruijn graph B_n is the graph underlying the minimal DFA that recognizes the languages A* a A^(n-1) for a in the alphabet A.) We show that this problem is decidable, by giving a complete characterization of the graphs that are foldings of de Bruijn graphs. This then allows us to conclude in particular that the unifiability problem for LTL-X is decidable.

We also apply our method to prove PSPACE-completeness of unifiability for a logic called Alt1, and we formulate a problem about hypergraphs which is equivalent to the unifiability problem for normal modal logic K. The decidability of the latter problem remains open.

This is joint work with Johannes Marti and Michelle Sweering; a preliminary version of part of the work was presented at the workshop UNIF'23 and we are currently working on the full version.

Automata

Friday November 3, 2023, 2PM, Salle 3052 (online)

**Krzysztof Ziemiański** (University of Warsaw) *Presheaf automata*

Automata

Friday October 20, 2023, 2PM, Salle 3052

**Automata Team** *Welcome session*

Automata

Wednesday October 18, 2023, 3PM, Salle 3052

**Joël Ouaknine** *What’s Decidable about Discrete Linear Dynamical Systems?*

Perhaps surprisingly, many decision problems concerning LDS (such as reachability of a given hyperplane, known as the Skolem Problem) have been open for many decades. In this talk, we explore the landscape of such problems, focussing in particular on model-checking questions.

Automata

Friday October 13, 2023, 2PM, Salle 3052

**Antonio Casares** (LaBRI) *A characterization of half-positionality for omega-regular languages*

Automata

Friday October 6, 2023, 2PM, Salle 3052

**Christian Choffrut** *Synchronous orders on the set of integers*

The characterization of linear synchronous orderings on the integers is mentioned in a paper of Liu and Minnes (2009), which refers to a paper of Khoussainov and Rubin (2001) where it is implicit and is obtained as a general result on unary relations (not necessarily orderings). In my talk I will also comment on these results and propose some possible (hopefully genuinely novel!) extensions.

Automata

Friday September 29, 2023, 2PM, Salle 3052

**Alexander Rabinovich** (Tel-Aviv University) *The Church Synthesis Problem Over Continuous Time*

Automata

Friday September 22, 2023, 2PM, Salle 3052

**Victor Marsault** (LIGM, CNRS) *Introduction to querying with RPQs: semantics in theory and practice*

Most query languages for property graphs are based on the theoretical formalism of Regular Path Queries (RPQs). The query is a regular expression that searches for walks in the graph labeled by words that match the expression.

There is no real consensus on what the correct answer to an RPQ is, or even what the nature of the answer should be. Different real-world languages use different semantics, and these fundamentally differ from the traditional semantics of RPQs used in theory. The core of this talk is about all these differences and their implications.

Automata

Friday September 8, 2023, 2PM, Salle de séminaire 147 (Olympe de Gouges)

**Alfredo Costa** (University of Coimbra, CMUC) *A profinite approach to complete bifix decodings of recurrent languages.*

Automata

Friday June 30, 2023, 2PM, Salle 146 Olympe de Gouges

**Eugène Asarin** (IRIF) *Bandwidth of Timed Automata: 3 classes*

In this paper, we identify three classes of timed automata according to the asymptotics of the bandwidth of their languages with respect to this precision ε: automata are either meager, with an O(1) bandwidth, normal, with a Θ(log (1/ε)) bandwidth, or obese, with Θ(1/ε) bandwidth. We define two structural criteria and prove that they partition timed automata into these 3 classes of bandwidth, implying that there are no intermediate asymptotic classes.

Both criteria are formulated using morphisms from paths of the timed automaton to some finite monoids extending Puri's orbit graphs, and the proofs are based on Simon's factorization forest theorem.

Joint work with A.Degorre, C.Dima, B. Jacobo Inclán

Automata

Friday June 23, 2023, 2PM, Salle 147 Olympe de Gouges

**Hugues Déprés** *The hardness of computing twin-width*

While the twin-width of several graph classes is well known, we will show that determining whether an n-vertex graph has twin-width at most 4 is NP-complete, and that it requires time 2^Ω(n/log n) under ETH.

This talk is based on joint work with Pierre Bergé and Édouard Bonnet.

Automata

Friday June 16, 2023, 2PM, Salle 147 Olympe de Gouges

**Stefan Kiefer** *On the state complexity of complementing unambiguous finite automata*

Automata

Friday June 9, 2023, 2PM, Salle 146 Olympe de Gouges

**Daniel Smertnig** *Deciding Sequential? and Unambiguous? for weighted automata over fields*

This talk is on joint work with J. Bell.

Automata

Friday June 2, 2023, 2PM, Salle 146 Olympe de Gouges

**Alexandra Rogova** ([DB]) *GPC: A Pattern Calculus for Property Graphs*

Automata

Friday May 26, 2023, 2PM, Salle 146 Olympe de Gouges

**C Aiswarya** *On the edit distance between transducers*

This is a joint work with Amaldev Manuel (IIT Goa) and Saina Sunny (IIT Goa).

Automata

Friday May 19, 2023, 2PM, Salle 3052

**Andrea Cali** *Non encore annoncé.*

Automata

Friday May 12, 2023, 2PM, Salle de séminaire 147 (Olympe de Gouges)

**Maxime Buron** *Rewriting the infinite chase*

Automata

Friday May 5, 2023, 2PM, Salle de séminaire 147 (Olympe de Gouges)

**Mirna Dzamonja** *Capturing convergence through changing the logic*

Automata

Friday April 21, 2023, 2PM, Salle 3052

**Herman Goulet-Ouellet** *What lies inside free profinite monoids*

In the first part of the talk, I will present basic concepts related with free profinite monoids and survey some key results, including the connections with regular languages and with symbolic dynamics. In the second part, I will explain how free profinite monoids can be used in a practical way to study dynamical systems defined by primitive substitutions. More precisely, I will explain how Almeida's representation produces easy-to-compute numerical invariants for these systems.

Automata

Friday April 7, 2023, 2PM, Salle 3052

**Mahsa Shirmohammadi** *Stochastic games and strategy complexity*

Automata

Friday March 31, 2023, 2PM, Salle 3052

**Leon Bohn** *Learning algorithms for ω-automata*

Automata

Friday March 24, 2023, 2PM, Salle 3052

**Quentin Manière** *Counting queries in ontology-based data access*

Automata

Friday March 17, 2023, 2PM, Salle 3052

**Florian Renkin** *Réductions efficaces de machines de Mealy*

Automata

Friday March 10, 2023, 2PM, Salle 3052

**Uri Abraham** *On states and invariants*

`` 1. x[i] := 1; 2. y[i] := x[(i − 1) mod N] ``

Here N is the number of processes, and p0, . . . , pN−1 are the processes. Process pi writes on register x[i] and all other processes can read it. The registers are serial. The invariant should be good enough to prove the following statement:

After every process has stopped executing its simple protocol, at least one process pi has set y[i] = 1.

Try to find an invariant and prove this statement. This algorithm will serve to discuss the notion of invariants and to describe a method that can help in developing invariants for more sophisticated algorithms. We will also discuss the question ``what is a state'' (which is relevant to the notion of invariance of course).

Automata

Friday March 3, 2023, 2PM, Salle 3052 (ZOOM)

**Svetlana Puzynina** *Abelian subshifts generated by infinite words*

Automata

Friday February 24, 2023, 2PM, Salle 3052

**Ismaël Jecker** *Parikh Automata over Infinite Words (ON ZOOM)*

ZOOM

Automata

Friday February 17, 2023, 2PM, Salle 3052

**Yann Ramuzat** *The Semiring-Based Provenance Framework for Graph Databases*

This is joint work with Silviu Maniu and Pierre Senellart.

Automata

Friday February 10, 2023, 2PM, Salle 3052

**Uli Fahrenberg** *An invitation to higher-dimensional automata theory*

Automata

Friday February 3, 2023, 2PM, Salle 3052

**Florent Koechlin** *Two criteria to prove the inherent ambiguity of bounded context-free languages*

Although they made it possible to prove the inherent ambiguity of several languages, as for example the language L = a^n b^m c^p with n=m or m=p, iteration techniques are still very laborious to implement, are very specific to the studied language, and seem even sometimes unadapted. For instance, the relative simplicity of the proof of inherent ambiguity of L completely collapses by replacing the constraint "n=m or m=p" by "n≠m or m≠p". In this talk, I will present two useful criteria based on generating series to prove easily the inherent ambiguity of some bounded context-free languages. These languages, which have a rational generating series, resisted both the classical iteration techniques developed in the 1960’s and the analytic methods introduced by Philippe Flajolet in 1987.

Automata

Friday January 6, 2023, 2PM, Salle 3052

**Christian Choffrut** *Le monoide grammique / The grammic monoid*

La relation qui met ensemble deux mots qui ont la même action sur l’ensemble des lignes est une congruence plus grossière que le congruence plaxique (celle des tableaux de Young) et elle est décidable. Je considère le cas d’un alphabet à 3 lettres pour lequel elle est obtenue en ajoutant aux règles de Knuth une seule nouvelle règle très simple. Je m’aventurerai à proposer un conjecture sur les alphabets à plus de 3 lettres et en passant je parlerai des (très jolis et peut-être utiles) travaux de Okninski et al. sur les algèbres de monoids plaxiques.

—

Schensted showed how to insert a new element in a Young tableau. It consists of inserting this element in the bottom row (row= nondecreasing sequence of elements) and iterating the process further up in case an element of the bottom row is bumped. I am interested in the action of the free monoid which assigns to a row, the row obtainded by Schensted insertion, but ignoring the possible bumped element. Christophe Reutenauer considered in his May seminar the action on the set of columns. His (stylic) monoid is finite (there exist finitely many columns for a fixed alphabet) while mine, the grammic monoid, is infinite.

The relation between two words having the same action on the set of rows is a congruence which is coarser than the plactic congruence (that defining the Young tableaux) and decidable. I consider the case of a 3 letter alphabet for which the congreunce is generated by the Knuth rules plus a unique simple rule. I will risk a conjecture for alphabets of more than 3 letters and say a few words on the (very nice and possibly related) works of Okninski and al. on the algebras of the plactic monoids.

#### Year 2022

Automata

Friday December 16, 2022, 2PM, Salle 3052

**Carl-Fredrik Nyberg Brodda** *Language-theoretic methods in combinatorial semigroup theory*

Automata

Friday December 9, 2022, 2PM, Salle 3052

**Sarah Winter** *A Regular and Complete Notion of Delay for Streaming String Transducers*

We show that our notion is regular: we design a finite automaton that can check whether the delay between any two SSTs executions is smaller than some given bound. As a consequence, our notion enjoys good decidability properties: in particular, while equivalence between non-deterministic SSTs is undecidable, we show that equivalence up to fixed delay is decidable. Moreover, we show that our notion has good completeness properties: we prove that two SSTs are equivalent if and only if they are equivalent up to some (computable) bounded delay.

Together with the regularity of our delay notion, it provides an alternative proof that SSTs equivalence is decidable. Finally, the definition of our delay notion is machine-independent, as it only depends on the origin semantics of SSTs. As a corollary, the completeness result also holds for equivalent machine models such as deterministic two-way transducers, or MSO transducers.

This is joint work with Emmanuel Filiot, Ismaël Jecker, and Christof Löding.

Automata

Friday December 2, 2022, 2PM, Salle 3052

**Léo Exibard** *Runtime monitoring for Hennessy-Milner logic with recursion over systems with data*

I then examine what kind of properties can be monitored at runtime, depending on the monitor model. A key aspect is that the logic has close links with register automata with non-deterministic reassignment, which yields a monitor synthesis algorithm, and allows to derive impossibility results. In particular, contrary to the regular case, restricting to deterministic monitors strictly reduces the set of monitorable properties.

This is joint work with the MoVeMnt team (Reykjavik University): Luca Aceto, Antonis Achilleos, Duncan Paul Attard, Adrian Francalanza, Karoliina Lehtinen.

Automata

Friday November 25, 2022, 2PM, Salle 3052

**Moses Ganardi** *Expressiveness of Subword Constraints*

This presentation is based on joint work with Pascal Baumann, Ramanathan S. Thinniyam, and Georg Zetzsche (MPI-SWS), which has been presented at STACS 2022 .

Automata

Friday November 18, 2022, 2PM, Salle 3052

**Anantha Padmanabha** *Databases and Predicate Modal Logics: A tale of two cities*

In the first case we will look at the consistent query answering problem, where a given database violates some specified constraints. We will see why such databases are interesting and how one would evaluate queries in these cases. We will discuss new algorithms that we have introduced and our attempts to solve an open conjecture in the field. This is work in collaboration with Diego Figueira, Luc Segoufin and Cristina Sirangelo. In the second case we will discuss First Order Modal Logic. These logics are notoriously undecidable (for instance restrictions to unary predicates, guarded fragment, two variable fragment are all undecidable). We will discuss some decidable fragments that we have identified. This is a work in collaboration with R. Ramanujam, Yanjing Wang and Mo Liu. Finally we will discuss some possible directions to bring these two seemingly unrelated topics together.

Automata

Friday October 28, 2022, 2PM, Salle 3052

**Pierre Vandenhove** *Characterizing Omega-Regularity through Finite-Memory Determinacy of Games on Infinite Graphs*

These results are based on joint work with Patricia Bouyer and Mickael Randour and have been published in the proceedings of STACS 2022.

Automata

Friday October 14, 2022, 2PM, Salle 3052

**Howard Straubing** (Boston College) *A Problem about Automata and Logic*

Automata

Friday October 7, 2022, 2PM, Salle 3052

**Jacques Sakarovitch** (IRIF, CNRS and LTCI, Télécom Paris, IPP) *The Net Automaton of a Rational Expression*

This construction has two supplementary outcomes.

The first one is the reinterpretation in terms of automata of a data structure introduced by Champarnaud, Laugerotte, Ouardi, and Ziadi for the efficient computation of the position (or Glushkov) automaton of a rational expression, and which consists in a duplicated syntactic tree of the expression decorated with some additional links.

The second one supposes that this construction devised for the case of weighted expressions is brought back to the domain of Boolean expressions. It allows then to describe, in terms of automata, the construction of the Star Normal Form of an expression that was defined by Brüggemann-Klein, and also with the purpose of an efficient computation of the position automaton.

This is joint work with Sylvain Lombardy (Labri, U. Bordeaux)

Automata

Friday September 16, 2022, 2:30PM, Salle 3052

**Alexander Rabinovich** *On Uniformization in the Full Binary Tree*

```
in the full binary tree. In other words, there is no MSO definable choice function in the full binary tree.
The cross-section of a relation R(X,Y) at D is the set of all E such that R(D,E) holds. Hence, a function that uniformizes R chooses one element from every non-empty cross-section.
The relation ``Y is a one element subset of X
```

has finite and countable cross-sections.
We prove that in the full binary tree the following theorems hold:

Theorem (Finite cross-section) If every cross-section of an MSO definable relation is finite, then it has an MSO definable uniformizer.

Theorem (Uncountable cross-section) There is an MSO definable relation R such that every MSO definable relation included in R and with the same domain as R has an uncountable cross-section.

Automata

Friday June 24, 2022, 2:30PM, Salle 3052

**Nikhil Balaji** *Identity Testing for Radical Expressions*

This work is in collaboration with Klara Nosan, Mahsa Shirmohammadi and James Worrell. The results are going to be presented at LICS 2022, and the full-version of the paper can be found here: https://arxiv.org/abs/2202.07961.

Automata

Friday May 20, 2022, 2:30PM, Salle 3052

**Aliaume Lopez** *Locality and Preservation Theorems*

The robustness of this proof scheme is explained by its behavior over arbitrary structures, over which we show that existential local sentences match exactly the first-order sentences preserved under local elementary embeddings. Furthermore, we prove that existential local sentences are exactly those that can be written using a positive variant of the Gaifman normal form.

Automata

Friday May 13, 2022, 2:30PM, Salle 3052

**Christophe Reutenauer** (UQAM, Canada) *Le monoïde stylique (seminaire joint Combinatoire et Automates)*

Automata

Friday April 22, 2022, 2:30PM, Salle 3058 ONLINE

**Wojtek Przybyszewski** *Definability of neighborhoods in graphs of bounded twin-width and its consequences.*

Automata

Friday April 15, 2022, 2:30PM, Salle 3052

**Nguyễn Lê Thành Dũng** *Polyregular functions: some recent developments*

In this talk, after recalling this context, I will present some subsequent developments in which I have been involved: * the subclass of comparison-free polyregular (or “polyblind”) functions, definable through a natural restriction of pebble transducers, which Pierre Pradic and I actually discovered while studying a linear λ-calculus; * some results that either relate the growth rate of a polyregular function (comparison-free or not) to the “resources” needed to compute it (number of pebbles or MSO-interpretation dimension), or show that there is no such relationship.

This last item is joint work with Mikołaj Bojańczyk, Gaëtan Douéneau-Tabot, Sandra Kiefer and Pierre Pradic, and builds upon a previous work by Nathan Lhote [2020].

Automata

Friday April 1, 2022, 1:45PM, Salle 3052

**Pierre Ohlmann** *Characterising half-positionality in infinite duration games over infinite arenas*

This is the first known characterization in this setting. I will explain the result, quickly survey existing related work, show how it is proved and try to argue why it is interesting.

Note the unusual time: 13h45.

Automata

Friday March 25, 2022, 2:30PM, Salle 3058

**Nathan Grosshans** *Visibly pushdown languages in AC^0*

While many questions are still open, one of the greatest successes of this research endeavour has been the characterisation of the regular languages in AC^0, the subclass of NC^1 corresponding to Boolean circuits of polynomial length, constant depth and with gates of unbounded fan-in. This characterisation takes the form of a triple languages-algebra-logic correspondence: a regular language is in AC^0 if and only if its syntactic morphism is quasi-aperiodic if and only if it is definable in first-order logic over words with linear order and modular predicates.

It is natural to try to extend such results to classes of formal languages greater than the class of regular languages. A well studied and robust such class is given by visibly pushdown languages (VPLs): languages recognised by pushdown automata where the stack-height-behaviour only depends on the letters read from the input. Over the previous decade, a series of works concentrated on the fine complexity of VPLs, with several achievements: one of those was a characterisation of the class of visibly counter languages (basically VPLs recognised by visibly pushdown automata with only one stack symbol) in AC^0 by Krebs, Lange and Ludwig. However, the characterisation of the VPLs in AC^0 still remains open.

In this talk, I shall present a conjectural characterisation of the VPLs in AC^0 obtained with Stefan Göller at the Universität Kassel. It is inspired by the conjectural characterisation given by Ludwig in his Ph.D. thesis as a generalisation of the characterisation for visibly counter languages, but that is actually false. In fact, we give a more precise general conjectural characterisation that builds upon recognisability by morphisms into Ext-algebras, an extension of recognisability by monoid-morphisms proposed by Czarnetzki, Krebs and Lange to suit the case of VPLs. This characterisation classifies the VPLs into three categories according to precise conditions on the Ext-algebra-morphisms that recognise them: - those that are TC^0-hard; - those that are in AC^0; - those that correspond to a well-identified class of “intermediate languages” that we believe to be neither in AC^0 nor TC^0-hard.

Automata

Friday March 18, 2022, 2:30PM, Salle 3052

**Edwin Hamel-De Le Court** *Two-player Boundedness Counter Games*

Automata

Friday March 11, 2022, 2:30PM, Salle 3052

**Arthur Jaquard** *A Complexity Approach to Tree Algebras: the Polynomial Case*

Our main result establishes an equivalence between the languages recognised by algebras of polynomial complexity and the languages that can be described by nominal word automata that parse linearisation of the trees. On the way, we show that for such algebras, having polynomial complexity corresponds to having uniformly boundedly many orbits under permutation of the variables, or having a notion of bounded support (in a sense similar to the one in nominal sets).

We also show that being recognisable by an algebra of polynomial complexity is a decidable property for a regualr language of trees.

This is joint work with Thomas Colcombet.

Automata

Friday February 18, 2022, 2:30PM, Salle 3052

**Klara Nosan** *On computing the algebraic closure of matrix groups*

In this talk we introduce the problem of computing the Zariski closure and describe an existing algorithm, due to Derksen, Jeandel and Koiran, before moving to our main result, which is to obtain an upper bound on the degree of the polynomials that define the Zariski closure. Having an a priori bound allows us to give a simple algorithm for the problem, via linear algebra, similar to Karr's algorithm for obtaining affine invariants for affine programs.

Automata

Friday February 11, 2022, 2:30PM, Salle 3052

**Soumyajit Paul** *Complexity of solving extensive form games with imperfect information*

Automata

Friday February 4, 2022, 2:30PM, Salle 3052 (Online)

**Bartek Klin** *Orbit-finite-dimensional vector spaces, with applications to weighted register automata*

Applications of this include a decision procedure for equivalence of weighted register automata, which are the common generalization of weighted automata and register automata for infinite alphabets. The algorithm runs in exponential time, and in polynomial time for a fixed number of registers. As a special case, we can decide, with the same complexity, language equivalence for unambiguous register automata.

(Joint work with Mikołaj Bojańczyk and Joshua Moerman.)

Automata

Friday January 21, 2022, 2:30PM, Salle 3052

**Victor Marsault** *Demonstration of Awali 2.1, a library for weighted automata and transducers.*

Awali may be accessed in C++ (awalidyn, or directly using templates) or in Python (awalipy). Awali can also be used interactively from its command-line interface (Cora) or using awalipy together with Jupyter, a top-level Python interpreter.

Awali may be downloaded from http://vaucanson-project.org/Awali/2.1/ and I'll be happy to address possible installation issues after the presentation.

Automata

Wednesday January 5, 2022, 4:15PM, Salle 3052

**Léo Exibard** *Extending Reactive Synthesis to Infinite Data Domains through Machines with Registers*

The aim of this talk is to investigate the case of infinite alphabets. Correspondingly, executions are modelled as data omega-words. In this context, we study specifications and implementations respectively given as automata and transducers extended with a finite set of registers, used to store and compare data values. We consider different instances, depending on whether the specification is nondeterministic, universal (a.k.a. co-nondeterministic) or deterministic: contrary to the finite-alphabet case, those classes are expressively distinct.

When the number of registers of the target implementation is unbounded, the synthesis problem is undecidable, while decidability is recovered in the deterministic case. In the bounded setting, undecidability still holds for non-deterministic specifications, but decidability is recovered for universal ones.

The study was initially conducted over data domains with the equality predicate only, but the techniques can be lifted to the dense order (Q,<) and so-called oligomorphic data domains, over which register automata behave in an omega-regular way. A further exploration of the problem allows to extend the results to the discrete order (N,<), where the behaviours can be regularly approximated. Finally, decidability can be transferred to the case of words with the prefix relation (A^*,<) through a notion of reducibility between domains.

Note the unusual day and time!

#### Year 2021

Automata

Friday December 10, 2021, 2:30PM, Salle 3052

**Marie Fortin** (University of Liverpool) *How undecidable are HyperLTL and HyperCTL*?*

Automata

Friday December 3, 2021, 2:30PM, Salle 3052 (Online)

**Jan Otop** (University of Wrocław) *Active learning automata with syntactic queries*

First, I will discuss why extending L^*, which asks only semantic queries, to infinite-words languages is difficult. Next, I will present an alternative approach; instead of learning some automaton for a hidden language, we assume that there is a hidden automaton and the algorithm is supposed to learn an equivalent automaton. In this approach, the learning algorithm is allowed to ask standard semantic queries (membership and equivalence) and loop-index queries regarding the structure of the hidden automaton. These queries do not reveal the full structure of the automaton and hence do not trivialize the learning task.

In the extended framework, there are polynomial-time learning algorithms for various types of infinite-word automata: deterministic Buechi automata, LimSup-automata, deterministic parity automata and limit-average automata.

Finally, the idea to incorporate syntactic queries can be adapted to the pushdown framework; I will briefly discuss the learning algorithm for deterministic visibly pushdown automata.

Automata

Friday November 26, 2021, 2:30PM, Salle 3052

**Stéphane Le Roux** *Extensive-form games with incentive stage-bidding*

The notion of subgame perfect equilibrium (SPE) is naturally extended to these bidding games, and they always always exist like in the classical games. They also enjoy new properties: - If the game tree is binary-branching, payoff-sum-maximizing SPE always exist. - If the game involves only two players, all SPE are payoff-sum-maximizing with the same payoff-tuple, which is called the bidding value of the game. - This value is computable, whereas SPE payoff-tuples are not even continuous in classical games.

This is joint work with Valentin Goranko

Automata

Friday October 29, 2021, 2:30PM, Salle 3052

**Nofar Carmeli** (ENS) *The Fine-Grained Complexity of Answering Database Queries*

Automata

Friday October 22, 2021, 2:30PM, Salle 3052

**Dietmar Berwanger** (LSV) *Telling Everything. Information Quotients in Games with Communication*

The talk is based on joint work (in progress) with Laurent Doyen; a part of the material is presented in [D. Berwanger, L. Doyen (2019): Observation and distinction in infinite games, https://arxiv.org/abs/1809.05978]

Automata

Friday October 15, 2021, 2:30PM, Salle 3052 (Online) https://u-paris.zoom.us/j/87690991231?pwd=QjN4QUJKdExOMXp3a1MrQTNNL1RuZz09

**Amaldev Manuel** (Indian Institute of Technology Goa) *Algebraically characterising first-order logic with neighbour*

Automata

Friday October 8, 2021, 2:30PM, Salle 3052

**Thomas Colcombet** *FO-separation of regular languages over words of ordinal length*

Automata

Friday October 1, 2021, 2:30PM, Salle 3052

**Jacques Sakarovitch** (IRIF, CNRS & Télécom Paris) *Derived terms without derivation*

Automata

Friday July 2, 2021, 2:30PM, Hybride : Salle 3052 et BBB (https://bbb-front.math.univ-paris-diderot.fr/recherche/ama-bgy-hx5-3rl)

**Antonio Casares** *Optimal Transformations of Games and Automata using Muller Conditions*

In this talk, I will present a construction that takes as input a Muller automaton and transforms it into a parity automaton in an optimal way. More precisely, the resulting parity automaton has minimal size and uses a minimal number of priorities among those automata that admit a locally bijective morphism to the original Muller automaton. This transformation and the optimality result can also be applied to games and other types of transition systems.

We show two applications: an improvement on the determinisation of Büchi automata into deterministic parity automata and characterisations of automata that admit parity, Rabin or Streett conditions in top of them.

This is joint work with Thomas Colcombet and Nathanaël Fijalkow, and it will appear at ICALP 2021.

Automata

Friday June 25, 2021, 2:30PM, https://bbb-front.math.univ-paris-diderot.fr/recherche/ama-bgy-hx5-3rl

**Amina Doumane** *Tree-to-tree functions*

Automata

Friday June 18, 2021, 2:30PM, https://bbb-front.math.univ-paris-diderot.fr/recherche/ama-bgy-hx5-3rl

**Charles Paperman** *Dynamic Membership for regular language*

Automata

Friday June 11, 2021, 2:30PM, Salle 3052

**Jan Dreier** *Lacon- and Shrub-Decompositions: Characterizing First-Order Transductions of Bounded Expansion Classes*

The leading question of this talk is: “How can we generalize the beautiful existing algorithmic results of sparse graphs to dense graphs?” We start with an overview over sparse and dense graph classes and then introduce lacon- and shrub-decompositions. We show that dense graph classes can be exactly characterized by having a sparse lacon- or shrub-decoposition. If one could efficiently compute such a decomposition then one could solve every problem definable in first-order logic in linear time on these classes.

Automata

Friday June 4, 2021, 2:30PM, https://bbb-front.math.univ-paris-diderot.fr/recherche/ama-bgy-hx5-3rl

**Deacon Linkhorn** *The pseudofinite monadic second order theory of linear order (and a connection to profinite algebra).*

I will present an explicit axiomatisation of this shared theory, and characterise the non-standard completions (i.e. those admitting infinite models) in terms of residue functions. I will then talk about a connection with profinite monoids using extended Stone duality. In particular I will discuss a special case of a theorem due to Gehrke, Grigorieff, and Pin saying that the free profinite monoid on one generator is the extended Stone dual of the Boolean algebra of regular languages over a singleton alphabet (together with the binary operation of concatenation).

Automata

Friday May 28, 2021, 2:30PM, https://bbb-front.math.univ-paris-diderot.fr/recherche/ama-bgy-hx5-3rl

**Jonathan Tanner** *On the Size of Finite Rational Matrix Semigroups*

Automata

Friday May 21, 2021, 2:30PM, https://u-paris.zoom.us/rec/share/CBacDMMIJL2XuVNP7bx9V23Y1lpOsU0Dql1SwglYizke_yn6MOTtQEwXgFOVqZs.4RJmUCKgDVogKWAj Passcode: k$o$L92E6J

**Enrico Formenti** *On the decidability of dynamical properties of addtive cellular automata*

Automata

Friday May 7, 2021, 2:30PM, https://bbb-front.math.univ-paris-diderot.fr/recherche/ama-bgy-hx5-3rl

**Sadegh Soudjani** *On Decidability of Time-Bounded Reachability in CTMDPs*

Automata

Friday April 30, 2021, 2:30PM, https://bbb-front.math.univ-paris-diderot.fr/recherche/ama-bgy-hx5-3rl

**Denis Kuperberg** (CNRS, ENS de Lyon) *Positive first-order logic on words*

Automata

Friday April 23, 2021, 2:30PM, https://bbb-front.math.univ-paris-diderot.fr/recherche/ama-bgy-hx5-3rl

**Misha Vyalyi** *Re-pairing brackets and commutative automata.*

Automata

Friday April 16, 2021, 2:30PM, https://bbb-front.math.univ-paris-diderot.fr/recherche/ama-bgy-hx5-3rl

**Arthur Jaquard** *A Complexity Approach to Tree Algebras: the Bounded Case*

Tree algebras in many of their forms, such as clones, hyperclones, operads, etc, as well as other kind of algebras, are infinitely sorted: the carrier is a multi sorted set indexed by a parameter that can be interpreted as the number of variables or hole types. Finite such algebras - meaning when all sorts are finite - can be classified depending on the asymptotic size of the carrier sets as function of the parameter, that we call the complexity of the algebra. This naturally defines the notions of algebras of bounded, linear, polynomial, exponential or doubly exponential complexity…

Our main result precisely characterizes the tree algebras of bounded complexity based on the languages that they recognize as Boolean closures of simple languages. Along the way, we prove that such algebras that are syntactic are exactly those in which, as soon as there are sufficiently many variables, the elements are invariant under permutation of the variables.

Automata

Friday April 2, 2021, 2:30PM, https://bbb-front.math.univ-paris-diderot.fr/recherche/ama-bgy-hx5-3rl

**Amaury Pouly** (IRIF) *On the Decidability of Reachability in Continuous Time Linear Time-Invariant Systems*

Automata

Friday March 19, 2021, 2:30PM, http://perso.ens-lyon.fr/pierre.pradic/slides/2021-03-irif.pdf

**Pierre Pradic** *Star-free languages, first-order transductions and the non-commutative λ-calculus*

This work is part of an exploration of the expressiveness of the simply-typed λ-calculus (STLC) and related substructural variants (linear, affine, planar) using Church encodings of datatypes. More specifically, we are interested in the connection with automata theory for string transductions and languages.

I will first introduce the setting and motivate the problems using Hillebrand and Kanellakis' result stating that the classes of STLC-definable and regular languages coincide. I will then focus on a result stating that star-free languages correspond exactly to those obtained in a non-commutative refinement of STLC based on linear logic. I will sketch an alternative proof of this result using a semantic evaluation argument and discuss related work-in-progress concerning characterizations in the non-commutative λ-calculus of first-order regular string transductions using planar reversible 2DFTs and tree-walking automata.

(the results I will present are based on https://hal.archives-ouvertes.fr/hal-02476219 and http://nguyentito.eu/2021-01-links.pdf)

Automata

Friday March 12, 2021, 2:30PM, https://u-paris.zoom.us/rec/share/CF6tuTHp2Y6P2vtynWBE_dDKsv93CiJOIBtvg3ujsYCsqvPpjMS6DCY3Wf_BzmUx.GtIj9JDQznwAW_6w Passcode: F504d+s8@?

**Nathanaël Fijalkow** *Search algorithms for Probabilistic Context-Free Grammars*

Joint (ongoing) work with Pierre Ohlmann and Guillaume Lagarde.

Automata

Friday March 5, 2021, 2:30PM, Online at https://bbb-front.math.univ-paris-diderot.fr/recherche/ama-bgy-hx5-3rl

**Manfred Madritsch** (Université de Lorraine, CNRS) *Three views on numeration systems*

The first part deals with signed numeration systems. In these systems, we add digits to the alphabet such as the digit $-1$ in the binary system. Under certain conditions, on consecutive digits, we obtain unique representations. This is related to the concept of abstract numeration systems. We will study the shift and odometer from the point of view of dynamical systems.

Digital restrictions also play an important role in another numeration system: the Zeckendorf expansion. This is an example of the larger class of numeration systems based on linear recurrent sequences, which we discuss in the second part. A way to analyse a numeration system is to examine functions operating on the digital representation. The most famous of these functions is the sum-of-digits function and we investigate it from an analytic point of view.

In the expansion of a randomly chosen real, we expect each block of digits to occur with the same frequency. This leads to the concept of normal numbers and the related notion of uniformly distributed sequences. In the last part, we adopt a probabilistic point of view and construct normal numbers and uniformly distributed sequences related to numeration systems.

Automata

Friday February 19, 2021, 2:30PM, https://bbb-front.math.univ-paris-diderot.fr/recherche/ama-bgy-hx5-3rl

**Liat Peterfreund** *2-Valued Logic for SQL on Incomplete Information*

In a joint work with Leonid Libkin, we show that, contrary to the widely held view, SQL could have been designed based on the standard two-valued logic, without any loss of expressiveness and without giving up nulls. We show that conflating unknown, resulting from conditions referring to nulls, with false leads to an equally expressive version of SQL. Queries written under the two-valued semantics can be efficiently translated into the standard SQL and thus executed on any existing RDBMS. Our results cover the core of the SQL 1999 Standard, including SELECT-FROM-WHERE-GROUP BY-HAVING queries extended with subqueries and IN/EXISTS/ANY/ALL conditions, and recursive queries. In addition, we show that no other many-valued logic for treating nulls could have possibly led to a more expressive language.

Automata

Friday February 12, 2021, 2:30PM, https://bbb-front.math.univ-paris-diderot.fr/recherche/ama-bgy-hx5-3rl

**Julien Grange** *Successor-Invariant First-Order Logic on Classes of Bounded Degree*

Automata

Friday January 29, 2021, 2:30PM, Salle 3052

**Stefan Göller** (University of Kassel) *Bisimulation Finiteness of Pushdown Systems Is Elementary*

Automata

Friday January 22, 2021, 2:30PM, Online

**Daniela Petrisan** *Learning automata and transducers: a categorical approach*

This is joint work with Thomas Colcombet and Riccardo Stabile.

Automata

Friday January 15, 2021, 2:30PM, Salle 3052

**Ayrat Khalimov** *Church Synthesis on Register Automata over Infinite Ordered Domains*

(This is the joint work by Léo Exibard, Emmanuel Filiot, Ayrat Khalimov)

#### Year 2020

Automata

Friday December 18, 2020, 2:30PM, Salle 3052

**Damien Pous** *Cyclic proofs, System T and the power of contraction*

Automata

Friday December 11, 2020, 2:30PM, Salle 3052

**Joël Ouaknine** (MPI-SWS) *Holonomic Techniques, Periods, and Decision Problems*

Parts of this talk will be based on the paper “On Positivity and Minimality for Second-Order Holonomic Sequences”, https://arxiv.org/abs/2007.12282 .

Automata

Friday December 4, 2020, 2:30PM, Salle 3052

**Georg Zetzsche** *Rational subsets of Baumslag-Solitar groups*

This is joint work with Michaël Cadilhac and Dmitry Chistikov.

Automata

Friday November 27, 2020, 2:30PM, Salle 3052

**Nathan Lhote** (LaBRI) *Pebble Minimization of Polyregular Functions.*

Automata

Friday November 20, 2020, 2:30PM, Salle 3052

**Victor Lutfalla** (LIPN) *Substitution planar tilings with n-fold rotational symmetry*

Automata

Thursday November 12, 2020, 3:30PM, Salle 3052

**Guillermo Alberto Perez** (University of Antwerp) *Coverability in 1-VASS with Disequality Tests*

Unusual time!

Automata

Friday November 6, 2020, 2:30PM, Salle 3052

**Denis Kuperberg** (LIP, ENS Lyon, CNRS) *Recognizing Good-for-Games automata: the G2 conjecture*

Automata

Friday October 30, 2020, 2:30PM, Salle 3052

**Wojciech Czerwiński** (University of Warsaw) *Universality problem for unambiguous Vector Addition Systems with States*

(joint work with Diego Figueira and Piotr Hofman)

Automata

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

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*

Automata

Friday June 26, 2020, 2:30PM, Held online, on BigBlueButton

**Laure Daviaud** (City University of London) *About learning automata and weighted automata*

Automata

Friday June 19, 2020, 2:30PM, Online on BigBlueButton

**Sven Dziadek** *Weighted Logics and Weighted Simple Automata for Context-Free Languages of Infinite Words*

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.

Automata

Friday June 12, 2020, 2:30PM, Online (BigBlueButton)

**Kuize Zhang** *On detectability of finite automata and labeled Petri nets*

Automata

Friday June 5, 2020, 2:30PM, Online

**K. S. Thejaswini** (University of Warwick) *The Strahler Number of a Parity Game*

Automata

Friday May 29, 2020, 2:30PM, Online

**Liat Peterfreund** (IRIF) *Weight Annotation in Information Extraction*

Automata

Friday May 22, 2020, 2:30PM, Virtual seminar on BigBlueButton

**Mikołaj Bojańczyk** (MIMUW) *Single use transducers over infinite alphabets*

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.

Automata

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*

Automata

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*

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.

Automata

Friday April 17, 2020, 2:30PM, Online

**Jan Philipp Wächter** (Universität Stuttgart) *An Automaton Group with PSPACE-Complete Word Problem*

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.

Automata

Friday April 10, 2020, 2:30PM, Online

**Javier Esparza** *An Efficient Normalisation Procedure for Linear Temporal Logic*

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

Automata

Friday April 3, 2020, 2:30PM, Online

**Nathanaël Fijalkow** (LaBRI) *Assume Guarantee Synthesis for Prompt Linear Temporal Logic*

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

Automata

Friday March 27, 2020, 2:30PM, Salle 3052

**Edwin Hamel-De Le Court** *To be announced.*

Automata

Friday March 20, 2020, 2:30PM, Online

**Pierre Ohlmann** (IRIF) *Controlling a random population*

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

Automata

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*

Attention ! Horaire non habituel !

Automata

Friday March 6, 2020, 2:30PM, Salle 3052

**Henning Urbat** (FAU Erlangen-Nürnberg) *Automata Learning: An Algebraic Approach*

Automata

Friday February 28, 2020, 2:30PM, Salle 3052

**Marie Van Den Bogaard** (ULB) *Subgame Perfect Equilibria in Quantitative Reachability Games*

Automata

Tuesday February 25, 2020, 2PM, Salle 3052

**Georg Zetsche** (MPI SWS) *Extensions of $\omega$-Regular Languages*

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

Note the unusual time (14:00).

Automata

Friday February 21, 2020, 2:30PM, Salle 3052

**Luc Dartois** (LACL) *Reversible Transducers*

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

Automata

Friday February 7, 2020, 2:30PM, Salle 3052

**Youssouf Oualhadj** (LACL) *Life is random time is not: Markov decision processes with window objectives*

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.

Automata

Friday January 31, 2020, 2:30PM, Salle 3052

**Arnaud Sangnier** (IRIF) *Deciding the existence of cut-off in parameterized rendez-vous networks*

This is a joint work with Florian Horn.

Automata

Friday January 17, 2020, 2:30PM, Salle 3052

**Marc Zeitoun** (LABRI) *The star-free closure*

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.

Automata

Friday January 10, 2020, 2:30PM, Salle 3052

**Karoliina Lehtinen** *Parity Games – the quasi-polynomial era*

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

Automata

Tuesday December 17, 2019, 2:30PM, Salle 0010

**Achim Blumensath** (Masaryk University) *Regular Tree Algebras*

Noter la salle et l'horaire inhabituels.

Automata

Friday December 6, 2019, 2:30PM, Salle 3052

**Wesley Fussner** *Residuation: Origins and Open Problems*

Automata

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

**Dmitry Chistikov** (University of Warwick) *On the complexity of linear arithmetic theories over the integers*

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

Automata

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

**Alexis Bes** *Décider (R,+,<,1) dans (R,+,<,Z)*

Automata

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

**Patrick Totzke** *Timed Basic Parallel Processes*

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 https://arxiv.org/abs/1907.01240.

Automata

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

**Daniel Smertnig** (University of Waterloo) *Noncommutative rational Pólya series*

This is joint work with Jason Bell. arXiv:1906.07271

Automata

Monday October 28, 2019, 11AM, Salle 1007

**Pierre Ganty** (IMDEA Software Institute) *Deciding language inclusion problems using quasiorders*

Automata

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

**Luca Reggio** (Mathematical Institute, University of Bern) *Limits of finite structures: a duality theoretic perspective*

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.

Automata

Friday October 11, 2019, 2:30PM, Salle 1016

**Gaëtan Douéneau-Tabot** (IRIF) *Pebble transducers for modeling simple programs*

Automata

Friday July 5, 2019, 2:30PM, Salle 1001

**Mahsa Shirmohammadi** (CNRS) *Büchi Objectives in Countable MDPs*

Automata

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*

Automata

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

Automata

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

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

Automata

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

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

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

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

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

Automata

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

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

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

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

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

Automata

Tuesday March 26, 2019, 1PM, Salle 3052

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

Automata

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

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

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

Automata

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

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

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

Automata

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

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

Automata

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

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

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

Automata

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

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

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

Automata

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

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

Automata

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

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

Automata

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

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

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

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

Automata

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

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

#### Year 2018

Automata

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

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

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

Automata

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

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

Automata

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

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

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

Automata

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

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

Automata

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

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

Automata

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

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

Automata

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

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

This is joint work with Olivier Carton and Bruno Guillon.

Automata

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

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

Automata

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

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

Automata

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

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

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

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

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

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

Automata

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

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

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

Automata

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

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

Automata

Wednesday June 13, 2018, 3PM, Salle 3052

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

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

Date inhabituelle : Mercredi

Automata

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

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

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

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

Automata

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

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

Automata

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

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

Automata

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

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

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

Automata

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

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

Automata

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

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

Automata

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

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

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

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

Automata

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

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

Joint work with Jan Kretinsky and Salomon Sickert.

Séminaire de pôle

Automata

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

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

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

Automata

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

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

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

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

Automata

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

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

Automata

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

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

This is joint work with Serge Grigorieff and Theodore Slaman.

#### Year 2017

Automata

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

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

Automata

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

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

Automata

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

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

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

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

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

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

Automata

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

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

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

Automata

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

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

Automata

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

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

Automata

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

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

Automata

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

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

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

Automata

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

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

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

Automata

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

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

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

Automata

Friday July 7, 2017, 2PM, 0010

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

Automata

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

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

Automata

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

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

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

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

Automata

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

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

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

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

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

Automata

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

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

Automata

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

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

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

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

(No prior knowledge on set theory is assumed.)

Automata

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

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

Automata

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

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

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

Automata

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

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

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

Automata

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

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

Automata

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

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

Automata

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

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

Automata

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

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

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

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

Automata

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

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

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

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

Automata

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

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

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

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

Automata

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

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

Automata

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

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

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

Automata

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

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

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

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

Automata

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

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

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

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

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

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

–––––

**French version:**

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

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

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

Automata

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

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

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

#### Year 2016

Automata

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

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

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

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

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

Automata

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

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

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

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

Automata

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

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

http://www.lsv.ens-cachan.fr/~bollig/

Automata

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

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

Automata

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

**Lia Infinis** *Workshop*

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

Automata

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

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

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

Automata

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

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

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

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

Automata

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

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

Joint work with Olivier Carton and Olivier Serre.

Automata

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

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

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

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

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

Automata

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

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

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

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

Démonstration du logiciel Vaucuson-R

Automata

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

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

Automata

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

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

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

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

Automata

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

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

Automata

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

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

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

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

Automata

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

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

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

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

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

Hall F, 5ème étage, thèse disponible à l'adresse https://www.irif.univ-paris-diderot.fr/~guillonb/phd_defense.html

Automata

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

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

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

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

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

Automata

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

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

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

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

Automata

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

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

This is joint work with Seonhee Lim.

Automata

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

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

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

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

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

Automata

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

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

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

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

Automata

Monday March 21, 2016, 10AM, LABRI

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

Automata

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

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

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

Automata

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

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

Automata

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

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

Automata

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

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

Automata

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

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

Automata

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

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