Finite statistical complexity for sofic systems

We propose a measure of complexity for symbolic sequences, which is based o n conditional probabilities, and captures computational aspects of complexi ty without the explicit construction of minimal deterministic finite automa ta (DFA). Moreover, if the sequence is obtained from a dynamical system thr ough a suitable encoding and its equations of motion are known, we show how to estimate the regions of phase space that correspond to computational st ates with statistically equivalent futures (causal states). [S1063-651X(99) 11707-0].