Abstract:
Finite automata (with outputs but no initial states) have been extensively used
as models of computational complementarity, a property which mimics the physical
complementarity. All this work was focussed on “frames", i.e., on fixed, static, local
descriptions of the system behaviour. In this paper we are mainly interested in the
asymptotical description of complementarity. To this aim we will study the asymptotical behaviour of two complementarity principles by associating to every incomplete
deterministic automaton (with outputs, but no initial state) certain sofic shifts: automata having the same behaviour correspond to a unique sofic shift. In this way, a class of sofic shifts reflecting complementarity will be introduced and studied. We will prove that there is a strong relation between “local complementarity", as it is perceived at the level of “frames", and “asymptotical complementarity" as it is described by the sofic shift.