This paper continues investigations of synchronized alternating machines which provide a natural model of communication of parallel processes. It is proved that synchronized alternating space SASPACE(S(n))=ℝcÅ>0NSPACE(nëcS’(n’)). Using this characterization of synchronized alternating space the following new characterizations of fundamental complexity classes are established: (1) ℝcÅ>0DSPACE(cS’(n’))=ℝcÅ>0ATIME(cS’(n’))=ℝcÅ>0SATIME(cS’(n’))=SASPACE(S(n)) for S(n)≥log2n. (2) NSPACE(n)=ℒ(2SAFA), i.e. two-way synchronized alternating finite automata recognize exactly context-sensitive languages. (3) PSPACE=SALOGSPACE is exactly the class of languages recognized by two-way synchronized alternating multihead finite automata. Further, the parallel complexity of synchronized alternating finite automata is investigated and some hierarchy results are established. The authors also investigate the decidability problems for multihead and multitape automata from the new point of view. Instead of having one common finite state control enabling ‘full communication’ of the heads as usual they consider k independent finite automata communicating only by synchronization. This represents a natural intermediate case between ‘full communication’ and ‘no communication’ and the authors present several new results and open problems for this form of communication of parallel processes.
