Hardness and inapproximability of minimizing adaptive distinguishing sequences

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 pr...

Full description

Saved in:
Bibliographic Details
Published in:Formal methods in system design 2014-06, Vol.44 (3), p.264-294
Main Authors: Tuerker, Uraz Cengiz, Yeniguen, Huesnue
Format: Article
Language:English
Subjects:
Algorithms
Approximation
CAE) and Design
Circuits and Systems
Computer-Aided Engineering (CAD
Construction
Electrical Engineering
Engineering
Formal method
Hardness
Optimization
Polynomials
Software Engineering/Programming and Operating Systems
Systems design
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0925-9856
1572-8102
DOI:10.1007/s10703-014-0205-0