Lookahead-based approaches for minimizing adaptive distinguishing sequences

Türker, Uraz Cengiz and Ünlüyurt, Tonguç and Yenigün, Hüsnü (2014) Lookahead-based approaches for minimizing adaptive distinguishing sequences. In: 26th IFIP International Conference on Testing Software and Systems, Madrid, Spain

Full text not available from this repository.

Official URL: http://dx.doi.org/10.1007/978-3-662-44857-1_3


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.

Item Type:Papers in Conference Proceedings
Uncontrolled Keywords:Finite State Machines, Adaptive Distinguishing Sequences, Greedy algorithms
Subjects:Q Science > QA Mathematics > QA076 Computer software
ID Code:24484
Deposited By:Hüsnü Yenigün
Deposited On:08 Dec 2014 11:23
Last Modified:02 Aug 2019 10:32

Repository Staff Only: item control page