Compatible-invariant subset analysis of deterministic finite automata via semi-tensor product of matrices approach

摘要

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 compatibleinvariant 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.