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

DOI10.1137/15M1024603zbMATH Open1339.68147arXiv1410.4034OpenAlexW1716012257MaRDI QIDQ2808158FDOQ2808158

Authors: François Gonze, Raphaël M. Jungers Edit this on Wikidata

Publication date: 26 May 2016

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

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.

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

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

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)

Cites Work

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

Cited In (5)

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

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)