University of Leicester
Browse

Distinguishing Sequences for Distributed Testing: Adaptive Distinguishing Sequences

Download (1.02 MB)
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 Journal

Volume

59

Issue

8

Pagination

1186 - 1206

Publisher

Oxford University Press (OUP)

issn

0010-4620

eissn

1460-2067

Copyright date

2016

Available date

2016-08-01

Publisher version

https://ieeexplore.ieee.org/abstract/document/8204584

Language

en

Usage metrics

    University of Leicester Publications

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC