2 citations · 4 across the 4 of their papers we have counts for
8 papers
Weighted Automata and Expressions over Pre-Rational Monoids
Nicolas Baudru, Louis-Marie Dando, Nathan Lhote +3
The Kleene theorem establishes a fundamental link between automata and expressions over the free monoid. Numerous generalisations of this result exist in the literature. Lifting th…
Equivalence kernels of sequential functions and sequential observation synthesis
Paulin Fournier, Nathan Lhote
We show that one can decide if a rational equivalence relation can be given as the equivalence kernel of a sequential letter-to-letter transduction. This problem comes from the set…
A Robust Class of Linear Recurrence Sequences
Corentin Barloy, Nathanaël Fijalkow, Nathan Lhote +1
We introduce a subclass of linear recurrence sequences which we call poly-rational sequences because they are denoted by rational expressions closed under sum and product. We show…
String-to-String Interpretations with Polynomial-Size Output
Mikołaj Bojańczyk, Sandra Kiefer, Nathan Lhote
String-to-string MSO interpretations are like Courcelle's MSO transductions, except that a single output position can be represented using a tuple of input positions instead of jus…
Edge arboricity : Do we need equitabilility ?
Nathan Lhote, Mohammed Senhaji
In this paper we study a new variant of graph arboricity, which requires all the forests to have the same number of edges (up to a difference of 1). We prove that the new variant,…
On Delay and Regret Determinization of Max-Plus Automata
Emmanuel Filiot, Ismaël Jecker, Nathan Lhote +2
Decidability of the determinization problem for weighted automata over the semiring , WA for short, is a long-standing open question. We propo…