Pin's generalized synchronizing automaton conjecture

Let A=(Q,Σ)A=(Q,\Sigma) be a finite automaton with n=Qn=|Q| states. Its rank rr is the minimum rank of its input words, where the rank of an input word is the cardinality of the image of its associated mapping. A terminal word is an input word attaining this minimum rank. Pin's conjecture. Every nn-state automaton of rank rr has a terminal word of length at most

(nr)2.(n-r)^2.

This generalizes the synchronizing case, since rank-one automata are synchronizing and terminal words are then reset words. The supplied status evidence says that this generalized conjecture was disproved by Kari (2001).

Sources & referencesView supporting material

Primary source

Nasim Karimi, “Reaching the minimum ideal in a finite semigroup”, arXiv:1506.01633 (2015).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.