Decreasing the length of adaptive distinguishing experiments for nondeterministic merging-free finite state machines

Nina Yevtushenko; Natalia Kushik

doi:10.1109/EWDTS.2015.7493120

Decreasing the length of adaptive distinguishing experiments for nondeterministic merging-free finite state machines

Nina Yevtushenko, Natalia Kushik

Tomsk State University

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

Abstract

Adaptive distinguishing experiments with nondeterministic Finite State Machines (FSMs) are widely used for deriving tests with the guaranteed fault coverage for reactive discrete event systems. For test minimization, adaptive distinguishing sequences of minimal length that distinguish as many states as possible are most interesting. However, it is known that in general, the length of an (adaptive) input sequence distinguishing states of a nondeterministic FSM can be exponential with respect to the number of FSM states. This paper is devoted to deriving adaptive distinguishing sequences for a nondeterministic FSM of a special class with the length that is polynomial with respect to the number of FSM states.

Original language	English
Title of host publication	Proceedings of 2015 IEEE East-West Design and Test Symposium, EWDTS 2015
Publisher	Institute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)	9781467377751
DOIs	https://doi.org/10.1109/EWDTS.2015.7493120
Publication status	Published - 15 Jun 2016
Externally published	Yes
Event	2015 IEEE East-West Design and Test Symposium, EWDTS 2015 - Batumi, Georgia Duration: 26 Sept 2015 → 29 Sept 2015

Publication series

Name	Proceedings of 2015 IEEE East-West Design and Test Symposium, EWDTS 2015

Conference

Conference	2015 IEEE East-West Design and Test Symposium, EWDTS 2015
Country/Territory	Georgia
City	Batumi
Period	26/09/15 → 29/09/15

Access to Document

10.1109/EWDTS.2015.7493120

Cite this

Yevtushenko, N., & Kushik, N. (2016). Decreasing the length of adaptive distinguishing experiments for nondeterministic merging-free finite state machines. In Proceedings of 2015 IEEE East-West Design and Test Symposium, EWDTS 2015 Article 7493120 (Proceedings of 2015 IEEE East-West Design and Test Symposium, EWDTS 2015). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/EWDTS.2015.7493120

@inproceedings{352014e09a9f4ae387f4d134da342416,

title = "Decreasing the length of adaptive distinguishing experiments for nondeterministic merging-free finite state machines",

abstract = "Adaptive distinguishing experiments with nondeterministic Finite State Machines (FSMs) are widely used for deriving tests with the guaranteed fault coverage for reactive discrete event systems. For test minimization, adaptive distinguishing sequences of minimal length that distinguish as many states as possible are most interesting. However, it is known that in general, the length of an (adaptive) input sequence distinguishing states of a nondeterministic FSM can be exponential with respect to the number of FSM states. This paper is devoted to deriving adaptive distinguishing sequences for a nondeterministic FSM of a special class with the length that is polynomial with respect to the number of FSM states.",

author = "Nina Yevtushenko and Natalia Kushik",

note = "Publisher Copyright: {\textcopyright} 2015 IEEE.; 2015 IEEE East-West Design and Test Symposium, EWDTS 2015 ; Conference date: 26-09-2015 Through 29-09-2015",

year = "2016",

month = jun,

day = "15",

doi = "10.1109/EWDTS.2015.7493120",

language = "English",

series = "Proceedings of 2015 IEEE East-West Design and Test Symposium, EWDTS 2015",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

booktitle = "Proceedings of 2015 IEEE East-West Design and Test Symposium, EWDTS 2015",

}

Yevtushenko, N & Kushik, N 2016, Decreasing the length of adaptive distinguishing experiments for nondeterministic merging-free finite state machines. in Proceedings of 2015 IEEE East-West Design and Test Symposium, EWDTS 2015., 7493120, Proceedings of 2015 IEEE East-West Design and Test Symposium, EWDTS 2015, Institute of Electrical and Electronics Engineers Inc., 2015 IEEE East-West Design and Test Symposium, EWDTS 2015, Batumi, Georgia, 26/09/15. https://doi.org/10.1109/EWDTS.2015.7493120

Decreasing the length of adaptive distinguishing experiments for nondeterministic merging-free finite state machines. / Yevtushenko, Nina; Kushik, Natalia.
Proceedings of 2015 IEEE East-West Design and Test Symposium, EWDTS 2015. Institute of Electrical and Electronics Engineers Inc., 2016. 7493120 (Proceedings of 2015 IEEE East-West Design and Test Symposium, EWDTS 2015).

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

TY - GEN

T1 - Decreasing the length of adaptive distinguishing experiments for nondeterministic merging-free finite state machines

AU - Yevtushenko, Nina

AU - Kushik, Natalia

PY - 2016/6/15

Y1 - 2016/6/15

N2 - Adaptive distinguishing experiments with nondeterministic Finite State Machines (FSMs) are widely used for deriving tests with the guaranteed fault coverage for reactive discrete event systems. For test minimization, adaptive distinguishing sequences of minimal length that distinguish as many states as possible are most interesting. However, it is known that in general, the length of an (adaptive) input sequence distinguishing states of a nondeterministic FSM can be exponential with respect to the number of FSM states. This paper is devoted to deriving adaptive distinguishing sequences for a nondeterministic FSM of a special class with the length that is polynomial with respect to the number of FSM states.

AB - Adaptive distinguishing experiments with nondeterministic Finite State Machines (FSMs) are widely used for deriving tests with the guaranteed fault coverage for reactive discrete event systems. For test minimization, adaptive distinguishing sequences of minimal length that distinguish as many states as possible are most interesting. However, it is known that in general, the length of an (adaptive) input sequence distinguishing states of a nondeterministic FSM can be exponential with respect to the number of FSM states. This paper is devoted to deriving adaptive distinguishing sequences for a nondeterministic FSM of a special class with the length that is polynomial with respect to the number of FSM states.

U2 - 10.1109/EWDTS.2015.7493120

DO - 10.1109/EWDTS.2015.7493120

M3 - Conference contribution

AN - SCOPUS:84979266147

T3 - Proceedings of 2015 IEEE East-West Design and Test Symposium, EWDTS 2015

BT - Proceedings of 2015 IEEE East-West Design and Test Symposium, EWDTS 2015

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2015 IEEE East-West Design and Test Symposium, EWDTS 2015

Y2 - 26 September 2015 through 29 September 2015

ER -

Yevtushenko N, Kushik N. Decreasing the length of adaptive distinguishing experiments for nondeterministic merging-free finite state machines. In Proceedings of 2015 IEEE East-West Design and Test Symposium, EWDTS 2015. Institute of Electrical and Electronics Engineers Inc. 2016. 7493120. (Proceedings of 2015 IEEE East-West Design and Test Symposium, EWDTS 2015). doi: 10.1109/EWDTS.2015.7493120

Decreasing the length of adaptive distinguishing experiments for nondeterministic merging-free finite state machines

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this