Adaptive homing sequences for partial weakly-initialized observable FSMs

Эндаумент фонд ТГУ!
Впиши своё имя в историю университета
- Сделать пожертвование -

2021 | Yevtushenko, Nina V.

Add to "Quick Collection"

Description	Size	Format
Adaptive homing sequences for partial weakly-initialized observable FSMs	647 KB	Adobe Acrobat PDF	Read	Download
DOI Доступ к ресурсу на сайте издателя			10.1109/EWDTS52692.2021.9581010

Title: Adaptive homing sequences for partial weakly-initialized observable FSMs
Creator: Vinarskii, Evgenii
|
Tvardovskii, Aleksandr
|
Yevtushenko, Nina V.
Date: 2021
DOI: 10.1109/EWDTS52692.2021.9581010
Description: 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.

Relationships: Show Relationship Browser for this Object
collection(s): Институт прикладной математики и компьютерных наук (c 01.09.2017 г.)
Identifier: смотреть в электронном каталоге НБ ТГУ
Type: статьи в сборниках
Source: 2021 IEEE East-West Design & Test Symposium (EWDTS), Batumi, Georgia, September 10-13, 2021 : proceedings. [S. l.], 2021. P. 335-339
Language: eng

Created: 05-04-2022

607 Visitors

503 Hits

117 Downloads