Effective algorithms for constructing minimum cost adaptive distinguishing sequences

Türker, Uraz Cengiz and Ünlüyurt, Tonguç and Yenigün, Hüsnü (2016) Effective algorithms for constructing minimum cost adaptive distinguishing sequences. Information and Software Technology, 74 . pp. 69-85. ISSN 0950-5849 (Print) 1873-6025 (Online)

This is the latest version of this item.

Full text not available from this repository. (Request a copy)

Abstract

Context: Given a Finite State Machine (FSM), a checking sequence is a test sequence that determines whether the system under test is correct as long as certain standard assumptions hold. Many checking sequence generation methods use an adaptive distinguishing sequence (ADS), which is an experiment that distinguishes the states of the specification machine. Furthermore, it has been shown that the use of shorter ADSs yields shorter checking 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. This motivates studying and investigating effective ADS construction methods. Objective: The main objective of this paper is to suggest new methods that can compute compact ADSs to be used in the construction of checking sequences. Method: We briefly present the existing ADS construction algorithms. We then propose generalizations of these approaches with a set of heuristics. We also conduct experiments to compare the size of the resultant ADSs and the length of the checking sequences constructed using these ADSs. Results: The results indicate that when the ADSs are constructed with the proposed methods, the length of the checking sequences may reduce up to 54% (40% on the average). Conclusions: In this paper, we present the state of the art ADS construction methods for FSMs and we propose generalizations of these methods. We show that our methods are effective in terms of computation time and ADS quality.
Item Type: Article
Uncontrolled Keywords: Finite State Machines; Adaptive distinguishing sequences; Checking sequences
Subjects: Q Science > QA Mathematics > QA075 Electronic computers. Computer science
Q Science > QA Mathematics > QA076 Computer software
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Industrial Engineering
Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng.
Faculty of Engineering and Natural Sciences
Depositing User: Hüsnü Yenigün
Date Deposited: 15 Jul 2016 11:27
Last Modified: 22 May 2019 13:38
URI: https://research.sabanciuniv.edu/id/eprint/29390

Available Versions of this Item

Actions (login required)

View Item
View Item