Laure Daviaud

OVERLAY Workshop 2025 Workshop Paper

Extracting Weighted Finite Automata from RNNs via iterative partitioning and spectral learning

• Sandamali Yashodhara Wickramasinghe
• Jacob M. Howe
• Laure Daviaud

Highlights Conference 2024 Conference Abstract

Open problems for weighted automata, and why they are so difficult. .

• Laure Daviaud

In this talk, I will review some open problems for weighted automata over general semirings and discuss the reasons why the usual techniques that have been used to solve similar questions, have not been successfully used for those (yet(?)). The talk is aimed to a broad audience - especially to those who know nothing/not much about weighted automata!

MFCS Conference 2023 Conference Paper

Universality and Forall-Exactness of Cost Register Automata with Few Registers

• Laure Daviaud
• Andrew Ryzhikov

The universality problem asks whether a given finite state automaton accepts all the input words. For quantitative models of automata, where input words are mapped to real values, this is naturally extended to ask whether all the words are mapped to values above (or below) a given threshold. This is known to be undecidable for commonly studied examples such as weighted automata over the positive rational (plus-times) or the integer tropical (min-plus) semirings, or equivalently cost register automata (CRAs) over these semirings. In this paper, we prove that when restricted to CRAs with only three registers, the universality problem is still undecidable, even with additional restrictions for the CRAs to be copyless linear with resets. In contrast, we show that, assuming the unary encoding of updates, the ∀-exact problem (does the CRA output zero on all the words?) for integer min-plus linear CRAs can be decided in polynomial time if the number of registers is constant. Without the restriction on the number of registers this problem is known to be PSPACE-complete.

Highlights Conference 2020 Conference Abstract

Probabilistic Automata

• Laure Daviaud

Probabilistic automata were introduced by Rabin in 1963 as an automatic way to map input words with probabilities. They can be viewed as classic non deterministic finite automata, where transitions are labelled with a probability to be taken, given a state and a letter, and words have then a certain probability to be accepted. Probabilistic automata can be seen as a particular case of partially observable Markov decision processes and the natural problems that arise ask whether one can find input words with high probability to be accepted. This tutorial will introduce this model and we will discuss in particular some famous problems related to it, such as emptiness, value 1, approximation, equivalence and containment.

Highlights Conference 2020 Conference Abstract

Probabilistic Automata

• Laure Daviaud

Probabilistic automata were introduced by Rabin in 1963 as an automatic way to map input words with probabilities. They can be viewed as classic non deterministic finite automata, where transitions are labelled with a probability to be taken, given a state and a letter, and words have then a certain probability to be accepted. Probabilistic automata can be seen as a particular case of partially observable Markov decision processes and the natural problems that arise ask whether one can find input words with high probability to be accepted. This tutorial will introduce this model and we will discuss in particular some famous problems related to it, such as emptiness, value 1, approximation, equivalence and containment.

SODA Conference 2019 Conference Paper

Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games

• Wojciech Czerwinski
• Laure Daviaud
• Nathanaël Fijalkow
• Marcin Jurdzinski
• Ranko Lazic 0001
• Pawel Parys

Several distinct techniques have been proposed to design quasi-polynomial algorithms for solving parity games since the breakthrough result of Calude, Jain, Khoussainov, Li, and Stephan (2017): play summaries, progress measures and register games. We argue that all those techniques can be viewed as instances of the separation approach to solving parity games, a key technical component of which is constructing (explicitly or implicitly) an automaton that separates languages of words encoding plays that are (decisively) won by either of the two players. Our main technical result is a quasi-polynomial lower bound on the size of such separating automata that nearly matches the current best upper bounds. This forms a barrier that all existing approaches must overcome in the ongoing quest for a polynomial-time algorithm for solving parity games. The key and fundamental concept that we introduce and study is a universal ordered tree. The technical highlights are a quasi-polynomial lower bound on the size of universal ordered trees and a proof that every separating safety automaton has a universal tree hidden in its state space.

I&C Journal 2018 Journal Article

Classes of languages generated by the Kleene star of a word

