Evaluating Length of a Shortest Adaptive Homing Sequence for Weakly Initialized FSMs
Evgenii Vinarskii, Nina Vladimirovna Yevtushenko · 2020
There are many research papers devoted to the state identification problem of finite state machines (FSMs) which are widely used for analysis of discrete event systems. A deterministic complete reduced FSM always has a homing sequence (HS) but a number of non-deterministic FSMs not necessarily have a preset HS; nevertheless, those FSMs can still have an adaptive HS. Moreover, adaptive HS can be shorter than the preset. If each state can be an initial state of a complete FSM, i.e., an FSM is non-initialized, then a shortest adaptive HS (if it exists) has polynomial length in the number of FSM states. We show that it is not the case for weakly-initialized FSMs: such FSMs can have a shortest adaptive HS of exponential length in the number of FSM states / transitions. However, the experimental evaluation shows that the non-polynomial upper bound for a shortest adaptive HS was never reached for randomly generated weakly-initialized two-input FSMs.