Modifying the Upper Bound on the Length of Minimal Synchronizing Word

DOI10.1007/978-3-642-22953-4_15zbMath1342.68188arXiv1104.2409OpenAlexW2171865517MaRDI QIDQ3088281

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)

Related Items (18)

Unnamed Item ⋮ Shortest positive products of nonnegative matrices ⋮ Synchronizing Automata on Quasi-Eulerian Digraph ⋮ P(l)aying for Synchronization ⋮ Synchronizing Automata of Bounded Rank ⋮ Synchronization of Automata with One Undefined or Ambiguous Transition ⋮ Primitive digraphs with large exponents and slowly synchronizing automata ⋮ Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata ⋮ Synchronizing Automata with Extremal Properties ⋮ Completely Reachable Automata: An Interplay Between Automata, Graphs, and Trees ⋮ Models and algorithms of automata theory for the control of an aircraft group ⋮ Complexity of a problem concerning reset words for Eulerian binary automata ⋮ A multi-parameter analysis of hard problems on deterministic finite automata ⋮ Coupling any number of balls in the infinite-bin model ⋮ On the Synchronizing Probability Function and the Triple Rendezvous Time ⋮ On the Synchronizing Probability Function and the Triple Rendezvous Time for Synchronizing Automata ⋮ Experiments with Synchronizing Automata ⋮ Černý's conjecture and the road colouring problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unambiguous automata
• An extremal problem for two families of sets
• Experiments on Synchronizing Automata
• Notable trends concerning the synchronization of graphs and automata
• The Averaging Trick and the Černý Conjecture
• Slowly Synchronizing Automata and Digraphs
• On two Combinatorial Problems Arising from Automata Theory
• On the Road Coloring Problem

This page was built for publication: Modifying the Upper Bound on the Length of Minimal Synchronizing Word