Please use this identifier to cite or link to this item:
|Title:||Parallel algorithms for generating distinguishing sequences for observable non-deterministic FSMs|
|Keywords:||Verification;Finite state machine;Distinguishing sequences|
|Publisher:||Association for Computing Machinery (ACM)|
|Citation:||ACM Transactions on Software Engineering and Methodology, pp. 1-37, (2017)|
|Abstract:||A distinguishing sequence (DS) for a finite state machine (FSM) is an input sequence that distinguishes every pair of states of the FSM. There are techniques that generate a test sequence with guaranteed fault detection power and it has been found that shorter test sequence can be produced if DSs are used. Despite these benefits, however, until recently the only published DS generation algorithms have been for deterministic FSMs. This paper develops a massively parallel algorithm, which can be used in GPU Computing, to generate DSs from partial observable non-deterministic FSMs. We also present the results of experiments using randomly generated FSMs and some benchmark FSMs. The results are promising and indicate that the proposed algorithm can derive DSs from partial observable non-deterministic FSMs with 32,000 states in an acceptable amount of time.|
|Appears in Collections:||Dept of Computer Science Research Papers|
Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.