The Synchronizing Probability Function for Primitive Sets of Matrices
From MaRDI portal
Publication:5859647
DOI10.1142/S0129054120410051zbMath1458.68093OpenAlexW2950671947MaRDI QIDQ5859647
Costanza Catalano, Raphaël M. Jungers
Publication date: 19 April 2021
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s0129054120410051
Applications of game theory (91A80) Formal languages and automata (68Q45) Algebraic systems of matrices (15A30)
Related Items (2)
New characterizations of primitive permutation groups with applications to synchronizing automata ⋮ A Linear Bound on the k-rendezvous Time for Primitive Sets of NZ Matrices
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Primitive digraphs with large exponents and slowly synchronizing automata
- Sets of nonnegative matrices without positive products
- On primitivity of sets of matrices
- Combinatorial properties of entire semigroups of nonnegative matrices
- Non-negative matrices and Markov chains. 2nd ed
- An extremal problem for two families of sets
- Limit theorems for products of positive random matrices
- Reset words for commutative and solvable automata
- Synchronizing finite automata on Eulerian digraphs.
- The synchronizing probability function for primitive sets of matrices
- The complexity of oblivious plans for orienting and distinguishing polygonal parts
- DFAs and PFAs with long shortest synchronizing word length
- On the interplay between Babai and Černý's conjectures
- On the Synchronizing Probability Function and the Triple Rendezvous Time
- The Synchronizing Probability Function of an Automaton
- Strong Inapproximability of the Shortest Reset Word
- Synchronizing Automata with Extremal Properties
- Invariant functions for the Lyapunov exponents of random matrices
- Primitive Sets of Nonnegative Matrices and Synchronizing Automata
- Reset Sequences for Monotonic Automata
- Synchronizing Automata Preserving a Chain of Partial Orders
- Synchronizing Automata and the Černý Conjecture
- Smoothed analysis of algorithms
- The Averaging Trick and the Černý Conjecture
- On two Combinatorial Problems Arising from Automata Theory
- Primitivity and Local Primitivity of Digraphs and Nonnegative Matrices
- Decidability of the Membership Problem for 2 × 2 integer matrices
- Attainable Values of Reset Thresholds
- On random primitive sets, directable NDFAs and the generation of slowly synchronizing DFAs
- An improvement to a recent upper bound for synchronizing words of finite automata
- Unsolvability in 3 × 3 Matrices
- On the synchronizing properties of certain prefix codes
- An Efficient Algorithm Finds Noticeable Trends and Examples Concerning the Černy Conjecture
- Estimation of the length of reset words for automata with simple idempotents
This page was built for publication: The Synchronizing Probability Function for Primitive Sets of Matrices
