Studing non-separability relation for non-deterministic finite statemachines with time-outs

In this paper we consider one of the classical finite state machine (FSM) model modification -FSM with time-outs (or timed FSM). In this model in addition to the ordinary transitions underinputs there are transitions under time-outs when no input is applying. So there is no externalstimulus in case of transitions under time-outs, and thus timed FSMs gives an opportunity to describethe behavior of many modern systems, for example, mobile phones, mp3-players, etc.In the past few years some papers have been carried out on studying different relations betweentimed FSMs. Most of these relations and their properties are inherited from the classicalFSM model. Non-separability relation, that is studied in this paper, is also adapted from FSMstheory, or, to be more precise, from FSMs with non-deterministic behavior. This relation is veryattractive for non-deterministic classical FSMs and FSMs with time-outs course for this relationwe don't need «all weather conditions» while testing, i.e. it is not necessary to input every sequencefrom the test suite enough times in order to observe all outputs of the system to this sequence.Practical implementation of this assumption is almost impossible, and so test suite derivationwith respect to the non-separability relation is actual for non-deterministic classical FSMsand their modifications.In this paper we present an algorithm for constructing a separating sequence for two separableFSMs with time-outs, and with the help of this algorithm one can derive a complete test suite fortimed FSM with respect to the non-separability relation in case of explicit faults enumeration. Theresults presented in the paper can be extended in different ways, for example, they can be appliedfor construction of test for timed FSMs whicht don't need «all weather conditions» and explicitfaults enumerations for timed FSMs.

Keywords

Authors

References