# Synchronizing Automata and the CÌŒernyÌ Conjecture

- ECU Author/Contributor (non-ECU co-authors, if there are any, appear on document)
- Miciah Dashiel Butler Masters (Creator)
- Institution
- East Carolina University (ECU )
- Web Site: http://www.ecu.edu/lib/
- Advisor
- Krishnan Gopalakrishnan

**Abstract:** We provide a survey of research surrounding the CÌŒernyÌ conjecture. This conjecture concerns finite-state automata that have the property of being "synchronizing." A synchronizing automaton is one for which there exists some input sequence that causes the automaton to transition to some fixed state irrespective of the state in which it had been before reading that input sequence. The CÌŒernyÌ conjecture states that if an automaton with n states is synchronizing then there exists some input sequence of length at most (n - 1)Â² that synchronizes it. We first survey the basic results that deal with synchronization of finite-state automata. We also study and implement several related algorithms including Eppstein's greedy algorithm for producing a reset sequence. An analysis of the length of the sequence produced by this algorithm leads to an interesting problem in extremal combinatorics the solution of which yields an upper bound of (nÂ³ - n)/6 on the length of the sequence. We then investigate a generalization of the CÌŒernyÌ conjecture. Next we study extremal automata for which the length of the shortest synchronizing sequence meets the CÌŒernyÌ bound. We then turn our attention to subclasses of automata for which the CÌŒernyÌ conjecture has been proved. Finally we discuss possible approaches and current efforts to proving the CÌŒernyÌ conjecture as well as some related problems from the literature.

## Additional Information

- Publication
- Thesis
- Date: 2012
- Keywords
- Computer science, automata, CÌŒernyÌ conjecture, deterministic, finite-state, synchronizing automata
- Subjects
- Machine theory
- Robots--Programming

Email this document to

This item references:

Title | Location & Link | Type of Relationship |
---|---|---|

Synchronizing Automata and the CÌŒernyÌ Conjecture | http://hdl.handle.net/10342/3937 | The described resource references, cites, or otherwise points to the related resource. |