Seminars

Speaker: Lê Thành Dũng Nguyễn, aka “Tito” — nguyentito.eu/

Title: The structure of polynomial growth for tree automata/transducers and MSO set queries

Abstract:

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 fine-grained lower
bounds known for these problems restricted to ambiguity of word automata
(Drabik, Dürr, Frei, Mazowiecki & Węgrzycki 2025).

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 property of MSO set queries leads directly to a generalization of
Bojańczyk's dimension minimization theorem for string-to-string polyregular
functions. Our generalization applies to MSO set interpretations from trees,
which subsume (as we show) tree-walking tree transducers and invisible pebble
tree-to-string transducers. Finally, with a bit more work we obtain the following:

* a new, short and conceptual proof that macro tree transducers of
linear growth compute only tree-to-tree MSO transductions (a seminal
theorem of Engelfriet and Maneth);

* a procedure to decide polynomial size-to-height increase for macro
tree transducers and compute the polynomial degree, which extends the
recent decidability result of Gallot, Maneth, Nakano and Peyrat (2024)
concerning linear size-to-height increase.

Speaker: Théo Matricon (theomat.github.io/)

Room: B21

Titre : Cost-guided enumeration of regular tree languages in constant delay

Abstract :

Program Synthesis from a few input output examples can be solved in an enumerative fashion, this enables domain agnostic solving assuming the specification can be checked.
The enumeration problem is given a reguar tree language represented by a top down deterministic tree automaton, to enumerate all such trees.
The complexity of the problem is measured in the delay: the time complexity between the enumeration of one tree and the next.
Enumeration by increasing size or depth does not scale for program synthesis due to the combinatorial explosion of the number of trees.
Therefore weights are added on the transition of the input automaton. Summing these weights define a unique cost for each tree inducing a total order over trees.
The goal is to enumerate in a cost-guided fashion i.e. that is in non-decreasing (>=) order of cost.
Algorithms in the literature since the first such search algorithm have all been in logarithmic delay.
We describe the first cost-guided enumeration algorithm with constant delay.

Speaker: Bastien Degardins

Room: Amphi Atrium (RdC Bâtiment ESPRIT)

Title: Visualization and queries for biology in de Bruijn Graphs using relational databases.

Abstract:

Since the emergence of modern sequencers, sequence bioinformatics has become
crucial for processing sequencing data, essential in medicine, biology,
archaeology, and beyond. However, the growing data volumes require software
adaptations to meet these new challenges, despite significant hardware
advancements. Vizitig is a genomic and transcriptomic data visualization
software based on De Bruijn graphs, offering an intuitive query system without
needing to load indexes into RAM, allowing direct work on disk. By leveraging
relational databases, which are highly optimized and backed by decades of
research, Vizitig opens new avenues for research.It relies on NetworkDisk, a
Python package that manages graphs in a relational database, simplifying
software engineering. With a domain-specific language (DSL), Vizitig enables
intuitive queries and easy manipulation of graph metadata, even for
non-technical users. For experts, its compatibility with NetworkX provides
additional possibilities in terms of graph manipulation.

Speaker: Aliaume Lopez (www.lsv.fr/~lopez/)

Title: Which polynomials are computed by N-weighted automata?

Room: B21

Abstract:
Given a semiring K, the notion of K-weighted automata generalizes regular languages to functions from Σ* to K. This model allows us to compute (multivariate) polynomial functions with coefficients in K. We provide a decidable characterization of polynomials with coefficients in Q that can be computed by K-weighted automata for K = (N,+,×) and for K = (Z+,×). As a consequence, we can decide which functions computed by Z-weighted automata are computed by N-weighted automata, under the assumption of commutativity (the order of the letters in the input does not matter) and polynomial growth (the output of the function is bounded by a polynomial in the size of the input). This surprisingly allows us to decide whether such functions are star-free, a notion borrowed from the theory of regular languages.