Computational mechanics: Pattern and prediction, structure and simplicity

Computational mechanics, an approach to structural complexity, defines a process's causal states and gives a procedure for finding them. We show that the causal-state representation -an epsilon -machine-is the minimal one consistent with accurate prediction. We establish several results on epsilon -machine optimality and uniqueness and on how epsilon -machines compare to alternative representations. Further results relate measures of randomness and structural complexity obtained from epsilon -machines to those from ergodic and information theories.