Computational mechanics: Pattern and prediction, structure and simplicity

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