Please use this identifier to cite or link to this item: http://buratest.brunel.ac.uk/handle/2438/11127
Title: Incomplete distinguishing sequences for finite state machines
Authors: Hierons, RM
Turker, UC
Keywords: Model-based testing;Finite state machines;Testing;Checking experiments;Adaptive distinguishing sequences
Issue Date: 2015
Publisher: Oxford University Press (OUP)
Citation: The Computer Journal, (2015)
Abstract: Given a Finite State Machine (FSM) M, a Distinguishing Sequence (DS) is a test that identifies the state of M. While there are two types of DSs, preset DSs (PDSs) and adaptive DSs (ADSs), not all FSMs possess a DS. In this paper, we examine the problem of finding incomplete PDSs and ADSs, exploring associated optimisation problems: finding a largest set of states that has a DS and finding a smallest set of DSs that, between them, distinguish all of the states. We also propose a greedy algorithm to produce a small set of incomplete ADSs and use experiments to compare this with two previously published algorithms for generating state identifiers. We show that the optimisation problems related to incomplete ADSs and PDSs are PSPACE-Complete as are corresponding approximation problems. In the experiments we found that incomplete ADSs produced by the proposed greedy algorithm led to relatively compact state identifiers.
URI: http://comjnl.oxfordjournals.org/content/early/2015/06/09/comjnl.bxv041.abstract
http://bura.brunel.ac.uk/handle/2438/11127
DOI: http://dx.doi.org/10.1093/comjnl/bxv041
ISSN: 1460-2067
Appears in Collections:Dept of Computer Science Research Papers

Files in This Item:
File Description SizeFormat 
Fulltext.pdf1.21 MBUnknownView/Open


Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.