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

Natalia Kushik; Nina Yevtushenko; Husnu Yenigun

doi:10.5220/0005854500830090

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

Natalia Kushik, Nina Yevtushenko, Husnu Yenigun

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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 sequences instead of preset ones, and prove that for non-initialized nondeterministic FSMs the problem of checking the existence of an adaptive synchronizing sequence is in P.

Original language	English
Title of host publication	AMARETTO 2016 - Proceedings of the International Workshop on DomAin Specific Model-Based AppRoaches to vErificaTion and validaTiOn
Editors	Antonello Calabro, Francesca Lonetti, Eda Marchetti
Publisher	SciTePress
Pages	83-91
Number of pages	9
ISBN (Electronic)	9789897581663
DOIs	https://doi.org/10.5220/0005854500830090
Publication status	Published - 1 Jan 2016
Event	1st International Workshop on domAin Specific Model-Based AppRoaches to vErificaTion and validaTiOn, AMARETTO 2016 - Rome, Italy Duration: 19 Feb 2016 → 21 Feb 2016

Publication series

Name	AMARETTO 2016 - Proceedings of the International Workshop on DomAin Specific Model-Based AppRoaches to vErificaTion and validaTiOn

Conference

Conference	1st International Workshop on domAin Specific Model-Based AppRoaches to vErificaTion and validaTiOn, AMARETTO 2016
Country/Territory	Italy
City	Rome
Period	19/02/16 → 21/02/16

Keywords

Adaptive sequences
Nondeterministic finite state machines
Synchronizing experiments

Access to Document

10.5220/0005854500830090

Cite this

Kushik, N., Yevtushenko, N., & Yenigun, H. (2016). Reducing the complexity of checking the existence and derivation of adaptive synchronizing experiments for nondeterministic FSMs. In A. Calabro, F. Lonetti, & E. Marchetti (Eds.), AMARETTO 2016 - Proceedings of the International Workshop on DomAin Specific Model-Based AppRoaches to vErificaTion and validaTiOn (pp. 83-91). (AMARETTO 2016 - Proceedings of the International Workshop on DomAin Specific Model-Based AppRoaches to vErificaTion and validaTiOn). SciTePress. https://doi.org/10.5220/0005854500830090

Kushik, Natalia ; Yevtushenko, Nina ; Yenigun, Husnu. / Reducing the complexity of checking the existence and derivation of adaptive synchronizing experiments for nondeterministic FSMs. AMARETTO 2016 - Proceedings of the International Workshop on DomAin Specific Model-Based AppRoaches to vErificaTion and validaTiOn. editor / Antonello Calabro ; Francesca Lonetti ; Eda Marchetti. SciTePress, 2016. pp. 83-91 (AMARETTO 2016 - Proceedings of the International Workshop on DomAin Specific Model-Based AppRoaches to vErificaTion and validaTiOn).

@inproceedings{e2cfd148ce064cd89cea9cc93d4bc3f1,

title = "Reducing the complexity of checking the existence and derivation of adaptive synchronizing experiments for nondeterministic FSMs",

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 sequences instead of preset ones, and prove that for non-initialized nondeterministic FSMs the problem of checking the existence of an adaptive synchronizing sequence is in P.",

keywords = "Adaptive sequences, Nondeterministic finite state machines, Synchronizing experiments",

author = "Natalia Kushik and Nina Yevtushenko and Husnu Yenigun",

note = "Publisher Copyright: Copyright {\textcopyright} 2016 by SCITEPRESS - Science and Technology Publications.; 1st International Workshop on domAin Specific Model-Based AppRoaches to vErificaTion and validaTiOn, AMARETTO 2016 ; Conference date: 19-02-2016 Through 21-02-2016",

year = "2016",

month = jan,

day = "1",

doi = "10.5220/0005854500830090",

language = "English",

series = "AMARETTO 2016 - Proceedings of the International Workshop on DomAin Specific Model-Based AppRoaches to vErificaTion and validaTiOn",

publisher = "SciTePress",

pages = "83--91",

editor = "Antonello Calabro and Francesca Lonetti and Eda Marchetti",

booktitle = "AMARETTO 2016 - Proceedings of the International Workshop on DomAin Specific Model-Based AppRoaches to vErificaTion and validaTiOn",

}

Kushik, N, Yevtushenko, N & Yenigun, H 2016, Reducing the complexity of checking the existence and derivation of adaptive synchronizing experiments for nondeterministic FSMs. in A Calabro, F Lonetti & E Marchetti (eds), AMARETTO 2016 - Proceedings of the International Workshop on DomAin Specific Model-Based AppRoaches to vErificaTion and validaTiOn. AMARETTO 2016 - Proceedings of the International Workshop on DomAin Specific Model-Based AppRoaches to vErificaTion and validaTiOn, SciTePress, pp. 83-91, 1st International Workshop on domAin Specific Model-Based AppRoaches to vErificaTion and validaTiOn, AMARETTO 2016, Rome, Italy, 19/02/16. https://doi.org/10.5220/0005854500830090

Reducing the complexity of checking the existence and derivation of adaptive synchronizing experiments for nondeterministic FSMs. / Kushik, Natalia; Yevtushenko, Nina; Yenigun, Husnu.
AMARETTO 2016 - Proceedings of the International Workshop on DomAin Specific Model-Based AppRoaches to vErificaTion and validaTiOn. ed. / Antonello Calabro; Francesca Lonetti; Eda Marchetti. SciTePress, 2016. p. 83-91 (AMARETTO 2016 - Proceedings of the International Workshop on DomAin Specific Model-Based AppRoaches to vErificaTion and validaTiOn).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

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

AU - Kushik, Natalia

AU - Yevtushenko, Nina

AU - Yenigun, Husnu

PY - 2016/1/1

Y1 - 2016/1/1

N2 - 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 sequences instead of preset ones, and prove that for non-initialized nondeterministic FSMs the problem of checking the existence of an adaptive synchronizing sequence is in P.

AB - 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 sequences instead of preset ones, and prove that for non-initialized nondeterministic FSMs the problem of checking the existence of an adaptive synchronizing sequence is in P.

KW - Adaptive sequences

KW - Nondeterministic finite state machines

KW - Synchronizing experiments

U2 - 10.5220/0005854500830090

DO - 10.5220/0005854500830090

M3 - Conference contribution

AN - SCOPUS:84966783357

T3 - AMARETTO 2016 - Proceedings of the International Workshop on DomAin Specific Model-Based AppRoaches to vErificaTion and validaTiOn

SP - 83

EP - 91

BT - AMARETTO 2016 - Proceedings of the International Workshop on DomAin Specific Model-Based AppRoaches to vErificaTion and validaTiOn

A2 - Calabro, Antonello

A2 - Lonetti, Francesca

A2 - Marchetti, Eda

PB - SciTePress

T2 - 1st International Workshop on domAin Specific Model-Based AppRoaches to vErificaTion and validaTiOn, AMARETTO 2016

Y2 - 19 February 2016 through 21 February 2016

ER -

Kushik N, Yevtushenko N, Yenigun H. Reducing the complexity of checking the existence and derivation of adaptive synchronizing experiments for nondeterministic FSMs. In Calabro A, Lonetti F, Marchetti E, editors, AMARETTO 2016 - Proceedings of the International Workshop on DomAin Specific Model-Based AppRoaches to vErificaTion and validaTiOn. SciTePress. 2016. p. 83-91. (AMARETTO 2016 - Proceedings of the International Workshop on DomAin Specific Model-Based AppRoaches to vErificaTion and validaTiOn). doi: 10.5220/0005854500830090

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

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this