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

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
Document type :
Conference papers
Complete list of metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-01262740
Contributor : Médiathèque Télécom Sudparis & Institut Mines-Télécom Business School <>
Submitted on : Friday, February 17, 2017 - 10:50:38 AM
Last modification on : Saturday, November 9, 2019 - 2:13:54 AM
Long-term archiving on: Thursday, May 18, 2017 - 2:13:18 PM

File

385214_1_En_15_Chapter.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Natalia Kushik, Husnu Yenigun. Heuristics for deriving adaptive homing and distinguishing sequences for nondeterministic finite state machines. 27th IFIP International Conference on Testing Software and Systems (ICTSS), Nov 2015, Sharjah And Dubai, United Arab Emirates. pp.243-248, ⟨10.1007/978-3-319-25945-1_15⟩. ⟨hal-01262740⟩

Share

Metrics

Record views

305

Files downloads

246