Abstract:
Motivated by Mermin's analysis of Einstein-Podolsky-Rosen correlations [25] and
[6] we study two computational complementarity principles introduced in [7] for a
class of probabilistic automata. We prove the existence of probabilistic automata
featuring both types of computational complementarity and we present a method
to reduce, under certain conditions, the study of computational complementarity of
probabilistic automata to the study of computational complementarity of deterministic
automata.