Stochastic automata with large state spaces and low rank

Abstract

It is shown by means of example that for each n > 3, there is a minimal n-state stochastic automaton whose output behavior is a word function of rank 3. Thus, there are stochastic word functions whose natural representation may be quite unwieldy, but whose values nevertheless can be computed in a rapid, compact fashion. © 1986.