Pin's generalized synchronizing automaton conjecture
Pin's generalized synchronizing automaton conjecture
Let be a finite automaton with states. Its rank 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 -state automaton of rank has a terminal word of length at most
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.