@inproceedings{8cca2beec7994d62bef17b290553b128,
title = "Some classes of finite state machines with polynomial length of distinguishing test cases",
abstract = "The paper is devoted to effective check of the existence and derivation of adaptive distinguishing sequences (distinguishing test cases) for possibly nondeterministic partial Finite State Machines (FSMs). The complexity of these problems for nondeterministic FSMs remains unknown, however the length of the corresponding test case is shown to be exponential. In this paper, we address FSM classes that allow to derive specific FSM projections for which the problem of checking whether a given FSM is adaptively distinguishing or not can be performed in polynomial time. In order to estimate the length of distinguishing test cases for FSMs of these classes we improve the upper bound on the length of an adaptive distinguishing test case for partial deterministic FSMs. The listed contributions make it possible to apply the proposed techniques for testing 'real' technical systems which behavior is decribed by (partial) nondeterministic FSMs.",
keywords = "Adaptive distinguishability, Complexity, Heuristics, Nondeterministic finite state machine (FSM), Test case",
author = "H{\"u}sn{\"u} Yenig{\"u}n and Nina Yevtushenko and Natalia Kushik",
note = "Publisher Copyright: {\textcopyright} 2016 ACM.; 31st Annual ACM Symposium on Applied Computing, SAC 2016 ; Conference date: 04-04-2016 Through 08-04-2016",
year = "2016",
month = apr,
day = "4",
doi = "10.1145/2851613.2851835",
language = "English",
series = "Proceedings of the ACM Symposium on Applied Computing",
publisher = "Association for Computing Machinery",
pages = "1680--1685",
booktitle = "2016 Symposium on Applied Computing, SAC 2016",
}