TY - GEN
T1 - Preset and adaptive homing experiments for nondeterministic finite state machines
AU - Kushik, Natalia
AU - El-Fakih, Khaled
AU - Yevtushenko, Nina
PY - 2011/8/11
Y1 - 2011/8/11
N2 - In this paper, we present algorithms for preset and adaptive homing experiments for a given observable reduced nondeterministic finite state machine (NFSM). We show that the tight upper bound on a shortest preset homing sequence for a NFSM with n states and with two or more initial states is of order 2 n2. The upper bound on a shortest adaptive homing sequence of a NFSM with m initial states, m ≤ n, states is of order ∑j=2 mCnj and this upper bound is of order 2 n when m tends to n.
AB - In this paper, we present algorithms for preset and adaptive homing experiments for a given observable reduced nondeterministic finite state machine (NFSM). We show that the tight upper bound on a shortest preset homing sequence for a NFSM with n states and with two or more initial states is of order 2 n2. The upper bound on a shortest adaptive homing sequence of a NFSM with m initial states, m ≤ n, states is of order ∑j=2 mCnj and this upper bound is of order 2 n when m tends to n.
KW - Preset and adaptive homing experiments
KW - nondeterministic finite state machines
U2 - 10.1007/978-3-642-22256-6_20
DO - 10.1007/978-3-642-22256-6_20
M3 - Conference contribution
AN - SCOPUS:79961183571
SN - 9783642222559
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 215
EP - 224
BT - Implementation and Application of Automata - 16th International Conference, CIAA 2011, Proceedings
T2 - 16th International Conference on Implementation and Application of Automata, CIAA 2011
Y2 - 13 July 2011 through 16 July 2011
ER -