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

• A counter example to a conjecture concerning synchronizing words in finite automata
• An extremal problem for two families of sets
• Experiments on Synchronizing Automata
• scientific article; zbMATH DE number 1834666 (Why is no real title available?)
• 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)

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

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)