Abstract:

The compatible-invariant subset of deterministic finite automata (DFA) is investigated to solve the problem of subset stabilization under the frameworks of semi-tensor product (STP) of matrices. The concepts of compatible-invariant subset and largest compatible-invariant subset are introduced inductively for Moore-type DFA, and a necessary condition for the existence of largest compatible-invariant subset is given. Meanwhile, by using the STP of matrices, a compatible feasible event matrix is defined with respect to the largest compatible-invariant subset. Based on the concept of compatible feasible event matrix, an algorithm to calculate the largest compatible-invariant subset contained in a given subset is proposed. Finally, an illustrative example is given to validate the results.

Key words: discrete event dynamical systems (DEDSs), finite automata, compatible invariant, semi-tensor product (STP), compatible feasible event matrix