Reversible Two-Party Computations

Martin Kutrib

doi:10.1142/S0129054125460050

Reversible Two-Party Computations

2025-09-01

0

PRE

AI

DOI：10.1142/S0129054125460050

Original

Original request for help

Save

Abstract

En 中文

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 also consider 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.

Keywords:

Watson-Crick automata

reversible computation

limited communication

computational capacity

closure properties

decidability of formal language problems

Reversible Two-Party Computations

Abstract

Journal

Organization