Skip to main content
MathOverflow

Return to Answer

Post Made Community Wiki by Stefan Kohl♦
Name of paper of Dubuc; Cerny -> Černý
Source Link
LSpice
LSpice
  • 12.9k
  • 4
  • 45
  • 69

Many special cases of the Cerny conjectureČerný conjecture in automata theory have been proved using linear algebra, or really representations of monoids, that do not have known combinatorial proofs. The conjecture states that an $n$-state synchronizing automaton has a synchronizing word of length at most $(n-1)^2$. In purely mathematical terms the conjecture states that given a set of transformations of an $n$-element set, of which some composition (with repetitions allowed) is a constant map, then some composition of length at most $(n-1)^2$ is a constant map.

Many proof analyze the corresponding linear representation of the monoid generated by these transformations. My favorite example is the paper of DubucDubuc, which proves the conjecture is true if one of the transformations is an $n$-cycle. CernyČerný had already shown that the bound can be reached by examples with an $n$-cycle. Dubuc uses the nature of representations of the cyclic group over the rationals (or if you like uses minimal polynomials). But there are many more such examples.

Many special cases of the Cerny conjecture in automata theory have been proved using linear algebra, or really representations of monoids, that do not have known combinatorial proofs. The conjecture states that an $n$-state synchronizing automaton has a synchronizing word of length at most $(n-1)^2$. In purely mathematical terms the conjecture states that given a set of transformations of an $n$-element set, of which some composition (with repetitions allowed) is a constant map, then some composition of length at most $(n-1)^2$ is a constant map.

Many proof analyze the corresponding linear representation of the monoid generated by these transformations. My favorite example is the paper of Dubuc, which proves the conjecture is true if one of the transformations is an $n$-cycle. Cerny had already shown that the bound can be reached by examples with an $n$-cycle. Dubuc uses the nature of representations of the cyclic group over the rationals (or if you like uses minimal polynomials). But there are many more such examples.

Many special cases of the Černý conjecture in automata theory have been proved using linear algebra, or really representations of monoids, that do not have known combinatorial proofs. The conjecture states that an $n$-state synchronizing automaton has a synchronizing word of length at most $(n-1)^2$. In purely mathematical terms the conjecture states that given a set of transformations of an $n$-element set, of which some composition (with repetitions allowed) is a constant map, then some composition of length at most $(n-1)^2$ is a constant map.

Many proof analyze the corresponding linear representation of the monoid generated by these transformations. My favorite example is the paper of Dubuc, which proves the conjecture is true if one of the transformations is an $n$-cycle. Černý had already shown that the bound can be reached by examples with an $n$-cycle. Dubuc uses the nature of representations of the cyclic group over the rationals (or if you like uses minimal polynomials). But there are many more such examples.

Source Link
Benjamin Steinberg
Benjamin Steinberg
  • 38.6k
  • 3
  • 104
  • 186

Many special cases of the Cerny conjecture in automata theory have been proved using linear algebra, or really representations of monoids, that do not have known combinatorial proofs. The conjecture states that an $n$-state synchronizing automaton has a synchronizing word of length at most $(n-1)^2$. In purely mathematical terms the conjecture states that given a set of transformations of an $n$-element set, of which some composition (with repetitions allowed) is a constant map, then some composition of length at most $(n-1)^2$ is a constant map.

Many proof analyze the corresponding linear representation of the monoid generated by these transformations. My favorite example is the paper of Dubuc, which proves the conjecture is true if one of the transformations is an $n$-cycle. Cerny had already shown that the bound can be reached by examples with an $n$-cycle. Dubuc uses the nature of representations of the cyclic group over the rationals (or if you like uses minimal polynomials). But there are many more such examples.