Hardness and inapproximability of minimizing adaptive distinguishing sequences

DOI10.1007/s10703-014-0205-0zbMath1317.68125OpenAlexW2016803840MaRDI QIDQ479811

Uraz Cengiz Türker, Hüsnü Yenigün

Publication date: 5 December 2014

Published in: Formal Methods in System Design (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10703-014-0205-0

zbMATH Keywords

state identificationadaptive distinguishing sequencesfinite state machine based testingformal testing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Specification and verification (program logics, model checking, etc.) (68Q60)

Related Items

Adaptive distinguishing test cases of nondeterministic finite state machines: test case derivation and length estimation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lower bounds on lengths of checking sequences
• Constructing optimal binary decision trees is NP-complete
• On the hardness of the minimum height decision tree problem
• Model-based testing of reactive systems. Advanced lectures.
• Decision trees for entity identification
• On minimizing the lengths of checking sequences
• Reduced length checking sequences
• Reset Sequences for Monotonic Automata
• Approximating Optimal Binary Decision Trees
• Testing Software Design Modeled by Finite-State Machines
• Preset and Adaptive Homing Experiments for Nondeterministic Finite State Machines
• Checking Completeness of Tests for Finite State Machines
• Testing finite-state machines: state identification and verification
• Formal Techniques for Networked and Distributed Systems – FORTE 2004
• A Method for the Design of Fault Detection Experiments