On finite monoids over nonnegative integer matrices and short Killing words. (English) Zbl 07559152
Niedermeier, Rolf (ed.) et al., 36th international symposium on theoretical aspects of computer science, STACS 2019, March 13–16, 2019, Berlin, Germany. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 126, Article 43, 13 p. (2019).
Summary: Let \(n\) be a natural number and \(\mathcal{M}\) a set of \(n\times n\)-matrices over the nonnegative integers such that \(\mathcal{M}\) generates a finite multiplicative monoid. We show that if the zero matrix \(\mathbf{0}\) is a product of matrices in \(\mathcal{M}\), then there are \(M_1,\dots,M_{n^5}\in\mathcal{M}\) with \(M_1\cdots M_{n^5}= 0\). This result has applications in automata theory and the theory of codes. Specifically, if \(X\subset\Sigma^*\) is a finite incomplete code, then there exists a word \(w\in\Sigma^*\) of length polynomial in \(\sum_{x\in X}|x|\) such that \(w\) is not a factor of any word in \(X^*\). This proves a weak version by A. Restivo’s conjecture [Quad. Ric. Sci. 109, 19-25 (1981; Zbl 0517.20035)].
For the entire collection see [Zbl 1411.68018].
For the entire collection see [Zbl 1411.68018].
MSC:
| 68Qxx | Theory of computing |
Citations:
Zbl 0517.20035References:
| [1] | P.C. Bell, M. Hirvensalo, and I. Potapov. Mortality for 2 ×2 Matrices Is NP-Hard. In Pro-ceedings of Mathematical Foundations of Computer Science (MFCS), pages 148-159. Springer, 2012. · Zbl 1365.68265 |
| [2] | J. Berstel and D. Perrin. Trends in the theory of codes. Bulletin of the EATCS, 29:84-95, 1986. · Zbl 1022.94506 |
| [3] | J. Berstel, D. Perrin, and C. Reutenauer. Codes and Automata. Cambridge University Press, 2009. |
| [4] | A. Carpi. On synchronizing unambiguous automata. Theoretical Computer Science, 60(3):285-296, 1988. · Zbl 0665.68044 |
| [5] | A. Carpi and F. D’Alessandro. On incomplete and synchronizing finite sets. Theoretical Computer Science, 664:67-77, 2017. · Zbl 1359.68161 |
| [6] | P. Goralčík, Z. Hedrlín, V. Koubek, and J. Ryšlinková. A game of composing binary relations. R.A.I.R.O. Informatique théorique, 16(4):365-369, 1982. · Zbl 0509.05011 |
| [7] | V.V. Gusev and E.V. Pribavkina. On Non-complete Sets and Restivo’s Conjecture. In Proceedings of Developments in Language Theory (DLT), pages 239-250. Springer, 2011. · Zbl 1221.68180 |
| [8] | V. Halava, T. Harju, and M. Hirvensalo. Undecidability Bounds for Integer Matrices Using Claus Instances. International Journal of Foundations of Computer Science, 18(5):931-948, 2007. · Zbl 1202.03052 |
| [9] | R.A. Horn and C.R. Johnson. Matrix analysis. Cambridge University Press, 2nd edition, 2013. · Zbl 1267.15001 |
| [10] | S. Julia, A. Malapert, and J. Provillard. A Synergic Approach to the Minimal Uncompletable Words Problem. Journal of Automata, Languages and Combinatorics, 22(4):271-286, 2017. · Zbl 1390.68400 |
| [11] | R.M. Jungers, V. Protasov, and V.D. Blondel. Efficient algorithms for deciding the type of growth of products of integer matrices. Linear Algebra and its Applications, 428(10):2296-2311, 2008. · Zbl 1145.65030 |
| [12] | J.-Y. Kao, N. Rampersad, and J. Shallit. On NFAs where all states are final, initial, or both. Theoretical Computer Science, 410(47):5010-5021, 2009. · Zbl 1194.68140 |
| [13] | P.V. Martugin. A series of slowly synchronizing automata with a zero state over a small alphabet. Information and Computation, 206(9-10):1197-1203, 2008. · Zbl 1151.68029 |
| [14] | M.S. Paterson. Unsolvability in 3 × 3 Matrices. Studies in Applied Mathematics, 49(1):105-107, 1970. · Zbl 0186.01103 |
| [15] | I. Potapov and P. Semukhin. Decidability of the Membership Problem for 2 × 2 integer matrices. In Proceedings of the Symposium on Discrete Algorithms (SODA), pages 170-186. SIAM, 2017. · Zbl 1410.68245 |
| [16] | A. Restivo. Some remarks on complete subsets of a free monoid. In Quaderni de “La Ricerca Scientifica”. Non-Commutative Structures in Algebra and Geometric Combinatorics, volume 109, pages 19-25. Consiglio Nazionale Delle Ricerche, 1981. · Zbl 0517.20035 |
| [17] | A. Ryzhikov and M. Szykuła. Finding Short Synchronizing Words for Prefix Codes. In Proceedings of Mathematical Foundations of Computer Science (MFCS), volume 117 of LIPIcs, pages 21:1-21:14, 2018. · Zbl 1510.68041 |
| [18] | M.-P. Schützenberger. On the definition of a family of automata. Information and Control, 4:245-270, 1961. · Zbl 0104.00702 |
| [19] | W. Tzeng. A Polynomial-Time Algorithm for the Equivalence of Probabilistic Automata. SIAM Journal on Computing, 21(2):216-227, 1992. · Zbl 0755.68075 |
| [20] | M.V. Volkov. Synchronizing Automata and the Černý Conjecture. In Proceedings of Language and Automata Theory and Applications (LATA), pages 11-27. Springer, 2008. · Zbl 1156.68466 |
| [21] | A. Weber and H. Seidl. On finitely generated monoids of matrices with entries in N. Inform-atique Théorique et Applications, 25(1):19-38, 1991. · Zbl 0721.20042 |
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.
