The synchronizing probability function for primitive sets of matrices

DOI10.1007/978-3-319-98654-8_16MaRDI QIDQ1622961zbMATH OpenOpenAlexFDO

Authors Costanza Catalano, Raphaël M. Jungers

Publication date 22 November 2018

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Applications of game theory (91A80) Algebraic systems of matrices (15A30)

Abstract: Motivated by recent results relating synchronizing DFAs and primitive sets, we tackle the synchronization process and the related longstanding v{C}ern'{y} conjecture by studying the primitivity phenomenon for sets of nonnegative matrices having neither zero-rows nor zero-columns. We formulate the primitivity process in the setting of a two-player probabilistic game and we make use of convex optimization techniques to describe its behavior. We develop a tool for approximating and upper bounding the exponent of any primitive set and supported by numerical results we state a conjecture that, if true, would imply a quadratic upper bound on the reset threshold of a new class of automata.

Recommendations

• The Synchronizing Probability Function for Primitive Sets of Matrices
• Primitive sets of nonnegative matrices and synchronizing automata
• The synchronizing probability function of an automaton
• On primitivity of sets of matrices
• Primitivity and synchronizing automata: a functional analytic approach

Cited in

(9)

• A Linear Bound on the k-rendezvous time for primitive sets of NZ matrices
• The synchronizing probability function of an automaton
• Primitivity and synchronizing automata: a functional analytic approach
• Primitive sets of nonnegative matrices and synchronizing automata
• Analytic methods for reachability problems
• On randomized generation of slowly synchronizing automata
• On primitivity of 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

This page was built for publication: The synchronizing probability function for primitive sets of matrices

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