Title :
LANG - algorithm for constructing unique input/output sequences in finite-state machines
Author :
Ahmad, I. ; Ali, F.M. ; Das, A.S.
Author_Institution :
Dept. of Comput. Eng., Kuwait Univ., Safat, Kuwait
fDate :
3/19/2004 12:00:00 AM
Abstract :
Finite-state-machines (FSMs) model a variety of hardware and software systems. Unique input/output (UIO) sequences are used in generation of test sequences to verify that a machine is in an expected state, which in turn ensures system reliability. The paper presents an efficient algorithm for computing UIO sequences for completely and incompletely specified FSMs with binary inputs. Set of states which produces identical outputs for nonconflicting inputs are partitioned by incrementally constructing a successor tree. The transitions of FSM are modified to create a set of more specified transitions. This also resulted in constructing UIO sequences for an additional number of states. By a heuristic breadth-first search of successor tree, shorter test sequences are generated. In addition, classifying the nodes as ´active´, ´inactive´ and ´dead´ and application of pruning rules and termination checks applied while partitioning the states reduced the search space and speeded up UIO-sequence construction. A chain-node search technique was used when successor tree failed to construct UIO sequences in some FSMs. The proposed algorithm, designated LANG, was tested with a large number of FSMs including the MCNC FSM benchmarks. To show the effectiveness of the proposed algorithm, results are compared with existing UIO-sequence-computation algorithms. The proposed algorithm computed shorter UIO sequences in negligible CPU time.
Keywords :
binary sequences; finite state machines; program verification; sequential machines; tree searching; FSM transitions; algorithm termination check; binary input; chain-node search technique; finite-state machine; heuristic breadth-first search; pruning rules; search space; successor tree; system reliability; test sequence generation; unique input/output sequence computation algorithm;
Journal_Title :
Computers and Digital Techniques, IEE Proceedings -
DOI :
10.1049/ip-cdt:20040350