Modifying the upper bound on the length of minimal synchronizing word

DOI10.1007/978-3-642-22953-4_15MaRDI QIDQ3088281zbMATH OpenOpenAlexFDO

Authors A. N. Trahtman

Publication date 19 August 2011

Published in Fundamentals of Computation Theory (Search for Journal in Brave)

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

zbMATH Keywords

deterministic finite automatonsynchronizing wordČerny conjecture

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: A word $w$ is called synchronizing (recurrent, reset, magic, directable) word of deterministic finite automaton (DFA) if $w$ sends all states of the automaton to a unique state. In 1964 Jan v{C}erny found a sequence of n-state complete DFA possessing a minimal synchronizing word of length $(n-1{)}^2$. He conjectured that it is an upper bound on the length of such words for complete DFA. Nevertheless, the best upper bound $(n^3-n)/6$ was found almost 30 years ago. We reduce the upper bound on the length of the minimal synchronizing word to $n(7n^2+6n-16)/48$. An implemented algorithm for finding synchronizing word with restricted upper bound is described. The work presents the distribution of all synchronizing automata of small size according to the length of an almost minimal synchronizing word.

Recommendations

• An Efficient Algorithm Finds Noticeable Trends and Examples Concerning the Černy Conjecture
• Synchronization of Some DFA
• Finding DFAs with maximal shortest synchronizing word length
• The Černý conjecture for aperiodic automata
• An improvement to a recent upper bound for synchronizing words of finite automata

Cites work

• scientific article; zbMATH DE number 1834666 (Why is no real title available?)
• A counter example to a conjecture concerning synchronizing words in finite automata
• An extremal problem for two families of sets
• Experiments on Synchronizing Automata
• Notable trends concerning the synchronization of graphs and automata
• On the Road Coloring Problem
• On two Combinatorial Problems Arising from Automata Theory
• Slowly synchronizing automata and digraphs
• The averaging trick and the Černý conjecture
• The Černý conjecture for aperiodic automata
• Unambiguous automata

Cited in

(29)

• Shortest positive products of nonnegative matrices
• Synchronizing non-deterministic finite automata
• scientific article; zbMATH DE number 6606363 (Why is no real title available?)
• A lower bound for the length of the shortest carefully synchronizing words
• On the synchronizing probability function and the triple rendezvous time. New approaches to Černý's conjecture
• Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata
• Synchronizing automata of bounded rank
• Finitely Generated Synchronizing Automata
• Coupling any number of balls in the infinite-bin model
• In extremal combinatorial problem associated with the bound on the length of a synchronizing word in an automaton
• A cornering strategy for synchronizing a DFA
• Synchronization of Some DFA
• Completely Reachable Automata: An Interplay Between Automata, Graphs, and Trees
• Synchronizing automata with finitely many minimal synchronizing words
• DFAs and PFAs with long shortest synchronizing word length
• Synchronizing Automata with Extremal Properties
• Černý's conjecture and the road colouring problem
• Synchronization of automata with one undefined or ambiguous transition
• Synchronizing times for k-sets in automata
• A multi-parameter analysis of hard problems on deterministic finite automata
• Experiments with Synchronizing Automata
• Almost optimal bound of recurrent word length for regular automata
• On the synchronizing probability function and the triple rendezvous time for synchronizing automata
• scientific article; zbMATH DE number 7228447 (Why is no real title available?)
• Primitive digraphs with large exponents and slowly synchronizing automata
• Complexity of a problem concerning reset words for Eulerian binary automata
• An improvement to a recent upper bound for synchronizing words of finite automata
• Synchronizing automata on quasi-Eulerian digraph
• Models and algorithms of automata theory for the control of an aircraft group

This page was built for publication: Modifying the upper bound on the length of minimal synchronizing word

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