Aperiodic two-way transducers

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.

Authors

• Olivier Carton
• Luc Dartois

Keywords

No keywords are indexed for this paper.