26 citations · 68 across the 9 of their papers we have counts for
11 papers
Feasability of Learning Weighted Automata on a Semiring
Laure Daviaud, Marianne Johnson
Since the seminal work by Angluin and the introduction of the L*-algorithm, active learning of automata by membership and equivalence queries has been extensively studied to learn…
The Big-O Problem for Max-Plus Automata is Decidable (PSPACE-Complete)
Laure Daviaud, David Purser, Marie Tcheng
We show that the big-O problem for max-plus automata is decidable and PSPACE-complete. The big-O (or affine domination) problem asks whether, given two max-plus automata computing…
The Strahler number of a parity game
Laure Daviaud, Marcin Jurdziński, K. S. Thejaswini
The Strahler number of a rooted tree is the largest height of a perfect binary tree that is its minor. The Strahler number of a parity game is proposed to be defined as the smalles…
Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games
Wojciech Czerwiński, Laure Daviaud, Nathanaël Fijalkow +3
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 St…
Undecidability of a weak version of MSO+U
Mikołaj Bojańczyk, Laure Daviaud, Bruno Guillon +2
We prove the undecidability of MSO on -words extended with the second-order predicate which says that the distance between consecutive positions in a set $X \subseteq \…
When is Containment Decidable for Probabilistic Automata?
Laure Daviaud, Marcin Jurdziński, Ranko Lazić +3
The emptiness and containment problems for probabilistic automata are natural quantitative generalisations of the classical language emptiness and inclusion problems for Boolean au…
Regular and First Order List Functions
Mikolaj Bojanczyk, Laure Daviaud, Krishna Shankara Narayanan
We define two classes of functions, called regular (respectively, first-order) list functions, which manipulate objects such as lists, lists of lists, pairs of lists, lists of pair…
A pseudo-quasi-polynomial algorithm for solving mean-payoff parity games
Laure Daviaud, Marcin Jurdzinski, Ranko Lazic
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 payo…
Degree of sequentiality of weighted automata
Laure Daviaud, Ismael Jecker, Pierre-Alain Reynier +1
Weighted automata (WA) are an important formalism to describe quantitative properties. Obtaining equivalent deterministic machines is a longstanding research problem. In this paper…
Identities in Upper Triangular Tropical Matrix Semigroups and the Bicyclic Monoid
Laure Daviaud, Marianne Johnson, Mark Kambites
We establish necessary and sufficient conditions for a semigroup identity to hold in the monoid of upper triangular tropical matrices, in terms of equivalence of certai…
Comparison of max-plus automata and joint spectral radius of tropical matrices
Laure Daviaud, Pierre Guillon, Glenn Merlet
Weighted automata over the max-plus semiring S are closely related to finitely generated semigroups of matrices over S. In this paper, we use results in automata theory to study tw…