Luc Dartois

Highlights Conference 2017 Conference Abstract

On Reversible Transducers

• Luc Dartois

Abstract available in PDF.

Highlights Conference 2016 Conference Abstract

Two-Way Visibly Pushdown Automata and Transducers

• Luc Dartois

CSL Conference 2015 Conference Paper

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 aperiodicity for these transducers and we show that aperiodic transducers correspond exactly to FO-transductions. This lifts to transducers the classical equivalence for languages between FO-definability, recognition by aperiodic monoids and acceptance by counter-free automata.

Highlights Conference 2013 Conference Abstract

Aperiodic two-way transducers

• Olivier Carton
• Luc Dartois

A two-way transducer is a finite state sequential machine with a two-way input tape and a one-way output tape. At each step of the computation, it reads the current symbol, outputs a possibly empty word, then changes its internal state and moves its input head, according to the transition taken with current state and the letter read. It computes a partial function from words over an alphabet to another set of words. Similarly, a MSO-definable function over words is defined as interpretations of linear graphs through logic. A result by Engelfriet and Hoogeboom proved the equivalence of the two models. I will recall the definition of both models, and state an extension of this result to the natural subclass of aperiodic two-way transducers.