Deterministic versus nondeterministic space in terms of synchronized alternating machines

AbstractThe 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