Algorithms and combinatorics of matrix reachability

The Černý conjecture is one of the oldest open problems in automata theory. At least that's what they say in the introduction of every paper even vaguely related to it. For a set of transformations of a finite set Q (mappings from Q to itself), it bounds the length of a shortest composition of these transformations resulting in a constant transformation (if it can be obtained this way at all).

This conjecture is usually perceived as a fairly isolated, self-absorbed question. However, it is a building block (and an obstacle) in a larger picture featuring nonnegative matrices, digraphs, finite rational matrix semigroups and weighted automata. By concentrating on a few most interesting results, I will explain a part of this picture by providing a phrasebook for travelling between the mentioned areas, which often talk about the same ideas in different languages. Some of the most natural questions will however remain unanswered. For example, we have almost no idea about the computational complexity of the following problem: given a finite set of rational matrices, does the set of all their products have finite cardinality?