A Linear Bound on the k-rendezvous Time for Primitive Sets of NZ Matrices

• Autorzy: Catalano Costanza , Azfar Umer , Charlier Ludovic , Jungers Raphaël M.

Identyfikatory

DOI

10.3233/FI-2021-2043

• Języki publikacji: EN

Abstrakty

EN

A set of nonnegative matrices is called primitive if there exists a product of these matrices that is entrywise positive. Motivated by recent results relating synchronizing automata and primitive sets, we study the length of the shortest product of a primitive set having a column or a row with k positive entries, called its k-rendezvous time (k-RT), in the case of sets of matrices having no zero rows and no zero columns. We prove that the k-RT is at most linear w.r.t. the matrix size n for small k, while the problem is still open for synchronizing automata. We provide two upper bounds on the k-RT: the second is an improvement of the first one, although the latter can be written in closed form. We then report numerical results comparing our upper bounds on the k-RT with heuristic approximation methods.

Słowa kluczowe

EN

primitive set of matrices; matrix semigroups; synchronizing automaton; Černý conjecture

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 180, nr 4
• Strony: 289--314
• Opis fizyczny: Bibliogr. 50 poz., rys., wykr.

Twórcy

autor

Catalano Costanza

• Department of Economics, Statistics and Research, Banca d’Italia (Central Bank of Italy), Largo Guido Carli 1, 00044 Frascati, Roma, Italy

autor

Azfar Umer

• ICTEAM, Université Catholique de Louvain, Avenue Georges Lemaîtres 4-6, Louvain-la-Neuve, Belgium

autor

Charlier Ludovic

• ICTEAM, Université Catholique de Louvain, Avenue Georges Lemaîtres 4-6, Louvain-la-Neuve, Belgium

autor

Jungers Raphaël M.

• ICTEAM, Université Catholique de Louvain, Avenue Georges Lemaîtres 4-6, Louvain-la-Neuve, Belgium

Bibliografia

