License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2019.43
URN: urn:nbn:de:0030-drops-102823
URL: https://drops.dagstuhl.de/opus/volltexte/2019/10282/
Kiefer, Stefan ;
Mascle, Corto
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.
BibTeX - Entry
@InProceedings{kiefer_et_al:LIPIcs:2019:10282,
author = {Stefan Kiefer and Corto Mascle},
title = {{On Finite Monoids over Nonnegative Integer Matrices and Short Killing Words}},
booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
pages = {43:1--43:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-100-9},
ISSN = {1868-8969},
year = {2019},
volume = {126},
editor = {Rolf Niedermeier and Christophe Paul},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10282},
doi = {10.4230/LIPIcs.STACS.2019.43},
annote = {Keywords: matrix semigroups, unambiguous automata, codes, Restivo's conjecture}
}
|
Keywords: |
|
matrix semigroups, unambiguous automata, codes, Restivo's conjecture |
|
Collection: |
|
36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
12.03.2019 |
