SCIENCE CHINA Information Sciences, Volume 63 , Issue 2 : 129203(2020) https://doi.org/10.1007/s11432-018-9739-9

Three matrix conditions for the reduction of finite automata based on the theory of semi-tensor product of matrices

More info
  • ReceivedSep 12, 2018
  • AcceptedJan 11, 2019
  • PublishedAug 9, 2019


There is no abstract available for this article.


This work was supported by National Natural Science Foundation of China (Grant Nos. U1804150, 61573199) and 2018 Henan Province Science and Technique Foundation (Grant No. 182102210045).


Appendixes A and B.


[1] Almeida J, Zeitoun M. Description and analysis of a bottom-up DFA minimization algorithm. Inf Processing Lett, 2008, 107: 52-59 CrossRef Google Scholar

[2] David J. The average complexity of Moore's state minimization algorithm is O(nloglogn). Lecture Notes in Computer Science, 2010, 6281: 318-329. Google Scholar

[3] Peeva K. Equivalence, reduction and minimization of finite automata over semirings. Theor Comput Sci, 1991, 88: 269-285 CrossRef Google Scholar

[4] Lamperti G, Scandale M. Incremental determinization and minimization of finite acyclic automata. In: Proceedings of IEEE International Conference on Systems, Man, and Cybernetics, 2013. 2250--2257. Google Scholar

[5] Holzer M, Kutrib M. Descriptional and computational complexity of finite automata-A survey. Inf Computation, 2011, 209: 456-470 CrossRef Google Scholar

[6] Carrasco R C, Forcada M L. Incremental Construction and Maintenance of Minimal Finite-State Automata. Comput Linguistics, 2002, 28: 207-216 CrossRef Google Scholar

[7] Zhang Z, Chen Z, Liu Z. Modeling and reachability of probabilistic finite automata based on semi-tensor product of matrices. Sci China Inf Sci, 2018, 61: 129202 CrossRef Google Scholar

[8] Yue J M, Chen Z Q, Yan Y Y, et al. Solvability of k-track assignment problem: a graph approach. Control Theory and Applications, 2017, 34: 457-466. Google Scholar

[9] Cheng D Z, Qi H S, Zhao Y. An Introduction to Semi-Tensor Product of Matrices and Its Applications. Singapore: World Scientific Publishing, 2012. Google Scholar

[10] Aho A V, Sethi R, Ullman J D. Compilers, Principles, Techniques, and Tools. Boston: Addison-Wesley Publishing Corporation, 1986. Google Scholar

  • Figure 1

    (a) An example of FA; (b) reduced counterparts of the FA.