CS Seminar: Generation of non-isomorphic unary automata and the Černý...
  • FENS
  • CS Seminar: Generation of non-isomorphic unary automata and the Černý...

You are here

Speaker: Kağan Kurşungöz

Title: Generation of non-isomorphic unary automata and the Černý conjecture

Date/Time: October 26, 12:40 - 13:30

Place: FENS L067


Abstract: Consider the sequence A001372 in the online encyclopedia of integer sequences (OEIS).   This is the number of mapping patterns from n points to themselves, or the number of non-isomorphic unary automata where all out-degrees are 1.  It is a well known and studied sequence, and there are formulas to compute any member.  However, we do not know of any implementation to generate all function classes, or corresponding automata.  We propose an efficient algorithm (albeit with acceptable redundancy) to generate all such unary automata using integer partitions.  

The application is the verification of Černý conjecture.  This is a long standing conjecture in graph theory, stating that if an automaton with n states has a synchronizing sequence, then the shortest syncyronizing sequence has length (n-1)^2 or less.  The conjecture is allegedly settled in the affirmative by Avraham Trahtman fairly recently, but his proof has not been checked yet.  The trend in literature before was to verify it by exhaustive search.  Kisielewicz and Szykuła found a method to systematically generate k-ary automata from non-isomorphic unary automata, and verified the conjecture for binary automata up to n = 11 states (update: another group verified binary automata with n = 12 states).  They take the existence of the lists of unary automata for granted.  Therefore, the generation of non-isomorphic unary automata is of central importance.  

We will give an overview of the conjecture and not-so-recent progress, and then describe the algorithm to generate unary automata for any number of states.  This is joint work with Kamer Kaya and Hüsnü Yenigün, supported by TÜBİTAK 1001 project no 114E569.