On the Minimal Reset Words of Synchronizing Automata

Overview

Cerny's conjecture is a 50-year old question which concerns the combinatorial field of synchronizing automata. In particular, it postulates that the maximal length of the minimal reset word among all n-state automata is (n-1)^2. A proof is presented for Pin's Theorem, which applies Cerny's conjecture to p-state automata consisting of a cycle and a non-permutation, where p is an odd prime. Also, families of automata of the form F(p, k) are introduced; they consist of a cycle and a group of k disjoint merging arcs. C(p, k) is defined to be the maximal length of minimal reset words within these families. A lower bound of C(p, k) for general k is demonstrated, and the exact value of C(p, 2) is found. These results are presented in two original theorems. In order to prove these statements, a connection is discovered between the structures of automata within F(p, k) and the cyclotomic field with respect to p.

Competition history

• ISEF 2015 Category not listed · Entry MATH025I

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.