On Distinguishing Sequences of Several Classes of Reversible Finite State Machines

The existence of distinguishing sequence (DS) is an important property for finite state machines (FSMs). Such an input sequence can distinguish all the states of the FSM. An FSM possessing a DS can be therefore easily analyzed in a case of unexpected failure and the state when the machine terminated can be identified. In this paper, we investigate length and existence of DSs of several classes of reversible finite state machines (RFSM). Reversible FSMs can be directly constructed on a quantum computer and therefore understanding their properties is important for the efficient usage and implementation of these devices in quantum technologies. In particular, we consider output balanced machines, where for every input the output assignment is balanced. We also consider output unbalanced machines that have the same output assignment for each input. Finally, we investigate a hierarchy of six classes of such machines. All machines we study in this paper possess a DS exists, unlike some RFSMs that might not have DS. In addition the length of DS of all of these machines is shorter than the general length of DS from [1].