- No file added yet -
Distinguishing Sequences for Distributed Testing: Adaptive Distinguishing Sequences
journal contribution
posted on 2020-04-08, 15:39 authored by Robert M Hierons, Uraz Cengiz Türker- This paper concerns the problem of testing from a finite state machine (FSM) $M$ modelling a system that interacts with its environment at multiple physically distributed interfaces, called ports. We assume that the distributed test architecture is used: there is a local tester at each port, the tester at port $p$ only observes events at $p$ and the testers do not interact during testing. This paper formalizes the notion of an adaptive test strategy and what it means for an adaptive test strategy to be controllable. We provide algorithms to check whether a global strategy is controllable and to generate a controllable adaptive distinguishing sequence (ADS). We prove that controllable ADS existence is PSPACE-Hard and that the problem of deciding whether $M$ has a controllable ADS with length $\ell $ is NP-Hard. In practice, there is likely to be a polynomial upper bound on the length of ADS in which we are interested and for this case the decision problem is NP-Complete.
History
Citation
The Computer Journal ( Volume: 59 , Issue: 8 , Aug. 2016 )Version
- AM (Accepted Manuscript)
Published in
The Computer JournalVolume
59Issue
8Pagination
1186 - 1206Publisher
Oxford University Press (OUP)issn
0010-4620eissn
1460-2067Copyright date
2016Available date
2016-08-01Publisher DOI
Publisher version
https://ieeexplore.ieee.org/abstract/document/8204584Language
enUsage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC