Conference item
On finite monoids over nonnegative integer matrices and short killing words
- Abstract:
- Let n be a natural number and M a set of n x n-matrices over the nonnegative integers such that M generates a finite multiplicative monoid. We show that if the zero matrix 0 is a product of matrices in M, then there are M_1, ..., M_{n^5} in M with M_1 *s 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.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, pdf, 478.3KB, Terms of use)
-
- Publisher copy:
- 10.4230/LIPIcs.STACS.2019.43
Authors
- Publisher:
- Schloss Dagstuhl
- Host title:
- 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
- Journal:
- STACS 2019 More from this journal
- Volume:
- 126
- Pages:
- 43:1--43:13
- Series:
- Leibniz International Proceedings in Informatics
- Publication date:
- 2019-03-12
- Acceptance date:
- 2018-12-20
- DOI:
- ISSN:
-
1868-8969
- ISBN:
- 9783959771009
- Keywords:
- Pubs id:
-
pubs:954605
- UUID:
-
uuid:3f920bd5-f99a-446a-b9e3-b778105561a1
- Local pid:
-
pubs:954605
- Source identifiers:
-
954605
- Deposit date:
-
2018-12-23
Terms of use
- Copyright holder:
- Kiefer and Mascle
- Copyright date:
- 2019
- Notes:
- Copyright © Stefan Kiefer and Corto Mascle; licensed under Creative Commons License CC-BY.
- Licence:
- CC Attribution (CC BY)
If you are the owner of this record, you can report an update to it here: Report update to this record