Please use this identifier to cite or link to this item:
|Title:||Incomplete distinguishing sequences for finite state machines|
|Keywords:||Model-based testing;Finite state machines;Testing;Checking experiments;Adaptive distinguishing sequences|
|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.|
|Appears in Collections:||Dept of Computer Science Research Papers|
Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.