zbMATH — the first resource for mathematics

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 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, () · 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)
[11] King, K.N., Alternating finite automata, () · 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 New York · Zbl 0365.68072
[14] Slobodová, A., On the power of communication in alternating computations, (), (in Slovak) · Zbl 0649.68050
[15] Slobodová, A., On the power of communication in alternating machines, (), 518-528 · Zbl 0649.68050
[16] Slobodová, A., Some properties of space-bounded synchronized alternating Turing machines with only universal states, (), 209-218
[17] Turakainen, P., On some transducer equivalence problems for families of languages, () · Zbl 0658.68097
[18] Wiedermann, J., On the power of synchronization, () · 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.