On the power of synchronization in parallel computations. (English) Zbl 0755.68045

Mathematical foundations of computer science, Proc. 14th Symp., MFCS ’89, Porąbka-Kozubnik/Pol. 1989, Lect. Notes Comput. Sci. 379, 196-206 (1989).
[For the entire collection see Zbl 0726.00018.]
We characterize the power of synchronization by deterministic space classes. We show that synchronized alternating space \(\text{SASPACE}(s(n))\) is equal to \(\bigcup_{c\in N}\text{DSPACE}(c^{s(n)})\) for \(s(n)\geq\log_ 2 n\). In particular we obtain a new characterization of PSPACE by synchronized alternating logspace which is characterized by synchronized alternating multihead finite automata. This extends the well known characterization of the hierarchy \(\text{DLOGSPACE}\subseteq\text{NLOGSPACE}\subseteq P\) by deterministic, nondeterministic, and alternating multihead automata resp. Further, we show \(\text{SASPACE}(s(n))=\bigcup_{c>0}\text{SATIME}(c^{s(n)})\).
The family of languages recognized by two-way synchronized alternating finite automata is known to include NLOGSPACE [A. Slobodová, On the power of communication inalternating machines, Lect. Notes Comp. Sci. 324, 518-528 (1988; Zbl 0649.68050)]. We show here a much stronger result, namely that this family is equal to \(\text{NSPACE}(n)\) (i.e., to context-sensitive languages). We then investigate the influence of limiting the number of parallel processes on the computational power of synchronized alternating finite automata, i.e., we study the parallel complexity classes. First we show that limiting the parallelism to a constant \(k\) reduces the power to that of \(k\)-head nondeterministic finite automata. Besides supporting the common view that number of heads is a reasonable measure of parallelism this result enables us to translate the hierarchy results to synchronized automata. Next we give an upper bound \(\text{NSPACE}(f(n)\log_ 2 n)\) for the power of synchronized alternating finite automata with parallelism limited by \(f(n)\). We give a strict hierarchy result for parallel complexity classes with bound \(f(n)\leq n^{1/4}/\log_ 2 n\).
Furthermore we consider decidability questions and find a surprising connection between synchronization and transducers.


68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q25 Analysis of algorithms and problem complexity
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)