TY - GEN
T1 - On the length of homing sequences for nondeterministic finite state machines
AU - Kushik, Natalia
AU - Yevtushenko, Nina
PY - 2013/8/13
Y1 - 2013/8/13
N2 - Given a reduced deterministic finite state machine, there always exists a homing sequence of length polynomial with respect to the number of states of the machine. For nondeterministic reduced finite state machines, a homing sequence may not exist, and moreover, if it exists, its length can be exponential. We show that the problem of deriving a homing sequence cannot be reduced to deriving a synchronizing word for underlying automata and should be studied independently. We also propose a novel class of (n - 1)-input finite state machines with n states whose shortest homing sequence is of length 2 n-1 -1.
AB - Given a reduced deterministic finite state machine, there always exists a homing sequence of length polynomial with respect to the number of states of the machine. For nondeterministic reduced finite state machines, a homing sequence may not exist, and moreover, if it exists, its length can be exponential. We show that the problem of deriving a homing sequence cannot be reduced to deriving a synchronizing word for underlying automata and should be studied independently. We also propose a novel class of (n - 1)-input finite state machines with n states whose shortest homing sequence is of length 2 n-1 -1.
U2 - 10.1007/978-3-642-39274-0_20
DO - 10.1007/978-3-642-39274-0_20
M3 - Conference contribution
AN - SCOPUS:84881246072
SN - 9783642392733
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 220
EP - 231
BT - Implementation and Application of Automata - 18th International Conference, CIAA 2013, Proceedings
T2 - 18th International Conference on Implementation and Application of Automata, CIAA 2013
Y2 - 16 July 2013 through 19 July 2013
ER -