In extremal combinatorial problem associated with the bound on the length of a synchronizing word in an automaton

DOI10.1007/BF01071771zbMath0691.05025MaRDI QIDQ3032279

I. K. Rystsov, M. A. Spivak, Alexander A. Klyachko

Publication date: 1987

Published in: Cybernetics (Search for Journal in Brave)

zbMATH Keywords

finite automatonextremal problemsynchronizing wordindependence systems

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Hypergraphs (05C65) Formal languages and automata (68Q45)

Related Items (16)

Unnamed Item ⋮ Almost optimal bound of recurrent word length for regular automata ⋮ Describing Homing and Distinguishing Sequences for Nondeterministic Finite State Machines via Synchronizing Automata ⋮ Reset words for commutative and solvable automata ⋮ Completely Reachable Automata: An Interplay Between Automata, Graphs, and Trees ⋮ On the Interplay Between Černý and Babai’s Conjectures ⋮ Synchronizing Automata and the Černý Conjecture ⋮ A NOTE ON SYNCHRONIZED AUTOMATA AND ROAD COLORING PROBLEM ⋮ Algebraic synchronization criterion and computing reset words ⋮ Genetic Algorithm for Synchronization ⋮ COMPAS - A Computing Package for Synchronization ⋮ Approximating Minimum Reset Sequences ⋮ On the Synchronizing Probability Function and the Triple Rendezvous Time for Synchronizing Automata ⋮ Matrix Mortality and the Černý-Pin Conjecture ⋮ Černý's conjecture and the road colouring problem ⋮ Primitive Sets of Nonnegative Matrices and Synchronizing Automata

Cites Work

• Establishing certain bounds concerning finite automata
• Solution of a problem of A. Ehrenfeucht and J. Mycielski
• Closure in Independence Systems
• Unnamed Item
• Unnamed Item

This page was built for publication: In extremal combinatorial problem associated with the bound on the length of a synchronizing word in an automaton