Hardness and inapproximability of minimizing adaptive distinguishing sequences

Türker, Uraz Cengiz and Yenigün, Hüsnü (2014) Hardness and inapproximability of minimizing adaptive distinguishing sequences. Formal Methods in System Design, 44 (3). pp. 264-294. ISSN 0925-9856 (Print) 1572-8102 (Online)

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

Abstract

An adaptive distinguishing sequence (ADS) can be used for identifying an unknown initial state of a finite state machine (FSM). It has been long known that checking the existence of an ADS for an FSM, and finding an ADS for an FSM when one exists, can be performed in polynomial time. However, the problem of finding a minimum ADS has not been studied so far. Generating a minimum ADS is especially motivated when such an ADS is used repeatedly, e.g. for the construction of a test sequence. We introduce a number of metrics to define a minimum ADS and show that the problem of generating a minimum ADS with respect to these metrics is NP-complete. In addition, we provide inapproximability results for these hard problems and show that not only deciding but also approximating such a minimum ADS is a hard problem. We modify the only polynomial time ADS generation algorithm existing, and experimentally show that these modifications construct reduced ADSs. We also validate the motivation of ADS minimization by presenting experimental results on the effect of using reduced ADSs to generate test sequences.
Item Type: Article
Uncontrolled Keywords: Formal testing; Finite state machine based testing; State identification; Adaptive distinguishing sequences
Subjects: Q Science > QA Mathematics > QA076 Computer software
Divisions: 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: 23 Nov 2014 21:03
Last Modified: 02 Aug 2019 09:59
URI: https://research.sabanciuniv.edu/id/eprint/24481

Actions (login required)

View Item
View Item