Please use this identifier to cite or link to this item:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorHierons, RM-
dc.contributor.authorTurker, UC-
dc.identifier.citationComputer Journal, 2016en_US
dc.description.abstractThere 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.en_US
dc.publisherOxford University Press (OUP)-
dc.subjectFinite state machineen_US
dc.subjectDistributed test architectureen_US
dc.subjectPreset distinguishing sequenceen_US
dc.titleDistinguishing Sequences for Distributed Testing: Preset Distinguishing Sequencesen_US
dc.relation.isPartOfThe Computer Journal-
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.