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

Summary: 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))=\cup_{c>0}NSPACE(n\cdot c^{S(n)})\). Using this characterization of synchronized alternating space the following new characterizations of fundamental complexity classes are established:
(1)\(\cup_{c>0}DSPACE(c^{S(n)})=\cup_{c>0}\) \(ATIME(c^{S(n)})=\cup_{c>0}SATIME(c^{S(n)})=SASPACE(S(n))\) for \(S(n)\geq \log_ 2n\). (2) \(NSPACE(n)={\mathcal L}(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. We 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 we consider k independent finite automata communicating only by synchronization. This represents a natural intermediate case between “full communication” and we present several new results and open problems for this form of communication of parallel processes.


68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
Full Text: DOI


[1] Berstel, J., Transductions and Context-Free Languages> (1979), Teubner: Teubner Stuttgart · Zbl 0424.68040
[2] Bird, M., The equivalence problem for deterministic two-tape automata, J. Comput. System Sci., 7, 218-236 (1973) · Zbl 0271.94039
[3] Chandra, A. K.; Kozen, D. K.; Stockmeyer, J., Alternation, J. ACM, 28, 114-133 (1981) · Zbl 0473.68043
[4] van Emde Boas, P., The Second Machine Class 2, an encyclopedic view on the Parallel Computation Thesis, (Technical Report 85-24 (1985), Department of Mathematics, University of Amsterdam) · Zbl 0760.68027
[5] Fisher, P. C.; Rosenberg, A. L., Multi-tape one-way nonwriting automata, J. Comput. System Sci., 2, 88-101 (1968) · Zbl 0159.01504
[6] Hromkovič, J., How to organize the communication among parallel processes in alternating computations (1986), Unpublished manuscript
[7] Hromkovič, J., Tradeoffs for language recognition on alternating machines, Theoret. Comput. Sci., 63, 203-221 (1989) · Zbl 0667.68060
[8] Ibarra, O., Reversal bounded multicounter machines and their decision problems, J. ACM, 25, 116-133 (1978) · Zbl 0365.68059
[9] Ibarra, O., The unsolvability of the equivalence problem for ε-free NGSM’s with unary input (output) alphabet and applications, SIAM J. Comput., 4, 524-532 (1978) · Zbl 0386.68054
[10] Karhumäki, J., The equivalence of mapping on languages, Lecture Notes in Computer Science, 281, 26-38 (1987) · Zbl 0637.68093
[11] King, K. N., Alternating finite automata, (Doctoral Dissertation (1981), University of California: University of California Berkeley, CA) · Zbl 0665.68064
[12] Rivest, R. L.; Yao, A. C., \(k+1\) heads are better than \(k\), J. ACM, 25, 337-340 (1978) · Zbl 0372.68017
[13] Rozenberg, G.; Salomaa, A., The Mathematical Theory of \(L\)-systems (1980), Academic Press: Academic Press New York · Zbl 0365.68072
[14] Slobodová, A., On the power of communication in alternating computations, (Student Research Papers Competition (1987), Section Computer Science, Comenius University: Section Computer Science, Comenius University Bratislava), (in Slovak) · Zbl 0649.68050
[15] Slobodová, A., On the power of communication in alternating machines, (Proceedings MCFS ’88. Proceedings MCFS ’88, Lecture Notes in Computer Science, 324 (1988), Springer: Springer New York), 518-528 · Zbl 0649.68050
[16] Slobodová, A., Some properties of space-bounded synchronized alternating turing machines with only universal states, (Proceedings IMYCS ’88 (1988), Hungarian Academy of Sciences: Hungarian Academy of Sciences Budapest), 209-218
[17] Turakainen, P., On some transducer equivalence problems for families of languages, (Research Report (1987), University of Oulu: University of Oulu Finland) · Zbl 0658.68097
[18] Wiedermann, J., On the power of synchronization, (Technical Report (1987), VUSEI-AR: VUSEI-AR Bratislava) · Zbl 0689.68074
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.