Project Report

My research concerns finite-state automata from automata theory, which is a part of the discipline of computer science. A finite-state automaton, or FSA, is an abstract model of computation. An FSA comprises a finite set of possible states, an alphabet, and a transition function. At any instant, the FSA can be in exactly one of its states. Given the current state and some input (a symbol from the alphabet), the FSA moves into another state (or possibly stays the same state) as dictated by the transition function. Finite-state automata have been well studied and are important in computer science both from theoretical and practical points of view. Few open problems remain in automata theory; one such problem is the ?erný conjecture concerning "synchronizing automata." An FSA is called "synchronizing" if there exists some input sequence that causes the automaton to transition into some fixed state, irrespective of the state in which it was before that input sequence was given. Such an input sequence is commonly called a "reset word." The ?erný conjecture states that given a synchronizing automaton with n states, there exists some reset word for that automaton that is no longer than (n-1)^2 symbols. Automata that reach this bound are known, and no automaton that exceeds the bound is known, but the bound has defied general proof, despite attempts spanning decades by many researchers employing a multitude of approaches. One approach that has yielded an important partial result is a greedy algorithm due to Eppstein. A greedy, or locally optimizing, algorithm is one that makes short-sighted decisions: When the algorithm reaches a situation in which it has multiple choices, it always chooses the one that appears at the moment to be the best choice, heedless of the possibility that a choice that appears suboptimal now may ultimately result in a lower final cost. In particular, the Eppstein algorithm iteratively builds a reset word by finding the shortest sequence of symbols that goes from two (or more) states that the automaton could be in to one state, repeating until there remains only one state that the automaton could be in, and concatenating these sequences to construct a final reset word that will cause the automaton to transition from any one of its states to exactly one single, fixed state. A greedy algorithm is fast because it makes decisions quickly, and it can be easier to design and analyze than a more sophisticated algorithm, but for some problems, a greedy algorithm does not always find the optimal solution. Such is the case with the Eppstein algorithm, which is shown to generate suboptimal reset words for some synchronizing automata. Still, the Eppstein algorithm provides a significant result: An analysis of the algorithm shows that on a given synchronizing automaton with n states, the algorithm produces a reset word for that automaton, and that reset word will have length no greater than (n^3-n)/6. The algorithm serves as a constructive proof that the upper bound on the length of the shortest reset word for any synchronizing automaton is cubic in the number of possible states. This bound, while falling short of the bound postulated in the ?erný conjecture, is the tightest known bound on the length of the shortest word for general synchronizing automata. I investigated approaches based on the Eppstein algorithm, as well as other approaches, to find a tighter bound on the length of the shortest reset word of a given automaton. This work is ongoing as part of my graduate studies. In addition to work specifically on the ?erný conjecture, my grant provided my with a unique opportunity to network and to share ideas with researchers at institutions in China. Such sharing of knowledge is the basis of scientific progress, and the connections that the EAPSI program facilitates foster greater cultural, political, social, and linguistic understanding between China and the United States.

National Science Foundation (NSF)
Office of International and Integrative Activities (IIA)
Application #
Program Officer
Carter Kimsey
Project Start
Project End
Budget Start
Budget End
Support Year
Fiscal Year
Total Cost
Indirect Cost
Masters Miciah B
United States
Zip Code