Lookahead-Based Approaches for Minimizing Adaptive Distinguishing Sequences

Abstract : For Finite State Machine (FSM) based testing, it has been shown that the use of shorter Adaptive Distinguishing Sequences (ads) yields shorter test sequences. It is also known, on the other hand, that constructing a minimum cost ADS is an NP-hard problem and it is NP-hard to approximate. In this paper, we introduce a lookahead-based greedy algorithm to construct reduced ADSs for FSMs. The greedy algorithm inspects a search space to make a decision. The size of the search space is adjustable, allowing a trade-off between the quality and the computation time. We analyse the performance of the approach on randomly generated FSMs by comparing the ADSs constructed by our algorithm with the ADSs that are computed by the existing algorithms.
Document type :
Conference papers
Mercedes G. Merayo; Edgardo Montes Oca. 26th IFIP International Conference on Testing Software and Systems (ICTSS), Sep 2014, Madrid, Spain. Springer, Lecture Notes in Computer Science, LNCS-8763, pp.32-47, 2014, Testing Software and Systems. 〈10.1007/978-3-662-44857-1_3〉
Liste complète des métadonnées

Cited literature [29 references]  Display  Hide  Download

https://hal.inria.fr/hal-01405273
Contributor : Hal Ifip <>
Submitted on : Tuesday, November 29, 2016 - 4:39:05 PM
Last modification on : Tuesday, November 29, 2016 - 4:48:50 PM
Document(s) archivé(s) le : Monday, March 27, 2017 - 8:24:16 AM

File

978-3-662-44857-1_3_Chapter.pd...
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Uraz Türker, Tonguç Ünlüyurt, Hüsnü Yenigün. Lookahead-Based Approaches for Minimizing Adaptive Distinguishing Sequences. Mercedes G. Merayo; Edgardo Montes Oca. 26th IFIP International Conference on Testing Software and Systems (ICTSS), Sep 2014, Madrid, Spain. Springer, Lecture Notes in Computer Science, LNCS-8763, pp.32-47, 2014, Testing Software and Systems. 〈10.1007/978-3-662-44857-1_3〉. 〈hal-01405273〉

Share

Metrics

Record views

74

Files downloads

22