Adaptive homing sequences for partial weakly-initialized observable FSMs E. Vinarskii, A. Tvardovskii, N. V. Yevtushenko
Material type: ArticleContent type: Текст Media type: электронный Subject(s): конечные автоматы | частичные автоматыGenre/Form: статьи в сборниках Online resources: Click here to access online In: 2021 IEEE East-West Design & Test Symposium (EWDTS), Batumi, Georgia, September 10-13, 2021 : proceedings P. 335-339Abstract: Finite State Machine (FSM) based state identification problem is widely used for analysis of discrete event systems. A homing sequence (HS) allows to determine the current state of an FSM under investigation. An HS is known to always exist and has polynomial length with respect to the number of states for a non-initialized reduced complete deterministic FSM where for each input sequence there is exactly one output sequence and any state can be an initial state. The HS problem becomes more complex if partial, non-deterministic or weakly-initialized machines are considered; for such FSMs an HS not always exists and can be much longer when existing. In particular, it has been proven that for a complete weakly-initialized non-deterministic FSM, length of a shortest adaptive HS (AHS) can be exponential with respect to the number of FSM states but HS length was not evaluated. In this paper, we consider the HS problem for partial observable possibly non-deterministic FSMs. In particular, we suggest a criterion for the existence of an AHS for a partial observable FSM and estimate the length of a shortest AHS.Библиогр.: 13 назв.
Finite State Machine (FSM) based state identification problem is widely used for analysis of discrete event systems. A homing sequence (HS) allows to determine the current state of an FSM under investigation. An HS is known to always exist and has polynomial length with respect to the number of states for a non-initialized reduced complete deterministic FSM where for each input sequence there is exactly one output sequence and any state can be an initial state. The HS problem becomes more complex if partial, non-deterministic or weakly-initialized machines are considered; for such FSMs an HS not always exists and can be much longer when existing. In particular, it has been proven that for a complete weakly-initialized non-deterministic FSM, length of a shortest adaptive HS (AHS) can be exponential with respect to the number of FSM states but HS length was not evaluated. In this paper, we consider the HS problem for partial observable possibly non-deterministic FSMs. In particular, we suggest a criterion for the existence of an AHS for a partial observable FSM and estimate the length of a shortest AHS.
There are no comments on this title.