Approximation Algorithm for finding UIO Sequences
Step 1. Set length bound of search in UIO algorithm.
Step 2. Remove all convergent edges, and find shortest
paths from states without UIO to any states with
Step 3. construct signatures as UIOs for those states that
can’t find UIO in Step 1 and Step 2.
Time complexity is O( ), with the upper bound of UIO
length is n+1,where L is the given search bound, n is the
number of states, m is the number of transitions, and dmax
is the maximum outdegree.
*This algorithm appeared in
H. E. Wang, W. H. Chen and C. Y. Tang ,“An
approximation algorithm for obtaining UIO sequences
from the FSM model of a protocol.” Proc. of 1993 int’l
Symposium on Communications, Vol. 2/16, pp 28-34.