On Nonnegative Integer Matrices and Short Killing Words

DOI10.1137/19M1250893MaRDI QIDQ4992844zbMATH OpenFDO

Authors Stefan Kiefer, Corto N. Mascle

Publication date 10 June 2021

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1808.00940

zbMATH Keywords

codesmatrix semigroupsRestivo's conjectureunambiguous automata

Mathematics Subject Classification ID

Semigroups of transformations, relations, partitions, etc. (20M20) Semigroups in automata theory, linguistics, etc. (20M35) Formal languages and automata (68Q45) Combinatorics in computer science (68R05)

Abstract: Let $n$ be a natural number and $mathcalM$ a set of $nimesn$-matrices over the nonnegative integers such that the joint spectral radius of $mathcalM$ is at most one. We show that if the zero matrix $0$ is a product of matrices in $mathcalM$, then there are $M_1,ldots,M_{n^5}inmathcalM$ with $M_{1}cdots{M}_{n^5}=0$. This result has applications in automata theory and the theory of codes. Specifically, if $XsubsetSigm{a}^{\ast }$ is a finite incomplete code, then there exists a word $winSigm{a}^{\ast }$ of length polynomial in $su{m}_{xinX}|x|$ such that $w$ is not a factor of any word in $X^{\ast }$. This proves a weak version of Restivo's conjecture.

Recommendations

• On finite monoids over nonnegative integer matrices and short killing words
• Non-overlapping matrices via Dyck words
• Enumeration of nonnegative integer matrices
• Total non-negativity of some combinatorial matrices
• On a combinatorial theorem and its application to nonnegative matrices
• Overlap-free words and spectra of matrices
• Factorizations of k-nonnegative matrices
• On Nonnegative matrices generating a finite multiplicative monoid
• Shortest positive products of nonnegative matrices
• Pascal matrices and restricted words

Cites work

• A new lower bound for reset threshold of binary synchronizing automata with sink
• A Polynomial-Time Algorithm for the Equivalence of Probabilistic Automata
• A series of slowly synchronizing automata with a zero state over a small alphabet
• A synergic approach to the minimal uncompletable words problem
• Codes and automata.
• Corrigendum/addendum to: Sets of matrices all infinite products of which converge
• Decidability of the membership problem for \(2\times 2\) integer matrices
• Efficient algorithms for deciding the type of growth of products of integer matrices
• Finding short synchronizing words for prefix codes
• scientific article; zbMATH DE number 3817996 (Why is no real title available?)
• scientific article; zbMATH DE number 1988973 (Why is no real title available?)
• scientific article; zbMATH DE number 3803447 (Why is no real title available?)
• scientific article; zbMATH DE number 6125590 (Why is no real title available?)
• Mortality for 2 2 matrices is NP-hard
• On finitely generated monoids of matrices with entries in $\mathbb {N}$
• On incomplete and synchronizing finite sets
• On NFAs where all states are final, initial, or both
• On non-complete sets and Restivo's conjecture
• On synchronizing unambiguous automata
• On the definition of a family of automata
• Synchronizing Automata and the Černý Conjecture
• Undecidability bounds for integer matrices using Claus instances
• Unsolvability in 3 × 3 Matrices

Cited in

(6)

• Minimal zero words for second-order matrices
• Extremal sequences of polynomial complexity
• On finite monoids over nonnegative integer matrices and short killing words
• Complexity results for a cops and robber game on directed graphs
• Monoids of upper triangular matrices over the Boolean semiring
• Title not available (Why is no real title available?)

This page was built for publication: On Nonnegative Integer Matrices and Short Killing Words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4992844)