Generation of Checking Sequence
Abstract: Many systems in diverse areas
such as switching systems, telephony systems, communication protocols, lexical
analysis, pattern matching, and machine learning can be modeled by
deterministic Finite State Machines (FSM). Therefore, the test of these systems
can be done by verifying if the implementation M* of an FSM M is
equivalent to M. The focus of this method is how to generate a checking
sequence that can differentiate any implementation M*s not
equivalent to M and how to minimize the length of the checking sequence.
In recent years, there are
many progresses in the literature. Some new algorithms are proposed to generate
checking sequences with minimal length. In this presentation, the background
and some key issues of the literature will be introduced. After that, there
will be a brief review of those algorithms, especially the application of the
overlapping in minimizing the length of checking sequences. At the end, some
potential interests of further study will be discussed.