Deterministic Versus Nondeterministic Space in Terms of Synchronized Alternating Machines.
Juraj Hromkovic̆, Branislav Rovan, Anna Slobodová · Developments in Language Theory · 1993
The study of synchronized alternating machines has enabled to characterize several natural complexity classes. It is known that synchronized alternating space SASPACE(S(n))= ?c>0NSPACE(ncS(n)) for any (space-constructible) function S(n) Hromkovic?et al. (1991)]. In particular, context-sensitive languages are characterized by two-way synchronized alternating finite automata. Furthermore, PSPACE is characterized by synchronized alternating multihead finite automata and NLOG by synchronized alternating two-way finite automata with parallelism bounded by a constant. In the present paper we prove analogous characterizations for deterministic space classes using a restricted form of synchronization - globally deterministic synchronization. This enables to study the well-known open problems concerning nondeterminism versus determinism as problems about synchronization. We also show that globally deterministic synchronization is strictly more powerful than deterministic synchronization.