  Deterministic synchronous systems consisting of two finite automata running
in opposite directions on a shared read-only input are studied with respect to
their ability to perform reversible computations, which means that the automata
are also backward deterministic and, thus, are able to uniquely step the
computation back and forth. We study the computational capacity of such devices
and obtain on the one hand that there are regular languages that cannot be
accepted by such systems. On the other hand, such systems can accept even
non-semilinear languages. Since the systems communicate by sending messages, we
consider also systems where the number of messages sent during a computation is
restricted. We obtain a finite hierarchy with respect to the allowed amount of
communication inside the reversible classes and separations to general, not
necessarily reversible, classes. Finally, we study closure properties and
decidability questions and obtain that the questions of emptiness, finiteness,
inclusion, and equivalence are not semidecidable if a superlogarithmic amount
of communication is allowed.
