Some classes of finite state machines with polynomial length of distinguishing test cases

Yenigün, Hüsnü and Yevtushenko, Nina and Kushik, Natalia (2016) Some classes of finite state machines with polynomial length of distinguishing test cases. In: 31st Annual ACM Symposium on Applied Computing (SAC'16), Pisa, Italy

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

Official URL: http://dx.doi.org/10.1145/2851613.2851835


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.

Item Type:Papers in Conference Proceedings
Uncontrolled Keywords:Adaptive distinguishability; Complexity; Heuristics; Nondeterministic finite state machine (FSM); Test case
Subjects:Q Science > QA Mathematics > QA075 Electronic computers. Computer science
Q Science > QA Mathematics > QA076 Computer software
ID Code:29401
Deposited By:Hüsnü Yenigün
Deposited On:15 Jul 2016 15:47
Last Modified:15 Jul 2016 15:47

Repository Staff Only: item control page