文章基本信息

标题：On Finite Monoids over Nonnegative Integer Matrices and Short Killing Words
本地全文：下载
作者：Stefan Kiefer ; Corto Mascle
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：126
页码：1-13
DOI：10.4230/LIPIcs.STACS.2019.43
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：matrix semigroups; unambiguous automata; codes; Restivo's conjecture