~~NOCACHE~~
/* DO NOT EDIT THIS FILE               */
/* THIS FILE WAS GENERATED             */
/* EDIT THE FILE "indexheader" INSTEAD */
/* OR ACCESS THE DATABASE              */

{{page>.:indexheader}}

\\ ==== Next talks ====
[[en:seminaires:automates:index|Automata]]\\
Friday May 9, 2025, 2PM, Salle 3052\\
**Quentin Aristote** (IRIF) //Learning automata weighted over number rings, concretely (and categorically)//
<button type="link" size="xs" collapse="b5-1258">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b5-1258" collapsed="true">
<well size="sm">
We study automata weighted over number rings, that is, rings of integers in an algebraic number field.

We show that number rings are what we call "almost strong Fatou": if an n-state automaton weighted in a number field recognizes an integer-valued series, then it admits an equivalent n+1-state automaton weighted in the corresponding ring of integers.

We give a polynomial-time algorithm for computing such an n+1-state automaton, and show that removing any more states is at least as hard as solving the principal ideal problem, for which the best currently known algorithm is in quantum polynomial time.

Finally, we will see how this procedure can be used to reduce active learning problems in number rings to active learning problems in fields. If time allows, I will also give a brief teaser of how this generalizes to a generic reduction procedure between active learning problems for automata valued in different categories. These categorical aspects will be further developed on May 15th for a talk at the AutCat seminar.
</well>
</collapse>


[[en:seminaires:automates:index|Automata]]\\
Friday May 16, 2025, 2PM, Salle 3052\\
**Lê Thành Dũng (Tito) Nguyễn** (LIS (Marseille)) //The structure of polynomial growth for tree automata/transducers and MSO set queries//
<button type="link" size="xs" collapse="b5-1259">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b5-1259" collapsed="true">
<well size="sm">
Given an ℕ-weighted tree automaton, we give a decision procedure for exponential vs polynomial growth (with respect to the input size) in quadratic time, and an algorithm that computes the exact polynomial degree of growth in cubic time. As a special case, they apply to the growth of the ambiguity of a nondeterministic tree automaton, i.e. the number of distinct accepting runs over a given input. Our time complexities match the recent fine-grained lower bounds for these problems restricted to ambiguity of word automata.
We deduce analogous decidability results (ignoring complexity) for the growth of the number of results of set queries in Monadic Second-Order logic (MSO) over ranked trees. In the case of polynomial growth of degree k, we also prove a reparameterization theorem for such queries: their results can be mapped to k-tuples of input nodes in a finite-to-one and MSO-definable fashion. 
This has several consequences for transducers, that I will probably not have the time to cover in the talk, but you can check out the preprint: https://arxiv.org/abs/2501.10270 (joint work with Paul Gallot and Nathan Lhote).
</well>
</collapse>


[[en:seminaires:automates:index|Automata]]\\
Friday June 13, 2025, 2PM, Salle 3052\\
**Aliaume Lopez**  //To be announced.//
\\


\\ ==== Previous talks ====
\\ === Year 2025 ===

{{page>.:automates2025}}

\\ === Year 2024 ===

{{page>.:automates2024}}

\\ === Year 2023 ===

{{page>.:automates2023}}

\\ === Year 2022 ===

{{page>.:automates2022}}

\\ === Year 2021 ===

{{page>.:automates2021}}

\\ === Year 2020 ===

{{page>.:automates2020}}

\\ === Year 2019 ===

{{page>.:automates2019}}

\\ === Year 2018 ===

{{page>.:automates2018}}

\\ === Year 2017 ===

{{page>.:automates2017}}

\\ === Year 2016 ===

{{page>.:automates2016}}