On the Synchronizing Probability Function and the Triple Rendezvous Time for Synchronizing Automata

DOI10.1137/15M1024603zbMath1339.68147arXiv1410.4034OpenAlexW1716012257MaRDI QIDQ2808158

Raphaël M. Jungers, François Gonze

Publication date: 26 May 2016

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

game theorysynchronizationČerný's conjecturesynchronizing automatasynchronizing probability

Mathematics Subject Classification ID

Applications of game theory (91A80) Formal languages and automata (68Q45) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (4)

Synchronizing times for \(k\)-sets in automata ⋮ Preimage problems for deterministic finite automata ⋮ On the Interplay Between Černý and Babai’s Conjectures ⋮ On the Synchronizing Probability Function and the Triple Rendezvous Time

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The road coloring problem
• Synchronizing automata with a letter of deficiency 2
• On primitivity of sets of matrices
• An extremal problem for two families of sets
• Synchronizing finite automata on Eulerian digraphs.
• Synchronizing generalized monotonic automata
• Independent sets of words and the synchronization problem
• On the Synchronizing Probability Function and the Triple Rendezvous Time
• The Synchronizing Probability Function of an Automaton
• ON A CONJECTURE BY CARPI AND D'ALESSANDRO
• THE AVERAGING TRICK AND THE ČERNÝ CONJECTURE
• In extremal combinatorial problem associated with the bound on the length of a synchronizing word in an automaton
• A QUADRATIC UPPER BOUND ON THE SIZE OF A SYNCHRONIZING WORD IN ONE-CLUSTER AUTOMATA
• Modifying the Upper Bound on the Length of Minimal Synchronizing Word
• Reset Sequences for Monotonic Automata
• Synchronizing Automata and the Černý Conjecture
• Slowly Synchronizing Automata and Digraphs
• The Complexity of Finding Reset Words in Finite Automata
• On two Combinatorial Problems Arising from Automata Theory
• Experimental Study of the Shortest Reset Word of Random Automata

This page was built for publication: On the Synchronizing Probability Function and the Triple Rendezvous Time for Synchronizing Automata