Pin's generalized synchronizing automaton conjecture

At least 10 years old · documented by

Let A=(Q,Σ)A=(Q,\Sigma) be a finite automaton with n=∣Q∣n=|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

(n−r)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).

References

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.