Dynamical implementation of nondeterministic automata and concurrent systems

Several recent results have implemented a number of deterministic automata (finite-state, pushdown, even Turing machines and neural nets) using piecewise linear dynamical systems in one- and two dimensional euclidean spaces. Nondeterministic devices have only been likewise implemented by iterated systems containing several maps. We show how to simulate nondeterministic and concurrent systems (finitestate automata, pushdown automata, and Petri nets) using a single deterministic piecewise linear map of the real interval. As a consequence, we establish a correspondence between nondeterminism and incremental entropy of the corresponding dynamical system. Relationship to the separation of complexity classes is discussed