Paper Info
Title
Fast state verification
Abstract
Unique input/output (UIO) sequences are used for state verification and functional test in finite state machines. A UIO sequence for a state s distinguishes it from other states in the FSM. Current algorithms to compute UIO sequences are limited in their applicability to FSMs with binary input symbols such as those found in control applications. Execution times of traditional approaches are exponential in the number of FSM inputs. We develop a new heuristic algorithm to generate UIO sequences for FSMs with binary inputs. Execution time is reduced significantly by reducing the size of the search space. When a UIO sequence cannot be generated, our algorithm generates a small number of functional faults for state verification.
Year
DOI
Venue
1998
10.1145/277044.277205
DAC
Keywords
Field
DocType
execution time,finite state machines,uio sequence,finite state machine,binary input symbols,fast state verification,functional test,binary input symbol,model checking,fsm input,binary inputs,verification,heuristic algorithm,guided search,heuristic programming,current algorithm,functional fault,binary input,state verification,functional faults,formal verification,unique input/output sequences,sun,protocols,functional testing,search space,computer networks,testing,automata,input output
Model checking,Exponential function,Computer science,Heuristic (computer science),Algorithm,Theoretical computer science,Real-time computing,Finite-state machine,Execution time,Heuristic programming,Binary number,Formal verification
Conference
ISBN
Citations 
PageRank 
0-89791-964-5
4
0.48
References 
Authors
12
3
Name
Order
Citations
PageRank
Dechang Sun1323.17
Bapiraju Vinnakota223725.36
Wanli Jiang31139.16