Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 6 / Issue 1

available in:   PDF (201 kB) PS (71 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-006-01-0169


Computational Complementarity and Shift Spaces

Marjo Lipponen (Department of Mathematics, Finland)

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

1 C.S.Calude and G.Stefanescu (eds.). Automata, Logic, and Computability. Special issue dedicated to Professor Sergiu Rudeanu Festschrift.

Keywords: complementarity principles, finite automata, graphs, sofic shifts

Categories: F.1.1