The detection and stabilisation of limit cycle for deterministic finite automata

ABSTRACT

In this paper, the topological structure properties of deterministic finite automata (DFA), under the framework of the semi-tensor product of matrices, are investigated. First, the dynamics of DFA are converted into a new algebraic form as a discrete-time linear system by means of Boolean algebra. Using this algebraic description, the approach of calculating the limit cycles of different lengths is given. Second, we present two fundamental concepts, namely, domain of attraction of limit cycle and prereachability set. Based on the prereachability set, an explicit solution of calculating domain of attraction of a limit cycle is completely characterised. Third, we define the globally attractive limit cycle, and then the necessary and sufficient condition for verifying whether all state trajectories of a DFA enter a given limit cycle in a finite number of transitions is given. Fourth, the problem of whether a DFA can be stabilised to a limit cycle by the state feedback controller is discussed. Criteria for limit cycle-stabilisation are established. All state feedback controllers which implement the minimal length trajectories from each state to the limit cycle are obtained by using the proposed algorithm. Finally, an illustrative example is presented to show the theoretical results.

KEYWORDS:

• Automata
• limit cycle
• domain of attraction
• limit cycle-stabilisation
• semi-tensor product (STP) of matrices

Acknowledgment

The authors would like to express sincere gratitude to the anonymous referees for their helpful comments and suggestins which improved the quality and readability of this paper, and also would like to thank the Editor-in-Chief and editors for their support in handling this paper.

Disclosure statement

No potential conflict of interest was reported by the authors.

Notes

1. A complete introduction about Boolean algebra can be found in Ross and Wright (2003).

Additional information

Funding

This work was supported in part by the National Natural Science Foundation of China [grant number 61573199], [grant number 61573200]; the Natural Science Foundation of Tianjin City [grant number 14JCYBJC18700], [grant number 13JCYBJC17400].