Using Homing, Synchronizing and Distinguishing Input Sequences for the Analysis of Reversible Finite State Machines

Abstract

A digital device is called reversible if it realizes a reversible mapping, i.e., the one for which there exist a unique inverse. The field of reversible computing is devoted to studying all aspects of using and designing reversible devices. During last 15 years this field has been developing very intensively due to its applications in quantum computing, nanotechnology and reducing power consumption of digital devices. We present an analysis of the Reversible Finite State Machines (RFSM) with respect to three well known sequences used in the testability analysis of the classical Finite State Machines (FSM). The homing, distinguishing and synchronizing sequences are applied to two types of reversible FSMs: the converging FSM (CRFSM) and the nonconverging FSM (NCRFSM) and the effect is studied and analyzed. We show that while only certain classical FSMs possess all three sequences, CRFSMs and NCRFSMs have properties allowing to directly determine what type of sequences these machines possess.