Construction of Incompatible Graph of Finite State Machines Using the Theory of Semi-tensor Product of Matrices

In this paper we use the STP theory (semi-tensor product of matrices) to consider the construction of the incompatible graph of finite state machines (FSMs) in a mathematical manner. First, the output dynamics of FSMs are formulated as a bilinear dynamic equation by expressing output symbols as vectors and based on the state transition equation developed by the authors recently. Second, with the output dynamic equation, we design an algebraic algorithm for constructing the incompatible graph of an FSM, where some algebraic results proposed by the authors are used, such as, an algebraic criterion and an algorithm of determining whether a pair of states is k-difference in the sense of language recognition. Examples are given to verify these results.