Please use this identifier to cite or link to this item:
Title: Distinguishing Sequences for Distributed Testing: Preset Distinguishing Sequences
Authors: Hierons, RM
Turker, UC
Keywords: Finite state machine;Distributed test architecture;Preset distinguishing sequence
Issue Date: 2016
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.
ISSN: 1460-2067
Appears in Collections:Dept of Computer Science Research Papers

Files in This Item:
File Description SizeFormat 
FullText.pdf747.09 kBAdobe PDFView/Open

Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.