Stochastic automata with large state spaces and low rank (Q1085611)

An n-state stochastic automaton is defined as a quadruple \(S=(A,\{M(a):\) a in \(A\}\),\(\pi\),\(\eta)\) where A is a finite alphabet, each M(a) is a nonnegative \(n\times n\) matrix, the sum of all M(a)'s is a stochastic matrix, \(\pi\) is a \(1\times n\) nonnegative vector and \(\eta =(1,1,...,1)^ T\). The word function f generated by S is defined by \(f(a_ 1a_ 2...a_ k)=\pi M(a_ 1)M(a_ 2)...M(a_ k)\eta\). The rank of f is the rank of the Hankel matrix \(\| f(x_ iy_ j)\|\) where \(\{x_ i\}\) and \(\{y_ j\}\) are enumerations of \(A^*\). The author proves the following result: For each \(n>3\) there exists a word function of rank three which is generated by an n-state stochastic automaton but not by any stochastic automaton having fewer than n states.