USING HOMING, SYNCHRONIZING AND DISTINGUISHING INPUT SEQUENCES FOR THE ANALYSIS OF REVERSIBLE FINITE STATE MACHINES

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 non-converging FSM (NCRFSM) and the et is studied and analyzed. We show that while only certain classical FSMs possess all three sequences, CRFSMs and NCRF-SMs have properties allowing to directly determine what type of sequences these ma-chines possess.