~~NOCACHE~~ /* DO NOT EDIT THIS FILE */ [[en:seminaires:automates:index|Automata]]\\ Friday April 11, 2025, 2PM, Salle 3052\\ **Mahsa Shirmohammadi** //Differential Tree Automata// \\ A rationally dynamically algebraic (RDA) power series is one that arises as (a component of) the solution of a system of differential equations of the form y′=F(y), where F is a vector of rational functions that is defined at y(0). RDA power series subsume algebraic power series and are a proper subclass of differentially algebraic power series (those that satisfy a univariate polynomial-differential equation). We give a combinatorial characterisation of RDA power series in terms of exponential generating functions of regular languages of labelled trees. Motivated by this connection, we define the notion of a differential tree automaton. Differential tree automata generalise weighted tree automata by allowing the transition weights to be rational functions of the tree size. Our main result is that the ordinary generating functions of the formal tree series recognised by differential tree automata are exactly the differentially algebraic power series. The proof of this result establishes a general form of recurrence satisfied by the sequence of coefficients of a differentially algebraic power series, generalising Reutenauer's matrix representation of polynomially recursive sequences. As a corollary we obtain a procedure for determining equality of differential tree automata. The talk is based on a joint work with Rida Ait El Manssour, Vincent Cheval, and James Worrell and can be found here: https://arxiv.org/abs/2407.08218 [[en:seminaires:automates:index|Automata]]\\ Friday March 28, 2025, 2PM, Salle 3052\\ **Mahsa Shirmohammadi** //The Complexity of Orbit-Closure Problems// \\ Computational problems concerning the orbit of a point under the action of a matrix group occur in numerous subfields of computer science, including complexity theory, program analysis, quantum computation, and automata theory. In many cases the focus extends beyond orbits proper to orbit closures under a suitable topology. Typically one starts from a group and several points and asks questions about the orbit closure of the points under the action of the group, e.g., whether two given orbit closures intersect. In this talk, I will introduce and motivate several problems involving groups and orbit closures, focusing on computation and determination tasks. In regards to computation, we are given a set of matrices and tasked with computing the defining ideal of the algebraic group generated by those matrices. The determination task, on the other hand, involves starting with a given variety and determining whether and how it can be represented as an algebraic group or an orbit closure. The "how" question often asks whether the underlying group can be topologically generated by s matrices for a given s. The talk is based on several joint works: (ISSAC 22) https://dl.acm.org/doi/10.1145/3476446.3536172 (Submitted) https://arxiv.org/abs/2407.04626 (POPL25) https://arxiv.org/abs/2407.09154 [[en:seminaires:automates:index|Automata]]\\ Friday March 21, 2025, 2PM, Salle 3052\\ **Pascal Weil** (LIPN & ReLaX) //Recognizable trace languages, propositional dynamic logic and cascade decomposition of asynchronous automata// \\ Joint work with Bharat Adsul (IIT Bombay), Paul Gastin (LMF), Saptarshi Sankar (IIT-B), Shantanu Kulkarni (IIT-B), through papers at CONCUR 2020, LMCS 2020, CONCUR 2022, LICS 2024 We examine the following problem for regular languages of (Mazurkiewicz) traces: given a regular trace language, can it be recognized by a cascade product of very simple localized asynchronous automata — essentially, 2-state reset automata and group automata? This is a trace version of the Krohn-Rhodes theorem, a deep result on languages of finite words, which goes back to the early 1960s. Solving this problem in the positive (such a cascade product always exists) was surprisingly (?) non-trivial. It involves giving a proper definition of local cascade products of asynchronous (or Zielonka) automata, very much in the spirit of the notion of transducers, and describing an expressively complete fragment of PDL (propositional dynamic logic) for traces. Specialists of the topic will remember the time stamping mechanism in Zielonka's proof of the equivalence between regularity and asynchronous automata, and the related notion of a gossip automaton, introduced by Mukund and Sohoni. A large part of the proof consists in showing that certain PDL primitives which correspond to the gossip automaton, can be done without. [[en:seminaires:automates:index|Automata]]\\ Friday March 7, 2025, 2PM, Salle 3052\\ **Alexi Block Gorman** (LIGM) //A Hierarchy of Expressive Power for Büchi Automata Over the Reals// \\ There are compelling and long-established connections between automata theory and model theory, including Büchi automata and the additive group of real numbers. We say a subset X of the reals is "k-regular" if there is a Büchi automaton that accepts (one of) the base-k representations of every element of X, and rejects the base-k representations of each element in its complement. These sets often exhibit fractal-like behavior--e.g., the Cantor set is 3-regular. In this talk we will discuss the hierarchy of B\"uchi automata in terms of their expressive power--what other automata can we build from a few basic ones and (most of) the classic automata operations? We will unpack the connection between this question and first-order structures on the reals whose definable sets are all recognized by Büchi-automata. [[en:seminaires:automates:index|Automata]]\\ Friday February 28, 2025, 2PM, Salle 3052\\ **Herman Goulet-Ouellet** (Czech Technical University) //Density of group languages under ergodic probability measures// \\ I will present recent work (with Valérie Berthé, Carl-Fredrik Nyberg-Brodda, Dominique Perrin and Karl Petersen) about densities of group languages under ergodic probability measures. Group languages are the rational languages recognized by morphisms onto finite groups, or equivalently recognized by automata where letters act as permutations of the states. I will explain how to obtain a simple formula for the density which holds under some ergodicity condition on the skew product between the group recognizing the language and the support of the probability measure. I will also explain how to describe these minimal components and how they are related with return words. If time permits, I will also briefly touch on our recent efforts, with Valérie Berthé and Dominique Perrin, to extend these techniques to general rational languages. [[en:seminaires:automates:index|Automata]]\\ Friday February 21, 2025, 2PM, Salle 3052\\ **Andrew Ryzhikov** (University of Warsaw) //How combinatorics stands in the way of matrix reachability (and what we can do about that)// \\ Combinatorial automata theory can be seen as studying reachability in transformation semigroups. An interesting way of generalising this setting is by lifting it up to reachability in finite semigroups of rational matrices. Here, besides finite automata theory, other areas come into play, for example weighted automata, algebraic number theory, and multilinear algebra. I will explain several nice questions (such as mortality and minimum rank) that transfer from transformation semigroups to finite matrix semigroups. I will also explain the lack of mathematical structure that is brought by certain PSPACE-complete transformation semigroup problems. [[en:seminaires:automates:index|Automata]]\\ Friday February 14, 2025, 2PM, Salle 3052\\ **Sylvain Lombardy** (LaBRI) //On Two-way Q-Automata// \\ Joint work with Louis-Marie DANDO Two-way automata are natural models of computation. Nevertheless, it was proven in 1959 (both by Jefferson, and by Rabin and Scott) that they are not more powerful than one-way automata. In the framework of weighted automata, things are more complicated, thus interesting. We focus in this talk on automata where weights are rational numbers. We present a hierarchy of Q-automata: rotating, sweeping and 2-way automata. We show a natural extension of the Kleene-Schützenberger theorem between rotating Q-automata and Hadamard series which are extensions of rational series. Finally, we prove that 2-way Q-automata are not more powerful than rotating Q-automata. [[en:seminaires:automates:index|Automata]]\\ Friday January 31, 2025, 2PM, Salle 3052\\ **Christian Choffrut** //Message complexity of multiautomata systems// \\ The model, due to Jurdzinski in his PhD thesis 1999 under the direction of Kutylovski, is a finite collection of one-way or two-way deterministic automata working synchronously on the same input and dispatching messages when reaching certain so-called broadcasting states. The input is accepted if a predetermined automaton reaches a final state when it arrives at the right end of the input. The message complexity of the system is the function f(n) which, to every integer, assigns the minimum number of messages required in a run over inputs of length n. Jurdzinski and Kutylovski, 2002, proved in the one-way case that if the system requires a nonconstant number of messages then it requires at least log(n) messages and claimed a result of the same kind for two-way systems. I show that when the input is unary, i.e., over an alphabet with a unique letter, the language accepted is rational (or equivalently ultimately periodic) if and only if the number of messages is finite. [[en:seminaires:automates:index|Automata]]\\ Friday January 24, 2025, 2PM, Salle 3052\\ **Olivier Carton** (IRIF) //Rauzy dimension and finite state dimension// \\ In a paper of 1976, Rauzy studied two complexity notions, $\underline{β}$ and $\overline{β}$, for infinite sequences over a finite alphabet. The function $\underline{β}$ is maximum exactly in the Borel normal sequences and $\overline{β}$ is minimum exactly in the sequences that, when added to any Borel normal sequence, the result is also Borel normal. Although the definition of $\underline{β}$ and $\overline{β}$ do not involve finite-state automata, we establish some connections between them and the lower $\underline{\dim}$ and upper $\overline{\dim}$ finite-state dimension (or other equivalent notions like finite-state compression ratio, entropy or cumulative log-loss of finite-state predictors). We show tight lower and upper bounds on $\underline{\dim}$ and $\overline{\dim}$ as functions of $\underline{β}$ and $\overline{β}$, respectively. In particular this implies that sequences with $\overline{\dim}$ zero are exactly the ones that that, when added to any Borel normal sequence, the result is also Borel normal. We also show that the finite-state dimensions $\underline{\dim}$ and~$\overline{\dim}$ are essentially subadditive. [[en:seminaires:automates:index|Automata]]\\ Friday January 17, 2025, 2PM, Salle 3052\\ **Subin Pulari** (LaBRI) //On the Compressibility of Real Numbers: New insights using exponential sums// \\ Measuring the informational content of real numbers has been a significant area of inquiry in algorithmic information theory. Finite-state compressibility (or finite-state dimension) of a real number is a value in [0, 1] which quantifies the amount of information/randomness in the real number as measured using finite-state automata. Finite-state dimension is the lower asymptotic ratio of compression achievable on an infinite string using information-lossless finite-state compressors. Interestingly, the finite-state dimension of a real number is also equal to the block Shannon entropy rate of the infinite sequence representing the expansion of the real number in a base b. A line of work, originating from Schnorr and Stimm (1972), has established that a number is Borel normal in base b if and only if its base b expansion has finite-state compressibility equal to 1, i.e., is incompressible. Hence, normal numbers are precisely the class of numbers that are incompressible using finite-state compressors. Most of the prior research on finite-state dimension has relied on combinatorial methods. In this talk we explore how tools from Fourier analysis can be employed to gain new insights into the compressibility of real numbers and we answer an open question posed by Lutz and Mayordomo. Absolutely normal numbers, being finite-state incompressible in every base of expansion, are precisely those numbers which have finite-state dimension equal to 1 in every base. At the other extreme, for example, every rational number has 0 finite-state dimension in every base. Generalizing this, Lutz and Mayordomo asked the following question: Does there exist any s strictly between 0 and 1 and a real number r such that r has finite state dimension equal to s in every base?. In this talk we use several tools involving exponential sums and techniques from Schmidt's work in 1960 to construct, for any given s in (0,1], a real number r having finite-state compressibility equal to s in every base. We thereby answer the open question affirmatively.