7 citations · 17 across the 16 of their papers we have counts for
5 papers · 1 filter
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,…
Logical and Algebraic Characterizations of Rational Transductions
Emmanuel Filiot, Olivier Gauwin, Nathan Lhote
Rational word languages can be defined by several equivalent means: finite state automata, rational expressions, finite congruences, or monadic second-order (MSO) logic. The robust…
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…
On Reversible Transducers
Luc Dartois, Paulin Fournier, Ismaël Jecker +1
Deterministic two-way transducers define the robust class of regular functions which is, among other good properties, closed under composition. However, the best known algorithms f…
Logics for Word Transductions with Synthesis
Luc Dartois, Emmanuel Filiot, Nathan Lhote
We introduce a logic, called LT, to express properties of transductions, i.e. binary relations from input to output (finite) words. In LT, the input/output dependencies are modelle…