Computational Complementarity and Shift Spaces 1

Abstract: Computational complementarity was introduced to mimic the physical complementarity in terms of nite automata (with outputs but no initial state). Most of the work has been focussed on \frames", i.e., on xed, static, local descriptions of the system behaviour. The rst paper aiming to study the asymptotical description of complementarity was restricted to certain types of soc shifts. In this paper we continue this work and extend the results to all irreducible soc shifts. We also study computational complementarity in terms of labelled graphs rather than automata. Key Words: Complementarity principles, nite automata, soc shifts, graphs