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

doi:10.19682/j.cnki.1005-8885.2018.0028

中国邮电高校学报(英文) ›› 2018, Vol. 25 ›› Issue (5): 75-82.doi: 10.19682/j.cnki.1005-8885.2018.0028

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

张志鹏¹,陈增强¹,刘忠信²

1. 南开大学
2. 南开大学自动化系

收稿日期:2018-05-29 修回日期:2018-07-23 出版日期:2018-10-18 发布日期:2018-10-18
通讯作者: 陈增强 E-mail:chenzq@nankai.edu.cn
基金资助:
国家自然科学基金项目;国家自然科学基金项目

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

Received:2018-05-29 Revised:2018-07-23 Online:2018-10-18 Published:2018-10-18
Contact: Chen Zeng-Qiang E-mail:chenzq@nankai.edu.cn

摘要/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.

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

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

参考文献

1. Feng L, Wonham W M. Supervisory control of architecture for discrete-event systems. IEEE Transactions on Automatic Control, 2008, 53(6): 1449–1461

2. Zhang Z P, Chen Z Q, Han X G, et al. On the static output feedback stabilization of deterministic finite automata based upon the approach of semi-tensor product of matrix. Kybernetika, 2018, 54(1): 41–60

3. Su R, Schuppen J, Rooda J. Model abstraction of nondeterministic finite-state automata in supervisor synthesis. IEEE Transactions on Automatic Control, 2010, 55(11): 2527–2541

4. Cao Y Z, Ezawa Y. Nondeterministic fuzzy automata. Information Sciences. 2016, 191: 86–97

5. Cassandras C, Lafortune S. Introduction to discrete event system. 2nd ed. New York, NY, USA: Springer Science and Business Media, 2008

6. Kobetski A, Fabian M. Time-optimal coordination of flexible manufacturing systems using deterministic finite automata and mixed integer linear programming. Discrete Event Dynamic Systems, 2009, 19(3): 287–315

7. Xu X R, Hong Y G. Matrix expression and reachability analysis of finite automata. Journal of Control Theory and Applications, 2012, 10(2): 210–215

8. Cheng D Z. Semi-tensor product of matrices and its application to Morgen’s problem. Science in China Series: Information Sciences, 2001, 44(3): 195–212

9. Bof N, Fornasini E, Valcher M. Output feedback stabilization of Boolean control networks. Automatica, 2015, 57: 21–28

10. Li F F, Yu Z X. Feedback control and output feedback control for the stabilisation of switched Boolean networks. International Journal of Control, 2016, 89(2): 337–342

11. Li H T, Wang Y Z, Guo P L. State feedback based output tracking control of probabilistic Boolean networks. Information Sciences, 2016, 349/350: 1–11

12. Liu Y, Li B, Lu J Q, et al. Pinning control for the disturbance decoupling problem of Boolean networks. IEEE Transactions on Automatic Control, 2017, 62(12): 6595–6601

13. Meng M, Lam J, Feng J E, et al. l₁-gain analysis and model reduction problem for Boolean control networks. Information Sciences, 2016, 348: 68–83

14. Zhang K Z, Zhang L J. Observability of boolean control networks: A unified approach based on finite automata. IEEE Transactions on Automatic Control, 2016, 61(9): 2733–2738

15. Cheng D Z, He F H, Qi H S, et al. Modeling, analysis and control of networked evolutionary games. IEEE Transactions on Automatic Control, 2015, 60(9): 2402–2415

16. Gao N, Han X G, Chen Z Q, et al. Modeling and reachability analysis of synchronizing transitions bounded Petri net systems based upon semi-tensor product of matrices. Journal of China Universities of Posts and Telecommunications, 2017, 24(1): 77–86

17. Han X G, Chen Z Q, Liu Z X, et al. Calculation of siphons and minimal siphons in Petri nets based on semi-tensor product of matrices. IEEE Transactions on Systems, Man and Cybernetics: Systems, 2017, 47(3): 531–536

18. Wu Y H, Shen T L. Policy iteration approach to control residual gas fraction in IC engines under the framework of stochastic logical dynamics. IEEE Transactions on Control Systems Technology, 2017, 25(3): 1100–1107

19. Xu X R, Hong Y G. Observability analysis and observer design for finite automata via matrix approach. IET Control Theory and Application, 2013, 7(12): 1609–1615

20. Han X G, Chen Z Q, Liu Z X, et al. The detection and stabilisation of limit cycle for deterministic finite automata. International Journal of Control, 2018, 91(4): 874–886

21. Yan Y Y, Chen Z Q, Liu Z X. Verification analysis of self-verifying automata via semi-tensor product of matrices. Journal of China Universities of Posts and Telecommunications, 2014, 21(4): 96–104

22. Guo Y Q, Wang P, Gui W H, et al. Set stability and set stabilization of boolean control networks based on invariant subsets. Automatica, 2015, 61: 106–112

23. Guo Y Q, Ding Y, Xie D. Invariant subset and set stability of boolean networks under arbitrary switching signals. IEEE Transactions on Automatic Control, 2017, 62(8): 4209–4214

24. Ozveren C, Willsky A. Output stabilizability of discrete event dynamic systems. IEEE Transactions on Automatic Control, 1991, 36(8): 925–935

25. Syrmos V, Abdallah C, Dorato P, et al. Static output feedback— A survey. Automatica, 1997, 33(2): 125–137

26. Cheng D Z, Qi H S. A linear representation of dynamics of Boolean networks. IEEE Transactions on Automatic Control, 2010, 55(10): 2251–2258

Ross K, Wright C. Discrete mathematics. 5th ed. New York, NY, USA: Prentice Hall, 2003

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

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

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

编辑推荐

Metrics

本文评价