15 citations · 79 across the 28 of their papers we have counts for
5 papers · 1 filter
Streamability of nested word transductions
Emmanuel Filiot, Olivier Gauwin, Pierre-Alain Reynier +1
We consider the problem of evaluating in streaming (i.e., in a single left-to-right pass) a nested word transduction with a limited amount of memory. A transduction T is said to be…
Decidable Weighted Expressions with Presburger Combinators
Emmanuel Filiot, Nicolas Mazzocchi, Jean-François Raskin
In this paper, we investigate the expressive power and the algorithmic properties of weighted expressions, which define functions from finite words to integers. First, we consider…
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…
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…