Heuristics for deriving adaptive homing and distinguishing sequences for nondeterministic finite state machines

Kushik, Natalia and Yenigün, Hüsnü (2015) Heuristics for deriving adaptive homing and distinguishing sequences for nondeterministic finite state machines. In: 27th IFIP WG 6.1 International Conference on Testing Software and Systems (ICTSS), United Arab Emirates

[thumbnail of 47-Heuristics-for-Deriving-Adaptive-Homing-and-Distinguishing-Sequences.pdf] PDF
47-Heuristics-for-Deriving-Adaptive-Homing-and-Distinguishing-Sequences.pdf
Restricted to Repository staff only

Download (109kB) | Request a copy

Abstract

Distinguishing Sequences(DS)and Homing Sequences(HS)are used for state identification purposes in Finite State Machine (FSM) based testing. For deterministic FSMs, DS and HS related problems are well studied, for both preset and adaptive cases. There are also recent algorithms for checking the existence and constructing Adaptive DS and Adaptive HS for nondeterministic FSMs. However, most of the related problems are proven to be PSPACE-complete, while the worst case height of Adaptive DS and HS is known to be exponential. Therefore, novel heuristics and FSM classes where they can be applied need to be provided for effective derivation of such sequences. In this paper, we present a work in progress on the minimization of Adaptive DS and Adaptive HS for nondeterministic FSMs.
Item Type: Papers in Conference Proceedings
Uncontrolled Keywords: Nondeterministic finite state machines; Adaptive homing sequence; Adaptive distinguishing sequence; Novel heuristics
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 > Computer Science & Eng.
Faculty of Engineering and Natural Sciences
Depositing User: Hüsnü Yenigün
Date Deposited: 23 Jun 2016 15:50
Last Modified: 26 Apr 2022 09:22
URI: https://research.sabanciuniv.edu/id/eprint/29393

Actions (login required)

View Item
View Item