Primitivity and Synchronizing Automata: A Functional Analytic Approach

We give a survey of a function-analytic approach in the study of primitivity of matrix families and of synchronizing automata. Then we define the m-synchronising automata and prove that the existence of a reset m-tuple of a deterministic automata with n states can be decided in less than mn2(log2n+m+42) operations. We study whether the functional-analytic approach can be extended to m-primitivity and to m-synchronising automata. Several open problems and conjectures concerning the length of m-reset tuples, m-primitive products and finding those objects algorithmically are formulated.