Adaptive distinguishing test cases of nondeterministic finite state machines: test case derivation and length estimation

作     者：El-Fakih, Khaled Yevtushenko, Nina Kushik, Natalia 

作者机构：Amer Univ Sharjah POB 26666 Sharjah U Arab Emirates Tomsk State Univ Tomsk Russia RAS Inst Syst Programming Moscow Russia Univ Paris Saclay CNRS SAMOVAR Telecom SudParis Evry France 

出 版 物：《FORMAL ASPECTS OF COMPUTING》 (计算形式问题)

年 卷 期：2018年第30卷第2期

页      面：319-332页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：AUS [FRG-15-R27] Russian Science Foundation (RSF) [16-49-03012] Russian Science Foundation [16-49-03012] Funding Source: Russian Science Foundation 

主　　题：Adaptive distinguishing experiments Nondeterministic finite state machines Finite state machine based testing 

摘      要：A top-down approach is presented for checking the existence and derivation of an adaptive distinguishing test case (called also an adaptive distinguishing sequence) for a nondeterministic finite state machine (NDFSM). When such a test case exists, the method returns a canonical test case that includes all other distinguishing tests of the given complete observable NDFSM. In the second part of the paper, a constructive approach is provided for deriving a class of complete observable NDFSMs with n states, n 2, and 2 (n) - n - 1 inputs such that a shortest adaptive distinguishing test case for each NDFSM in the intended class has the length (height) 2 (n) - n - 1. In other words, we prove the reachability of the exponential upper bound on the length of a shortest adaptive distinguishing sequence for complete observable NDFSMs while for deterministic machines the upper bound is polynomial with respect to the number of states. For constructing the intended class of NDFSMs for a given n, we propose a special linear order over all the non-empty subsets without singletons of an n-element set. The obtained tight exponential upper bound initiates further research on identifying certain NDFSM classes where this upper bound is not reachable.