On Nonnegative Integer Matrices and Short Killing Words

DOI10.1137/19M1250893zbMath1486.20081arXiv1808.00940MaRDI QIDQ4992844

Corto N. Mascle, Stefan Kiefer

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

matrix semigroupscodesunambiguous automataRestivo's conjecture

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On incomplete and synchronizing finite sets
• A series of slowly synchronizing automata with a zero state over a small alphabet
• On NFAs where all states are final, initial, or both
• On synchronizing unambiguous automata
• Efficient algorithms for deciding the type of growth of products of integer matrices
• Mortality for 2 ×2 Matrices Is NP-Hard
• UNDECIDABILITY BOUNDS FOR INTEGER MATRICES USING CLAUS INSTANCES
• On the definition of a family of automata
• Synchronizing Automata and the Černý Conjecture
• A Polynomial-Time Algorithm for the Equivalence of Probabilistic Automata
• Decidability of the Membership Problem for 2 × 2 integer matrices
• A Synergic Approach to the Minimal Uncompletable Words Problem
• On Non-complete Sets and Restivo’s Conjecture
• Unsolvability in 3 × 3 Matrices
• On finitely generated monoids of matrices with entries in $\mathbb {N}$
• Corrigendum/addendum to: Sets of matrices all infinite products of which converge

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