In this talk, we study a model computing relations over finite words, generalising one- and two-way transducers. The model, called two-way two-tape automaton, consists in a finite-state machine with two read-only tapes, each one with a reading head able to go both ways. We first emphasize its relation with 4-way automata, which recognize sets of two-dimensional arrays of letters called picture languages; such correspondence provides a proof of the undecidability of the model, and an example separating determinism and non-determinism. We then describe several techniques which, applied to our model, establish (non-)closure properties of the recognizable relations. Finally, the main result presented in this talk is that alternating two-way two-tape automata are not closed under complementation. The proof is a refinement of one of J. Kari for picture languages.

Joint work with Olivier Carton and Olivier Serre.