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

[thumbnail of 49-Some-Classes-of-Finite-State-Machines-with-Polynomial-Length-of-Distinguishing-Test-Cases.pdf] PDF
Restricted to Repository staff only

Download (843kB) | Request a copy


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
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng.
Faculty of Engineering and Natural Sciences
Depositing User: Hüsnü Yenigün
Date Deposited: 15 Jul 2016 15:47
Last Modified: 26 Apr 2022 09:22

Actions (login required)

View Item
View Item