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

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collection › Contribution à une conférence › Revue par des pairs

Résumé

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.

langue originale	Anglais
titre	Proceedings of 2015 IEEE East-West Design and Test Symposium, EWDTS 2015
Editeur	Institute of Electrical and Electronics Engineers Inc.
ISBN (Electronique)	9781467377751
Les DOIs	https://doi.org/10.1109/EWDTS.2015.7493120
état	Publié - 15 juin 2016
Modification externe	Oui
Evénement	2015 IEEE East-West Design and Test Symposium, EWDTS 2015 - Batumi, Géorgie Durée: 26 sept. 2015 → 29 sept. 2015

Série de publications

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

Une conférence

Une conférence	2015 IEEE East-West Design and Test Symposium, EWDTS 2015
Pays/Territoire	Géorgie
La ville	Batumi
période	26/09/15 → 29/09/15

Accès au document

10.1109/EWDTS.2015.7493120

Contient cette citation

Yevtushenko, N., & Kushik, N. (2016). Decreasing the length of adaptive distinguishing experiments for nondeterministic merging-free finite state machines. Dans 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. Dans 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, Géorgie, 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).

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collection › Contribution à une conférence › Revue par des pairs

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. Dans 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

Résumé

Série de publications

Une conférence

Accès au document

Empreinte digitale

Contient cette citation