On the synchronizing probability function and the triple rendezvous time for synchronizing automata

DOI10.1137/15M1024603MaRDI QIDQ2808158zbMATH OpenOpenAlexFDO

Authors François Gonze, Raphaël M. Jungers

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 theorysynchronizationsynchronizing automatasynchronizing probabilityČerný's conjecture

Mathematics Subject Classification ID

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

Abstract: Cerny's conjecture is a longstanding open problem in automata theory. We study two different concepts, which allow to approach it from a new angle. The first one is the triple rendezvous time, i.e., the length of the shortest word mapping three states onto a single one. The second one is the synchronizing probability function of an automaton, a recently introduced tool which reinterprets the synchronizing phenomenon as a two-player game, and allows to obtain optimal strategies through a Linear Program. Our contribution is twofold. First, by coupling two different novel approaches based on the synchronizing probability function and properties of linear programming, we obtain a new upper bound on the triple rendezvous time. Second, by exhibiting a family of counterexamples, we disprove a conjecture on the growth of the synchronizing probability function. We then suggest natural follow-ups towards Cernys conjecture.

Recommendations

• On the synchronizing probability function and the triple rendezvous time. New approaches to Černý's conjecture
• The synchronizing probability function of an automaton
• The Cerny Conjecture Holds with High Probability
• Synchronizing random automata
• The Černý conjecture for automata respecting intervals of a directed graph

Cites work

• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• scientific article; zbMATH DE number 5593050 (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 counter example to a conjecture concerning synchronizing words in finite automata
• A note on a recent attempt to improve the Pin-Frankl bound
• A quadratic upper bound on the size of a synchronizing word in one-cluster automata
• An extremal problem for two families of sets
• Experimental study of the shortest reset word of random automata
• In extremal combinatorial problem associated with the bound on the length of a synchronizing word in an automaton
• Independent sets of words and the synchronization problem
• Modifying the upper bound on the length of minimal synchronizing word
• On a conjecture by Carpi and D'Alessandro
• On primitivity of sets of matrices
• On the synchronizing probability function and the triple rendezvous time. New approaches to Černý's conjecture
• On two Combinatorial Problems Arising from Automata Theory
• Parameterized complexity of synchronization and road coloring
• Reset Sequences for Monotonic Automata
• Slowly synchronizing automata and digraphs
• Synchronizing Automata and the Černý Conjecture
• Synchronizing automata with a letter of deficiency 2
• Synchronizing finite automata on Eulerian digraphs.
• Synchronizing generalized monotonic automata
• The averaging trick and the Černý conjecture
• The complexity of finding reset words in finite automata
• The road coloring problem
• The synchronizing probability function of an automaton
• The Černý conjecture for aperiodic automata

Cited in

(5)

• The synchronizing probability function of an automaton
• On the interplay between Černý and Babai's conjectures
• Synchronizing times for \(k\)-sets in automata
• Preimage problems for deterministic finite automata
• On the synchronizing probability function and the triple rendezvous time. New approaches to Černý's conjecture

This page was built for publication: On the synchronizing probability function and the triple rendezvous time for synchronizing automata

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