Primitive Sets of Nonnegative Matrices and Synchronizing Automata

DOI10.1137/16M1094099zbMath1378.15020arXiv1602.07556OpenAlexW2284475030MaRDI QIDQ3130423

Raphaël M. Jungers, Balázs Gerencsér, 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 matricesČerný conjectureprimitive sets of matricescarefully synchronizing automataexponent of a matrix set

Mathematics Subject Classification ID

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

Related Items (12)

Primitivity and Hurwitz Primitivity of Nonnegative Matrix Tuples: A Unified Approach ⋮ Using SAT solvers for synchronization issues in non-deterministic automata ⋮ New characterizations of primitive permutation groups with applications to synchronizing automata ⋮ Unnamed Item ⋮ Lower Bounds for Synchronizing Word Lengths in Partial Automata ⋮ On the Interplay Between Černý and Babai’s Conjectures ⋮ A Linear Bound on the k-rendezvous Time for Primitive Sets of NZ Matrices ⋮ Analytic methods for reachability problems ⋮ Synchronization problems in automata without non-trivial cycles ⋮ Attainable Values of Reset Thresholds ⋮ 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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Combinatorial properties of irreducible semigroups of nonnegative matrices
• Primitive digraphs with large exponents and slowly synchronizing automata
• Disjunctive networks and update schedules
• Sets of nonnegative matrices without positive products
• A lower bound for the length of the shortest carefully synchronizing words
• On primitivity of sets of matrices
• The generalized competition indices of primitive minimally strong digraphs
• Improved upper bounds on synchronizing nondeterministic automata
• Coefficients of ergodicity and the scrambling index
• An extremal problem for two families of sets
• Sets of nonnegative matrices with positive inhomogeneous products
• Directed graphs, 2D state models, and characteristic polynomials of irreducible matrix pairs
• Synchronizing finite automata on Eulerian digraphs.
• Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata
• Between primitive and 2-transitive: synchronization and its friends
• Concerning nonnegative matrices and doubly stochastic matrices
• Relationships between nondeterministic and deterministic tape complexities
• Shortest positive products of nonnegative matrices
• Strong Inapproximability of the Shortest Reset Word
• In extremal combinatorial problem associated with the bound on the length of a synchronizing word in an automaton
• Approximating Minimum Reset Sequences
• Compact noncontraction semigroups of affine operators
• Reset Sequences for Monotonic Automata
• Synchronizing Automata and the Černý Conjecture
• The Complexity of Finding Reset Words in Finite Automata
• On two Combinatorial Problems Arising from Automata Theory
• Asymptotic estimate of the length of a diagnostic word for a finite automaton
• Computational Complexity
• Definite and Quasidefinite Sets of Stochastic Matrices
• The Distribution of Positive Elements in Doubly-Stochastic Matrices

This page was built for publication: Primitive Sets of Nonnegative Matrices and Synchronizing Automata