6 citations · 7 across the 6 of their papers we have counts for
9 papers
Efficient Construction of Reversible Transducers from Regular Transducer Expressions
Luc Dartois, Paul Gastin, R. Govind +1
The class of regular transformations has several equivalent characterizations such as functional MSO transductions, deterministic two-way transducers, streaming string transducers,…
Aperiodic two-way transducers and FO-transductions
Olivier Carton, Luc Dartois
Deterministic two-way transducers on finite words have been shown by Engelfriet and Hoogeboom to have the same expressive power as MSO-transductions. We introduce a notion of aperi…
SD-Regular Transducer Expressions for Aperiodic Transformations
Luc Dartois, Paul Gastin, Shankara Narayanan Krishna
FO transductions, aperiodic deterministic two-way transducers, as well as aperiodic streaming string transducers are all equivalent models for first order definable functions. In t…
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…
Two-Way Visibly Pushdown Automata and Transducers
Luc Dartois, Emmanuel Filiot, Pierre-Alain Reynier +1
Automata-logic connections are pillars of the theory of regular languages. Such connections are harder to obtain for transducers, but important results have been obtained recently…
Aperiodic String Transducers
Luc Dartois, Ismaël Jecker, Pierre-Alain Reynier
Regular string-to-string functions enjoy a nice triple characterization through deterministic two-way transducers (2DFT), streaming string transducers (SST) and MSO definable funct…
Adding modular predicates to first-order fragments
Luc Dartois, Charles Paperman
We investigate the decidability of the definability problem for fragments of first order logic over finite words enriched with modular predicates. Our approach aims toward the most…
Rankers over Infinite Words
Luc Dartois, Manfred Kufleitner, Alexander Lauser
We consider the four fragments FO2, the intersection of Sigma2 and FO2, the intersection of Pi2 and FO2, and Delta2 of first-order logic FO[<] over finite and infinite words. For a…