Title: Two-way Two-tape Automata,
Abstract: In this article we consider two-way two-tape (alternating) automata accepting
pairs of words and we study some closure properties of this model. Our main
result is that such alternating automata are not closed under complementation
for non-unary alphabets. This improves a similar result of Kari and Moore for
picture languages. We also show that these deterministic, non-deterministic and
alternating automata are not closed under composition.