Primitive sets of nonnegative matrices and synchronizing automata

DOI10.1137/16M1094099MaRDI QIDQ3130423zbMATH OpenOpenAlexFDO

Authors Balázs Gerencsér, Raphaël M. Jungers, Vladimir V. Gusev

Publication date 22 January 2018

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

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

zbMATH Keywords

nonnegative matricesprimitive sets of matricesČerný conjecturecarefully synchronizing automataexponent of a matrix set

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Boolean and Hadamard matrices (15B34) Positive matrices and their generalizations; cones of matrices (15B48)

Abstract: A set of nonnegative matrices $mathcalM=M_1,M_2,ldots,M_k$ is called primitive if there exist indices $i_1,i_2,ldots,i_m$ such that $M_{i_1}{M}_{i_2}ldots{M}_{i_m}$ is positive (i.e. has all its entries $>0$). The length of the shortest such product is called the exponent of $mathcalM$. The concept of primitive sets of matrices comes up in a number of problems within control theory, non-homogeneous Markov chains, automata theory etc. Recently, connections between synchronizing automata and primitive sets of matrices were established. In the present paper, we significantly strengthen these links by providing equivalence results, both in terms of combinatorial characterization, and computational aspects. We study the maximal exponent among all primitive sets of $nimesn$ matrices, which we denote by $exp(n)$. We prove that $li{m}_{nightarrowinfty}fraclogexp(n)n=fraclog33$, and moreover, we establish that this bound leads to a resolution of the v{C}ern'{y} problem for carefully synchronizing automata. We also study the set of matrices with no zero rows and columns, denoted by $mathcalNZ$, due to its intriguing connections to the v{C}ern'{y} conjecture and the recent generalization of Perron-Frobenius theory for this class. We characterize computational complexity of different problems related to the exponent of $mathcalNZ$ matrix sets, and present a quadratic bound on the exponents of sets belonging to a special subclass. Namely, we show that the exponent of a set of matrices having total support is bounded by $2n^2-5n+5$.

Recommendations

• On primitivity of sets of matrices
• The Synchronizing Probability Function for Primitive Sets of Matrices
• The synchronizing probability function for primitive sets of matrices
• A Linear Bound on the k-rendezvous time for primitive sets of NZ matrices
• A linear bound on the \(k\)-rendezvous time for primitive sets of NZ matrices

Cites work

• scientific article; zbMATH DE number 1460605 (Why is no real title available?)
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• scientific article; zbMATH DE number 3222112 (Why is no real title available?)
• scientific article; zbMATH DE number 3354928 (Why is no real title available?)
• A lower bound for the length of the shortest carefully synchronizing words
• A note on a recent attempt to improve the Pin-Frankl bound
• An extremal problem for two families of sets
• Approximating minimum reset sequences
• Asymptotic estimate of the length of a diagnostic word for a finite automaton
• Between primitive and 2-transitive: synchronization and its friends
• Coefficients of ergodicity and the scrambling index
• Combinatorial matrix classes
• Combinatorial matrix theory
• Combinatorial properties of irreducible semigroups of nonnegative matrices
• Compact noncontraction semigroups of affine operators
• Computational Complexity
• Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata
• Concerning nonnegative matrices and doubly stochastic matrices
• Definite and Quasidefinite Sets of Stochastic Matrices
• Directable nondeterministic automata
• Directed graphs, 2D state models, and characteristic polynomials of irreducible matrix pairs
• Disjunctive networks and update schedules
• Improved upper bounds on synchronizing nondeterministic automata
• In extremal combinatorial problem associated with the bound on the length of a synchronizing word in an automaton
• Nonhomogeneous matrix products
• On primitivity of sets of matrices
• On two Combinatorial Problems Arising from Automata Theory
• Primitive digraphs with large exponents and slowly synchronizing automata
• Relationships between nondeterministic and deterministic tape complexities
• Reset Sequences for Monotonic Automata
• Sets of nonnegative matrices with positive inhomogeneous products
• Sets of nonnegative matrices without positive products
• Shortest positive products of nonnegative matrices
• Strong inapproximability of the shortest reset word
• Synchronizing Automata and the Černý Conjecture
• Synchronizing finite automata on Eulerian digraphs.
• The Distribution of Positive Elements in Doubly-Stochastic Matrices
• The complexity of finding reset words in finite automata
• The generalized competition indices of primitive minimally strong digraphs

Cited in

(15)

• A Linear Bound on the k-rendezvous time for primitive sets of NZ matrices
• An improved algorithm for finding the shortest synchronizing words
• The synchronizing probability function for primitive sets of matrices
• Recognition of matrices which are sign-regular of a given order and a generalization of oscillatory matrices
• Lower bounds for synchronizing word lengths in partial automata
• Primitivity and Hurwitz Primitivity of Nonnegative Matrix Tuples: A Unified Approach
• Analytic methods for reachability problems
• New characterizations of primitive permutation groups with applications to synchronizing automata
• Attainable values of reset thresholds
• On randomized generation of slowly synchronizing automata
• On primitivity of sets of matrices
• The Synchronizing Probability Function for Primitive Sets of Matrices
• Using SAT solvers for synchronization issues in non-deterministic automata
• On the interplay between Černý and Babai's conjectures
• A linear bound on the \(k\)-rendezvous time for primitive sets of NZ matrices

This page was built for publication: Primitive sets of nonnegative matrices and synchronizing automata

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