{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:39:09Z","timestamp":1787323149013,"version":"build-2736575974"},"reference-count":24,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/501100000288","name":"Royal Society","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000288","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>Let $n$ be a natural number, and let $\\mathcal{M}$ be a set of $n \\times n$-matrices over the nonnegative integers such that the joint spectral radius of $\\mathcal{M}$ is at most one. We show that if the zero matrix $0$ is a product of matrices in $\\mathcal{M}$, then there are $M_1, \\ldots, 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 of Restivo's conjecture.<\/jats:p>","DOI":"10.1137\/19m1250893","type":"journal-article","created":{"date-parts":[[2021,6,9]],"date-time":"2021-06-09T09:40:12Z","timestamp":1623231612000},"page":"1252-1267","source":"Crossref","is-referenced-by-count":2,"title":["On Nonnegative Integer Matrices and Short Killing Words"],"prefix":"10.1137","volume":"35","author":[{"given":"Stefan","family":"Kiefer","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Corto N.","family":"Mascle","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,6,9]]},"reference":[{"key":"atypb1","first-page":"153","volume":"24","author":"Ananichev D.","year":"2019","journal-title":"J. Autom. Lang. Comb."},{"key":"atypb2","first-page":"148","author":"Bell P.","year":"2012","journal-title":"Heidelberg"},{"key":"atypb3","first-page":"84","volume":"29","author":"Berstel J.","year":"1986","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci. EATCS"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"J. Berstel, D. Perrin, and C. Reutenauer,\n                      Codes and Automata\n                      , Encyclopedia Math. Appl. 129, Cambridge University Press, Cambridge, 2010.","DOI":"10.1017\/CBO9781139195768"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(88)90114-4"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.08.042"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(00)00314-1"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/1982160403651"},{"key":"atypb9","first-page":"239","author":"Gusev V.","year":"2011","journal-title":"Heidelberg"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054107005066"},{"key":"atypb11","unstructured":"R. Horn and C. Johnson,\n                      Matrix Analysis\n                      , 2nd ed., Cambridge University Press, Cambridge, 2013."},{"key":"atypb12","first-page":"271","volume":"22","author":"Julia S.","year":"2017","journal-title":"J. Autom. Lang. Comb."},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2007.08.001"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.07.049"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2008.03.020"},{"key":"atypb16","unstructured":"M. Mika and M. Szyku\u0142a,\n                      Complexity of the Frobenius Monoid Problem for a Finite Language\n                      , preprint,https:\/\/arxiv.org\/abs\/1902.06702, 2019."},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"M. Paterson,\n                      Unsolvability in 3 x 3 matrices\n                      , Studies in Appl. Math., 49 (1970), pp. 105-107.","DOI":"10.1002\/sapm1970491105"},{"key":"atypb18","first-page":"170","author":"Potapov I.","year":"2017","journal-title":"Philadelphia"},{"key":"atypb19","unstructured":"A. Restivo,\n                      Some remarks on complete subsets of a free monoid\n                      , in Noncommutative Structures in Algebra and Geometric Combinatorics, Quad. \u201cRicerca Sci.\u201d 109, CNR, Rome, 1981, pp. 19-25."},{"key":"atypb20","unstructured":"A. Ryzhikov and M. Szyku\u0142a,\n                      Finding short synchronizing words for prefix codes\n                      , in Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, LIPIcs. Leibniz Int. Proc. Inform. 117, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 21."},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(61)80020-X"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1137\/0221017"},{"key":"atypb23","first-page":"11","author":"Volkov M.","year":"2008","journal-title":"Berlin"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/1991250100191"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/19M1250893","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:44:44Z","timestamp":1787319884000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/19M1250893"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/19M1250893"],"URL":"https:\/\/doi.org\/10.1137\/19m1250893","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}