Please use this identifier to cite or link to this item:
|Title:||Distinguishing Sequences for Distributed Testing: Preset Distinguishing Sequences|
|Keywords:||Finite state machine;Distributed test architecture;Preset distinguishing sequence|
|Publisher:||Oxford University Press (OUP)|
|Citation:||Computer Journal, 2016|
|Abstract:||There has been long-standing interest in automatically generating test sequences from a finite state machine (FSM) and more recently this has been extended to the case where there are multiple physically distributed testers and so we are testing from a multi-port FSM. This paper explores the problem of generating a controllable preset distinguishing sequence (PDS) from a multi-port FSM, motivated by the fact that many FSM-based test generation algorithms use PDSs. We prove that it is generally undecidable whether a multi-port FSM has a controllable PDS but provide a class of multi-port FSMs for which the problem is decidable. We also consider the important case where there is an upper bound ` on the length of PDSs of interest, proving that controllable PDS existence is PSPACE-hard and in EXPSPACE. In practice the upper bound ` is likely to be a polynomial in terms of the size of the multi-port FSM and in this case controllable PDS existence is NP- Complete.|
|Appears in Collections:||Dept of Computer Science Research Papers|
Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.