• Laure Daviaud
• Charles Paperman

In this paper, we study the lattice and the Boolean algebra, possibly closed under quotient, generated by the languages of the form u ⁎, where u is a word. We provide effective equational characterisations of these classes, i. e. one can decide using our descriptions whether a given regular language belongs or not to each of them.

Highlights Conference 2018 Conference Abstract

Solving mean-payoff parity games in pseudo-quasi-polynomial time

• Laure Daviaud

ABSTRACT. In a mean-payoff parity game, one of the two players aims both to achieve a qualitative parity objective and to minimize a quantitative long-term average of payoffs (aka. mean payoff). The game is zero-sum and hence the aim of the other player is to either foil the parity objective or to maximize the mean payoff. Our main technical result is a pseudo-quasi-polynomial algorithm for solving mean-payoff parity games. All algorithms for the problem that have been developed for over a decade have a pseudo-polynomial and an exponential factors in their running times; in the running time of our algorithm the latter is replaced with a quasi-polynomial one. Our main conceptual contributions are the definitions of strategy decompositions for both players, and a notion of progress measures for mean-payoff parity games that generalizes both parity and energy progress measures. The former provides normal forms for and succinct representations of winning strategies, and the latter enables the application to mean-payoff parity games of the order-theoretic machinery that underpins a recent quasi-polynomial algorithm for solving parity games. This is a joint work with Marcin Jurdzinski and Ranko Lazic.

MFCS Conference 2017 Conference Paper

Comparison of Max-Plus Automata and Joint Spectral Radius of Tropical Matrices

• Laure Daviaud
• Pierre Guillon 0001
• Glenn Merlet

Weighted automata over the tropical semiring Zmax are closely related to finitely generated semigroups of matrices over Zmax. In this paper, we use results in automata theory to study two quantities associated with sets of matrices: the joint spectral radius and the ultimate rank. We prove that these two quantities are not computable over the tropical semiring, i. e. there is no algorithm that takes as input a finite set of matrices S and provides as output the joint spectral radius (resp. the ultimate rank) of S. On the other hand, we prove that the joint spectral radius is nevertheless approximable and we exhibit restricted cases in which the joint spectral radius and the ultimate rank are computable. To reach this aim, we study the problem of comparing functions computed by weighted automata over the tropical semiring. This problem is known to be undecidable, and we prove that it remains undecidable in some specific subclasses of automata.

MFCS Conference 2017 Conference Paper

The Shortest Identities for Max-Plus Automata with Two States

• Laure Daviaud
• Marianne Johnson

Max-plus automata are quantitative extensions of automata designed to associate an integer with every non-empty word. A pair of distinct words is said to be an identity for a class of max-plus automata if each of the automata in the class computes the same value on the two words. We give the shortest identities holding for the class of max-plus automata with two states. For this, we exhibit an interesting list of necessary conditions for an identity to hold. Moreover, this result provides a counter-example of a conjecture of Izhakian, concerning the minimality of certain identities.

Highlights Conference 2014 Conference Abstract

Asymptotic Behaviour of Max-Plus Automata and Size-Change Abstraction

• Laure Daviaud

Max-plus automata are weighted automata over the semiring (ℕ ∪ {-∞}, max, +) that compute some functions from words to ℕ ∪ {-∞}. In this talk, we will study the asymptotic behaviour of a max-plus automaton and more precisely the maximum length of a word of weight at most n. In particular, we will see that this function is of the form Θ ( n α ) for a computable rational α . This result can, in combination with the size-change abstraction, be used for inferring the termination time of an algorithm as a function of the size of its input. This is a joint work with Thomas Colcombet and Florian Zuleger.

Highlights Conference 2013 Conference Abstract

Approximate comparison of distance automata

• Laure Daviaud
• Thomas Colcombet

Distance automata are automata weighted over the semiring (N U {+infinity}, min, +) that compute functions from words to N U {+infinity}. It is known that testing f 0 and two functions f, g computed by distance automata, answers "yes" if f (1+e)g(w), and may answer "yes" or "no" in all other cases. This is a joint work with Thomas Colcombet.