Analytic methods for reachability problems. (English) Zbl 1477.68159
Summary: We consider a function-analytic approach to study synchronizing automata, primitive and ergodic matrix families. This gives a new way to establish some criteria for primitivity and for ergodicity of families of nonnegative matrices. We introduce a concept of canonical partition and use it to construct a polynomial-time algorithm for finding a positive matrix product and an ergodic matrix product whenever they exist. This also provides a generalization of some results of the Perron-Frobenius theory from one nonnegative matrix to families of matrices. Then we define the \(h\)-synchronizing automata and prove that the existence of a reset tuple is polynomially decidable. The question whether the functional-analytic approach can be extended to the \(h\)-primitivity is addressed and several open problems are formulated.
MSC:
| 68Q45 | Formal languages and automata |
| 15B48 | Positive matrices and their generalizations; cones of matrices |
| 47H09 | Contraction-type mappings, nonexpansive mappings, \(A\)-proper mappings, etc. |
Keywords:
reachability problems; Perron-Frobenius theory; primitive matrix; synchronizing automata; functional equation; contraction; affine operatorReferences:
| [1] | Alpin, Yu. A.; Alpina, V. S., Combinatorial properties of irreducible semigroups of nonnegative matrices, J. Math. Sci. (N. Y.), 191, 1, 4-9 (2013) · Zbl 1276.15015 |
| [2] | Alpin, Yu. A.; Alpina, V. S., Combinatorial properties of entire semigroups of nonnegative matrices, J. Math. Sci. (N. Y.), 207, 674-685 (2015) · Zbl 1332.15090 |
| [3] | Alpin, Yu. A.; Alpina, V. S., A new proof of the Protasov—Voynov theorem on semigroups of nonnegative matrices, Math. Notes, 105, 805-811 (2019) · Zbl 1426.15013 |
| [4] | Ananichev, D. S.; Volkov, M. V.; Gusev, V. V., Primitive digraphs with large exponents and slowly synchronizing automata, J. Math. Sci., 192, 263-278 (2013) · Zbl 1276.68089 |
| [5] | Berlinkov, M. V.; Szykuła, M., Algebraic synchronization criterion and computing reset words, Inf. Sci., 369, 718-730 (2016) · Zbl 1428.68192 |
| [6] | Blondel, V. D.; Jungers, R. M.; Olshevsky, A., On primitivity of sets of matrices, Automatica, 61, 80-88 (2015) · Zbl 1337.15024 |
| [7] | Azfar, U.; Catalano, C.; Charlier, L.; Jungers, R. M., A linear bound on the k-rendezvous time for primitive sets of NZ matrices, Fundam. Inform., XXI, 1-26 (2020) |
| [8] | Catalano, C.; Jungers, R. M., On Random primitive sets, directable NFAs and the generation of slowly synchronizing DFAs, J. Autom. Lang. Comb., 24, 2-4, 185-217 (2019) · Zbl 1429.68103 |
| [9] | Cavaretta, A. S.; Dahmen, W.; Micchelli, C. A., Stationary subdivision, Mem. Am. Math. Soc., 93, 453 (1991) · Zbl 0741.41009 |
| [10] | Chevalier, P.-Y.; Hendrickx, J. M.; Jungers, R. M., Reachability of consensus and synchronizing automata, (Proceedings of 54th IEEE Conference on Decision and Control. Proceedings of 54th IEEE Conference on Decision and Control, CDC (2015)) · Zbl 1320.93073 |
| [11] | Cohen, J. E.; Sellers, P. H., Sets of nonnegative matrices with positive inhomogeneous products, Linear Algebra Appl., 47, 185-192 (1982) · Zbl 0495.15013 |
| [12] | Eppstein, D., Reset sequences for monotonic automata, SIAM J. Comput., 19, 3, 500-510 (1990) · Zbl 0698.68058 |
| [13] | Fornasini, E., 2D Markov chains, Linear Algebra Appl., 140, 101-127 (1990) · Zbl 0707.60062 |
| [14] | Fornasini, E.; Valcher, M., Directed graphs, 2D state models and characteristic polynomials of irreducible matrix pairs, Linear Algebra Appl., 263, 275-310 (1997) · Zbl 0887.93033 |
| [15] | Fornasini, E.; Valcher, M., A polynomial matrix approach to the structural properties of 2D positive systems, Linear Algebra Appl., 413, 2-3, 458-473 (2006) · Zbl 1103.93016 |
| [16] | Gao, Y.; Shao, Y., Generalized exponents of primitive two-colored digraphs, Linear Algebra Appl., 430, 5-6, 1550-1565 (2009) · Zbl 1171.05018 |
| [17] | Gerencsér, B.; Gusev, V. V.; Jungers, R. M., Primitive sets of nonnegative matrices and synchronizing automata, SIAM J. Matrix Anal. Appl., 39, 1, 83-98 (2018) · Zbl 1378.15020 |
| [18] | Gusev, V. V., Lower bounds for the length of reset words in Eulearian automata, Int. J. Found. Comput. Sci., 24, 2, 251-262 (2013) · Zbl 1295.68144 |
| [19] | Gusev, V. V.; Jungers, R. M.; Pribavkina, E. V., Generalized primitivity of labelled digraphs, Electron. Notes Discrete Math., 61, 549-555 (2017) · Zbl 1379.05047 |
| [20] | Hajnal, J., Weak ergodicity in nonhomogeneous Markov chains, Proc. Camb. Philos. Soc., 54, 233-246 (1958) · Zbl 0082.34501 |
| [21] | Hajnal, J., On products of nonnegative matrices, Math. Proc. Camb. Philos. Soc., 79, 3, 521-530 (1976) · Zbl 0333.15013 |
| [22] | Hartfiel, D. J., Nonhomogeneous Matrix Products (2002), World Scientific Publishing Co., Inc.: World Scientific Publishing Co., Inc. River Edge, NJ · Zbl 1011.15006 |
| [23] | Hennion, H., Limit theorems for products of positive random matrices, Ann. Probab., 25, 4, 1545-1587 (1997) · Zbl 0903.60027 |
| [24] | Jungers, R. M.; Protasov, V. Yu., Lower and upper bounds for the largest Lyapunov exponent of matrices, Linear Algebra Appl., 438, 4448-4468 (2013) · Zbl 1281.65154 |
| [25] | Kohavi, Z., Switching and Finite Automata Theory (1970), McGraw-Hill: McGraw-Hill New York · Zbl 0206.47701 |
| [26] | Micchelli, C. A.; Prautzsch, H., Uniform refinement of curves, Linear Algebra Appl., 114-115, 841-870 (1989) · Zbl 0668.65011 |
| [27] | Olesky, D. D.; Shader, B.; van den Driessche, P., Exponents of tuples of nonnegative matrices, Linear Algebra Appl., 356, 1-3, 123-134 (2002) · Zbl 1018.15018 |
| [28] | Paz, A., Definite and quasidefinite sets of stochastic matrices, Proc. Am. Math. Soc., 16, 4, 634-641 (1965) · Zbl 0149.13404 |
| [29] | Protasov, V. Yu., Extremal \(L_p\)-norms of linear operators and self-similar functions, Linear Algebra Appl., 428, 10, 2339-2356 (2008) · Zbl 1147.15023 |
| [30] | Protasov, V. Yu., Semigroups of nonnegative matrices, Russ. Math. Surv., 65, 6, 1186-1188 (2010) · Zbl 1217.20037 |
| [31] | Protasov, V. Yu., Classification of k-primitive sets of matrices, SIAM J. Matrix Anal., 34, 3, 1174-1188 (2013) · Zbl 1281.15039 |
| [32] | Protasov, V. Yu., Asymptotics of products of nonnegative random matrices, Funct. Anal. Appl., 47, 2, 138-147 (2013) · Zbl 1312.15053 |
| [33] | Protasov, V. Yu.; Voynov, A. S., Sets of nonnegative matrices without positive products, Linear Algebra Appl., 437, 3, 749-765 (2012) · Zbl 1245.15033 |
| [34] | Romanovsky, V., Un théorème sur les zéros des matrices non négatives, Bull. Soc. Math. Fr., 61, 213-219 (1933) · JFM 59.0112.02 |
| [35] | Sarymsakov, T. A., Inhomogeneous Markov chains, Teor. Veroâtn. Primen., 6, 194-201 (1961) · Zbl 0121.35305 |
| [36] | Schneider, H., The concepts of irreducibility and full indecomposability of a matrix in the works of Frobenius, König and Markov, Linear Algebra Appl., 18, 139-162 (1977) · Zbl 0365.15009 |
| [37] | Trahtman, A. N., The Černý conjecture for aperiodic automata, Discret. Math. Theor. Comput. Sci., 9, 2, 3-10 (2007) · Zbl 1152.68461 |
| [38] | Voynov, A. S.; Protasov, V. Yu., Compact noncontraction semigroups of affine operators, Sb. Math., 206, 7, 921-940 (2015) · Zbl 1341.47048 |
| [39] | Voynov, A. S., Shortest positive products of nonnegative matrices, Linear Algebra Appl., 439, 6, 1627-1634 (2013) · Zbl 1283.15111 |
| [40] | Volkov, M. V., Synchronizing automata and the Černý conjecture, Language and Automata Theory and Applications. Language and Automata Theory and Applications, Lecture Notes in Comput. Sci., vol. 5196, 11-27 (2008), Springer: Springer Berlin · Zbl 1156.68466 |
| [41] | Wu, Y.; Xu, Z.; Zhu, Y., An expansion property of Boolean linear maps, Electron. J. Linear Algebra, 31, 381-407 (2016) · Zbl 1339.05164 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