• [1] Protasov VY, Voynov AS. Sets of nonnegative matrices without positive products. Linear Algebra and its Applications, 2012. 437:749-765. doi:10.1016/j.laa.2012.02.029.
• [2] Hennion H. Limit theorems for products of positive random matrices. The Annals of Probability, 1997. 25(4):1545-1587. doi:10.1214/aop/1023481103.
• [3] Protasov VY. Invariant functions for the Lyapunov exponents of random matrices. Sbornik: Mathematics, 2011. 202(1):101. doi:10.1070/sm2011v202n01abeh004139.
• [4] Hartfiel DJ. Nonhomogeneous matrix products. World Scientific Publishing, 2002. ISBN-9789810246280.
• [5] Seneta E. Non-negative Matrices and Markov Chains. Springer-Verlag New York, 2 edition, 1981. ISBN-978-0-387-32792-1. doi:10.1007/0-387-32792-4.
• [6] Chevalier PY, Hendrickx JM, Jungers RM. Reachability of consensus and synchronizing automata. In: IEEE Conference in Decision and Control. 2015 pp. 4139-4144. doi:10.1109/CDC.2015.7402864.
• [7] Fomichev VM, Avezova YE, Koreneva AM, Kyazhin SN. Primitivity and Local Primitivity of Digraphs and Nonnegative Matrices. J. of App. and Industrial Math., 2018. 12(3):453-469. doi:10.1134/S1990478918030067.
• [8] Blondel V, Jungers RM, Olshevsky A. On primitivity of sets of matrices. Automatica, 2015. 61:80-88. doi:10.1016/j.automatica.2015.07.026.
• [9] Gerencsér B, Gusev VV, Jungers RM. Primitive sets of nonnegative matrices and synchronizing automata. Siam J. on Matrix An. and Appl., 2018. 39(1):83-98. doi:10.1137/16M1094099.
• [10] Catalano C, Jungers RM. On randomized generation of slowly synchronizing automata. In: Mathematical Foundations of Computer Science. 2018 pp. 48:1-48:21. URL http://drops.dagstuhl.de/opus/volltexte/2018/9630/.
• [11] Catalano C, Jungers RM. On random primitive sets, directable NFAs and the generation of slowly synchronizing DFAs. Journal of Automata, Languages and Combinatorics, 2019. 24:185-217. doi:10.25596/jalc-2019-185.
• [12] Hajnal J. On products of non-negative matrices. Mathematical Proceedings of the Cambridge Philosophical Society, 1976. 79(3):521-530. doi:10.1017/S030500410005252X.
• [13] Catalano C, Jungers RM. The Synchronizing Probability Function for primitive sets of matrices. In: Developments in Language Theory. ISBN-978-3-319-98654-8, 2018 pp. 194-205.
• [14] Catalano C, Jungers RM. The Synchronizing Probability Function for primitive sets of matrices. International J. of Foundations of Computer Science, 2020. Accepted.
• [15] Eppstein D. Reset Sequences for Monotonic Automata. SIAM J. on Computing, 1990. 19(3):500-510. doi:10.1137/0219033.
• [16] Chen YB, Ierardi DJ. The complexity of oblivious plans for orienting and distinguishing polygonal parts. Algorithmica, 1995. 14(5):367-397. doi:10.1007/BF01192046.
• [17] Mateescu A, Salomaa A. Many-valued truth functions, Černý’s conjecture and road coloring. In: EATCS Bulletin. ISBN- 952-12-0450-8, 1999 pp. 134-150.
• [18] Natarajan BK. An Algorithmic Approach to the Automated Design of Parts Orienters. In: SFCS. 1986 pp. 132-142. doi:10.1109/SFCS.1986.5.
• [19] Schützenberger M. On the synchronizing properties of certain prefix codes. Information and Control, 1964. 7(1):23-36. doi:10.1016/S0019-9958(64)90232-3.
• [20] Biskup M, Plandowski W. Shortest synchronizing strings for Huffman codes. Theor. Comput. Sci., 2009. 410:3925-3941. doi:doi.org/10.1016/j.tcs.2009.06.005.
• [21] Volkov MV. Synchronizing automata and the Černý conjecture. In: Language and Automata Theory and Applications. 2008 pp. 11-27. doi:10.1007/978-3-540-88282-4_4.
• [22] Gawrychowski P, Straszak D. Strong inapproximability of the shortest reset word. In: Mathematical Foundations of Computer Sciences, volume 9234. 2015 pp. 243-255. doi:10.1007/978-3-662-48057-1_19.
• [23] Černý J, Pirická A, Rosenaurová B. On directable automata. Kybernetika, 1971. pp. 289-298.
• [24] Starke PH. Eine Bemerkung über homogene Experimente. J. Inf. Process. Cybern., 1966. 2:257-259.
• [25] Starke PH. A Remark About Homogeneous Experiments. Journal of Automata, Languages and Combinatorics, 2019. 24(2-4):133-137. doi:10.25596/jalc-2019-133.
• [26] Volkov MV. Preface. Journal of Automata, Languages and Combinatorics, 2019. 24(2-4):119-121. doi:10.25596/jalc-2019-119.
• [27] Černý J. Poznámka k homogénnym eksperimentom s konečnými automatami. Matematicko-fysikalny Casopis SAV, 1964. 14(14):208-216.
• [28] Černý J. A Note on Homogeneous Experiments with Finite Automata. Journal of Automata, Languages and Combinatorics, 2019. 24(2-4):123-132. doi:10.25596/jalc-2019-123.
• [29] Ananichev DS, Gusev VV. Approximation of Reset Thresholds with Greedy Algorithms. Fundamenta Informaticae, 2016. 145(3):221-227. doi:10.3233/FI-2016-1357.
• [30] Bondt MD, Don H, Zantema H. Lower Bounds for Synchronizing Word Lengths in Partial Automata. Int. J. Found. Comput. Sci., 2019. 30:29-60. doi:10.1142/S0129054119400021.
• [31] Kisielewicz A, Kowalski J, Szykuła M. Experiments with synchronizing automata. In: Implementation and application of automata, volume 9705. 2016 pp. 176-188. doi:10.1007/978-3-319-40946-7_15.
• [32] Trahtman A. Notable trends concerning the synchronization of graphs and automata. Electronic Notes in Discrete Mathematics, 2006. 25:173-175. doi:10.1016/j.endm.2006.06.072.
• [33] Kari J. Synchronizing finite automata on Eulerian digraphs. Theoretical Computer Science, 2003. 295(1):223-232. doi:10.1007/3-540-44683-4_38.
• [34] Steinberg B. The Averaging Trick and the Černý Conjecture. In: Developments in Language Theory. 2010 pp. 423-431. doi:10.1142/S0129054111008970.
• [35] Volkov M. Synchronizing automata preserving a chain of partial orders. Theoretical Computer Science, 2009. 410(37):3513-3519. doi:10.1016/j.tcs.2009.03.021.
• [36] Pin JE. On two combinatorial problems arising from automata theory. In: International Colloquium on Graph Theory and Combinatorics, volume 75. 1983 pp. 535-548. doi:10.1016/S0304-0208(08)73432-7.
• [37] Frankl P. An extremal problem for two families of sets. European J. of Combinatorics, 1982. 3(3):125-127. doi:10.1016/S0195-6698(82)80025-5.
• [38] Szykuła M. Improving the upper bound the length of the shortest reset words. In: Symposium on Theoretical Aspects of Computer Science, volume 96. 2018 pp. 56:1-56:16. doi:10.4230/LIPIcs.STACS.2018.56.
• [39] Gonze F, Gusev VV, Gerencsér B, Jungers RM, Volkov MV. On the Interplay Between Babai and Černý’s Conjectures. In: Developments in Language Theory. 2017 pp. 185-197. doi:10.1142/S0129054119400057.
• [40] Dzyga M, Ferens R, Gusev VV, Szykuła M. Attainable Values of Reset Thresholds. In: Math. Foundations of Comp. Scien., volume 83. 2017 pp. 40:1-40:14. doi:10.4230/LIPIcs.MFCS.2017.40.
• [41] Rystsov IK. Reset words for commutative and solvable automata. Theoretical Computer Science, 1997. 172(1):273-279. doi:10.1016/S0304-3975(96)00136-3.
• [42] Kisielewicz A, Szykuła M. Synchronizing Automata with Extremal Properties. In: Mathematical Foundations of Computer Sciences. 2015 pp. 331-343. doi:10.1007/978-3-662-48057-1_26.
• [43] Ananichev DS, Volkov MV, Gusev VV. Primitive digraphs with large exponents and slowly synchronizing automata. J. of Math. Sci., 2013. 192(3):263-278. doi:10.1007/s10958-013-1392-8.
• [44] Paterson M. Unsolvability in 3x3 Matrices. Studies in Applied Mathematics, 1996. 49(1):105-107. doi:10.1002/sapm1970491105.
• [45] Potapov I, Semukhin P. Decidability of the Membership Problem for 2x2 Integer Matrices. In: ACM-SIAM Symposium on Discrete Algorithms. 2017 pp. 170-186. doi:10.1137/1.9781611974782.12.
• [46] Gonze F, Jungers RM. On the Synchronizing Probability Function and the Triple Rendezvous Time. In: Language and Automata Theory and Appl. 2015 pp. 212-223. doi:10.1007/978-3-319-15579-1_16.
• [47] Azfar U, Catalano C, Charlier L, Jungers R. A linear bound on the k-rendezvous time for primitive sets of NZ matrices. In: Developments in Language Theory, volume 11647. 2019 pp. 59-73. doi:10.1007/978-3-030-24886-4_4.
• [48] Al’pin YA, Al’pina VS. Combinatorial properties of irreducible semigroups of nonnegative matrices. J. of Mathematical Sciences, 2013. 191(1):4-9.
• [49] Kari J. A Counter Example to a Conjecture Concerning Synchronizing Words in Finite Automata. Bulletin of the EATCS, 2001. 73:146.
• [50] Shitov Y. An Improvement to a Recent Upper Bound for Synchronizing Words of Finite Automata. Journal of Automata, Languages and Combinatorics, 2019. 24:367-373. doi:10.25596/jalc-2019-367.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).