Communication for alternating machines. (English) Zbl 0769.68022

Properties of a model of parallel computation generalizing the concept of alternation (the so-called synchronized alternation) is investigated and several results are obtained. The model supports a simple form of communications (via states) among parallel processes. It seems to be a useful tool for investigating both nondeterminism and parallelism.


68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
Full Text: DOI


[1] AHU74 Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The design and analysis of computer algorithms. Reading, MA: Addison-Wesley 1974 · Zbl 0326.68005
[2] CKS81 Chandra, A.K., Kozen, D.C., Stockmeyer, L.J.: Alternation. J. ACM28, 114-133 (1981) · Zbl 0473.68043 · doi:10.1145/322234.322243
[3] Gin75 Ginsburg, S.: Algebraic and automata-theoretic properties of formal languages. North Holland, Amsterdam: North Holland 1975
[4] HU69 Hopcroft, J.E., Ullman, J.D.: Formal languages and their relation to automata. Reading, MA: Addison-Wesley 1969 · Zbl 0196.01701
[5] Hr85 Hromkovi?, J.: On the power of alternation in automata theory. J. Comput. Syst. Sci.31, 28-39 (1985) · Zbl 0582.68018 · doi:10.1016/0022-0000(85)90063-7
[6] Hr86a Hromkovi?, J.: How to organize the communication among parallel processes in alternating computations. (Unpublished manuscript, January 1986)
[7] Hr86b Hromkovi?, J.: Tradeoffs for language recognition on alternating machines. Theor. Comput. Sci.63, 203-221 (1989) · Zbl 0667.68060 · doi:10.1016/0304-3975(89)90078-9
[8] HIRSTW Hromkovi? J., Inoue K., Rovan B., Slobodová A., Takanami I., Wagner K.: On the power of one-way synchronized alternating machines with small space. Int. J. Foundat. Comput. Sci. (to appear) · Zbl 0769.68030
[9] HKRS Hromkovi? J., Karhumäki J., Rovan B., Slobodová A.: On the power of synchronization in parallel computations. Discrete Appl. Math.32, 155-182 (1991) · Zbl 0734.68036 · doi:10.1016/0166-218X(91)90098-H
[10] IT91 Ibarra O.H., Tran N.Q.: On space-bounded synchronized alternating Turing machines. Proc. 8th FCT ’91 (Lect. Notes Comput. Sci., Vol. 529, pp. 248-257) Berlin Heidelberg New York: Springer 1991 · Zbl 0925.03183
[11] IT92 Ibarra O.H., Tran N.Q.: New results concerning synchronized finite automata (accepted for ICALP ’92)
[12] Kin81 King, K.N.: Alternating multihead finite automata. Proc. 8th ICALP’81. (Lect. Notes Comput. Sci., Vol. 115, pp. 506-520) Berlin Heidelberg New York: Springer 1981
[13] LLS84 Ladner, R.J., Lipton, R.J., Stockmeyer, L.J.: Alternating pushdown and stack automata. SIAM J. Comput.13, 135-155 (1984) · Zbl 0538.68039 · doi:10.1137/0213010
[14] Min61 Minsky, M.L.: Recursive unsolvability of Post’s problem of ?Tag? and other topics in the theory of Turing machines. Ann. Math.74, 437-455 (1961) · Zbl 0105.00802 · doi:10.2307/1970290
[15] PPR80 Paul, W.J., Prauss, E.J., Reischuk, R.: On alternation. Acta Inf.14, 243-255 (1980) · Zbl 0437.68025 · doi:10.1007/BF00264255
[16] Slo87 Slobodová, A.: On the power of communication in alternating computations. Student Research Paper Competition, Section Computer Science, Comenius University, Bratislava, April 1987 (in Slovak)
[17] Slo88 Slobodová, A.: On the power of communication in alternating machines. MFCS’88 (Lect. Notes Comput. Sci., Vol. 324, pp. 518-528). Berlin Heidelberg New York: Springer 1988
[18] Slo92 Slobodová, A.: Some properties of space-bounded synchronized alternating Turing machines with universal states only. Theor. Comput. Sci.96, 411-419 (1992) · Zbl 0754.68047 · doi:10.1016/0304-3975(92)90346-H
[19] Slo90 Slobodová, A.: One-way globally deterministic synchronized alternating finite automata recognize exactly deterministic context-sensitive languages. Inf. Process. Lett.36, 69-72 (1990) · Zbl 0704.68068 · doi:10.1016/0020-0190(90)90099-J
[20] Sud75 Sudborough, I.H.: On tape-bounded complexity classes. J. Comput. System Sci.10, 62-76 (1975) · Zbl 0299.68031 · doi:10.1016/S0022-0000(75)80014-6
[21] VEB88 van Emde Boas, P.: The second machine class 2, an encyclopedic view on the Parallel computation thesis. In: Rasiowa, H. (ed.) Mathematical problems in computational theory. (Banach Center Publications, Vol. 21, pp. 235-256). Warsaw: PWN-Polish Scientific Publishers 1988 · Zbl 0760.68027
[22] WW86 Wagner, K., Wechsung, G.: Computational complexity. (Mathematische Monographien 19) Berlin: Deutscher Verlag der Wissenschaften 1986
[23] Wie89 Wiedermann J.: On the power of synchronization. J. Inf. Process. Cybern. Elk25 (10), 499-506 (1989) · 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.