Published In

Facta Universitatis, Series: Electronics and Energetics

Document Type


Publication Date



Reversible computing, 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 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.


Facta Universitatis, Series: Electronics and Energetics, is an Open Access Journal in accordance with the Berlin Declaration. All articles can be downloaded free of charge for personal, educational and scientific purposes (Creative Commons licence CC BY-NC-ND).



Persistent Identifier