TY - GEN
T1 - Describing homing and distinguishing sequences for nondeterministic finite state machines via synchronizing automata
AU - Kushik, Natalia
AU - Yevtushenko, Nina
N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2015.
PY - 2015/1/1
Y1 - 2015/1/1
N2 - There is a long standing problem of the study of homing and distinguishing sequences for deterministic and nondeterministic Finite State Machines (FSMs) which are widely used in many applications. A homing sequence allows establishing the state of the given FSM after applying the sequence while a distinguishing sequence allows learning the state of the given FSM before the sequence is applied. On the other hand, other sequences, namely, synchronizing sequences, have been thoroughly studied for finite automata. For a synchronizing automaton, there is a state such that a synchronizing sequence takes the automaton from any state to this state. There are many papers reported on such automata as well as on the complexity of synchronizing sequences. In this paper, given a complete nondeterministic FSM, we propose a method for deriving a corresponding finite automaton such that the set of all homing (or distinguishing) sequences coincides with the set of all synchronizing sequences of the derived automaton.
AB - There is a long standing problem of the study of homing and distinguishing sequences for deterministic and nondeterministic Finite State Machines (FSMs) which are widely used in many applications. A homing sequence allows establishing the state of the given FSM after applying the sequence while a distinguishing sequence allows learning the state of the given FSM before the sequence is applied. On the other hand, other sequences, namely, synchronizing sequences, have been thoroughly studied for finite automata. For a synchronizing automaton, there is a state such that a synchronizing sequence takes the automaton from any state to this state. There are many papers reported on such automata as well as on the complexity of synchronizing sequences. In this paper, given a complete nondeterministic FSM, we propose a method for deriving a corresponding finite automaton such that the set of all homing (or distinguishing) sequences coincides with the set of all synchronizing sequences of the derived automaton.
KW - Distinguishing sequence (distinguishing word)
KW - Homing sequence (homing word)
KW - Nondeterministic finite state machines
KW - Synchronizing sequence (synchronizing word)
U2 - 10.1007/978-3-319-22360-5_16
DO - 10.1007/978-3-319-22360-5_16
M3 - Conference contribution
AN - SCOPUS:84951811887
SN - 9783319223599
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 188
EP - 198
BT - Implementation and Application of Automata - 20th International Conference, CIAA 2015, Proceedings
A2 - Drewes, Frank
PB - Springer Verlag
T2 - 20th International Conference on Implementation and Application of Automata, CIAA 2015
Y2 - 18 August 2015 through 21 August 2015
ER -