Heuristics for unique input output sequence computation

Abstract

In this thesis, several heuristic methods are proposed for the computation of Unique Input Output (UIO) Sequences for the states of a given finite state machine. UIO computation problem is known to be a hard problem. The methods suggested in this work are based on unfolding an exponential tree as the other methods existing in the literature. However, our methods perform a search guided by some heuristic information. We also introduce a parameter for inference based UIO sequence computation for a trade off between the memory used for the computation and the UIO sequence length. Based on a randomly generated set of finite state machines, an extensive experimental study is also provided to compare the performance of our methods between each other and to those already exist in the literature.