Conference item icon

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...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
Publisher copy:
10.4230/LIPIcs.STACS.2019.43

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Oxford college:
St John's College
Role:
Author
ORCID:
0000-0003-4173-6877
Publisher:
Schloss Dagstuhl Publisher's website
Journal:
STACS 2019 Journal website
Volume:
126
Pages:
43:1--43:13
Series:
Leibniz International Proceedings in Informatics
Host title:
36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Publication date:
2019-03-12
Acceptance date:
2018-12-20
DOI:
ISSN:
1868-8969
Source identifiers:
954605
ISBN:
9783959771009
Keywords:
Pubs id:
pubs:954605
UUID:
uuid:3f920bd5-f99a-446a-b9e3-b778105561a1
Local pid:
pubs:954605
Deposit date:
2018-12-23

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP