Reducing the complexity of checking the existence and derivation of adaptive synchronizing experiments for nondeterministic FSMs

Kushik, Natalia and Yevtushenko, Nina and Yenigün, Hüsnü (2016) Reducing the complexity of checking the existence and derivation of adaptive synchronizing experiments for nondeterministic FSMs. In: 1st International Workshop on domAin Specific Model-Based AppRoaches to vErificaTion and validaTiOn, Rome, Italy

[thumbnail of 48-AMERETTO.pdf] PDF
48-AMERETTO.pdf
Restricted to Repository staff only

Download (4MB) | Request a copy

Abstract

In this paper, we address the problem of setting a discrete system specified as a Finite State Machine (FSM) to a known initial state. As the system behavior can be nondeterministic, we discuss the complexity of problems related to deriving synchronizing sequences for nondeterministic FSMs and propose a way for decreasing such complexity. In fact, we suggest to use adaptive synchronizing experiments instead of preset ones, and prove that for non-initialized nondeterministic FSMs the problem of checking the existence of an adaptive synchronizing experiment is in P.
Item Type: Papers in Conference Proceedings
Uncontrolled Keywords: Adaptive sequences; Nondeterministic finite state machines; Synchronizing experiments
Subjects: Q Science > QA Mathematics > QA075 Electronic computers. Computer science
Q Science > QA Mathematics > QA076 Computer software
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng.
Faculty of Engineering and Natural Sciences
Depositing User: Hüsnü Yenigün
Date Deposited: 15 Jul 2016 11:48
Last Modified: 26 Apr 2022 09:22
URI: https://research.sabanciuniv.edu/id/eprint/29400

Actions (login required)

View Item
View Item