title   
  

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

[img]PDF - Repository staff only - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
4Mb

Official URL: http://dx.doi.org/10.5220/0005854500830090

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
ID Code:29400
Deposited By:Hüsnü Yenigün
Deposited On:15 Jul 2016 11:48
Last Modified:15 Jul 2016 11:48

Repository Staff Only: item control page