Journal article
On nonnegative integer matrices and short killing words
- Abstract:
- Let n be a natural number, and let \scrM be a set of n\times n-matrices over the nonnegative integers such that the joint spectral radius of \scrM is at most one. We show that if the zero matrix 0 is a product of matrices in \scrM , then there are M1, . . . , Mn5 \in \scrM with M1 \cdot \cdot \cdot Mn5 = 0. This result has applications in automata theory and the theory of codes. Specifically, if X \subset \Sigma \ast is a finite incomplete code, then there exists a word w \in \Sigma \ast of length polynomial in \sum x\in X | x| such that w is not a factor of any word in X\ast . This proves a weak version of Restivo's conjecture.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, 421.3KB, Terms of use)
-
- Publisher copy:
- 10.1137/19M1250893
Authors
- Publisher:
- Society for Industrial and Applied Mathematics
- Journal:
- SIAM Journal on Discrete Mathematics More from this journal
- Volume:
- 35
- Issue:
- 2
- Pages:
- 1252-1267
- Publication date:
- 2021-06-09
- Acceptance date:
- 2021-02-25
- DOI:
- Language:
-
English
- Keywords:
- Pubs id:
-
1163654
- Local pid:
-
pubs:1163654
- Deposit date:
-
2021-02-26
Terms of use
- Copyright holder:
- Society for Industrial Applied Mathematics
- Copyright date:
- 2021
- Rights statement:
- © 2021, Society for Industrial and Applied Mathematics.
- Notes:
- This is the accepted manuscript version of the article. The final version is available online from the Society for Industrial and Applied Mathematics at: https://doi.org/10.1137/19M1250893
If you are the owner of this record, you can report an update to it here: Report update to this record