×

zbMATH — the first resource for mathematics

Deterministic versus nondeterministic space in terms of synchronized alternating machines. (English) Zbl 0821.68056
Summary: The study of synchronized alternating machines has enabled to characterize several natural complexity classes. It is known that synchronized alternating space \(\text{SASPACE}(S(n)) = \bigcup_{c > 0} \text{NSPACE}(nc^{S(n)})\) for any (space-constructible) function \(S(n)\). In particular, context-sensitive languages are characterized by two-way synchronized alternating finite automata. Furthermore, PSPACE is characterized by synchronized alternating multihead finite automata. Furthermore, PSPACE is characterized by synchronized alternating multihead finite automata and NLOG by synchronized alternating two-way finite automata with parallelism bounded by a constant. In the present paper we prove analogous characterizations for deterministic space classes using a restricted form of synchronization – globally deterministic synchronization. This enables to study the well-known open problems concerning nondeterminism versus determinism as problems about synchronization. We also show that globally deterministic synchronization is strictly more powerful than deterministic synchronization.

MSC:
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
03D15 Complexity of computation (including implicit computational complexity)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Chandra, A.K.; Kozen, D.K.; Stockmeyer, Alternation, J. ACM, 28, 1, 114-133, (1981) · Zbl 0473.68043
[2] Dassow, J.; Hromkovicˇ, J.; Karhumäki, J.; Rovan, B.; Slobodová, A., On the power of synchronization in parallel computations, (), 196-206 · Zbl 0755.68045
[3] Geidmanis, D., On possibilities of one-way synchronized alternating and alternating finite automata, (), 292-299
[4] Hartmanis, J.; Lewis, P.M.; Stearns, R.E., Hiearchies of memory limited computations, Proc. 6th ann. IEEE symp. on switching circuit theory and logical design, 179-190, (1965)
[5] Hromkovicˇ, J., One-way multihead deterministic finite automata, Acta inform., 19, 377-384, (1983) · Zbl 0504.68049
[6] Hromkovicˇ, J., On the power of alternation in automata theory, J. comput. sci., 31, 28-39, (1985) · Zbl 0582.68018
[7] Hromkovicˇ, J., How to organize the communication among parallel processes in alternating computations, (1986), Comenius University, Unpublished manuscript
[8] Hromkovicˇ, J., Tradeoffs for language recognition on alternating machines, Theoret. comput. sci., 63, 203-221, (1989) · Zbl 0667.68060
[9] Hromkovicˇ, J.; Inoue, K., A note on realtime one-way synchronized alternating one-counter automata, Theoret. comput. sci., 108, 393-400, (1993) · Zbl 0776.68039
[10] Hromkovicˇ, J.; Inoue, K.; Ito, A.; Takanami, I., On the power of two-dimensional synchronized alternating finite automata, Fund. inform., 15, 90-98, (1991) · Zbl 0737.68060
[11] Hromkovicˇ, J.; Inoue, K.; Rovan, B.; Slobodová, A.; Takanami, I.; Wagner, K., On the power of one-way synchronized alternating machines with small space, Internat. found. comput. sci., 3, 65-79, (1992) · Zbl 0769.68030
[12] Hromkovicˇ, 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
[13] Ibarra, O.H.; Tran, N.Q., On space-bounded synchronized alternating Turing machines, (), 248-257 · Zbl 0925.03183
[14] Ibarra, O.H.; Tran, N.Q., New results concerning synchronized finite automata, (), 126-137
[15] Immerman, N., Nondeterministic space is closed under complementation,, SIAM J. comput., 17, 5, 935-938, (1988) · Zbl 0668.68056
[16] King, K.N., Alternating finite automata, () · Zbl 0665.68064
[17] King, K.N., Alternating multihead finite automata, (), 506-520 · Zbl 0665.68064
[18] Rosenberg, A.L., On multihead finite automata, IBM J. res. develop., 25, 388-394, (1966) · Zbl 0168.01303
[19] Rivest, R.L.; Yao, A.C., k + 1 heads are better than k, J. ACM, 25, 337-340, (1978) · Zbl 0372.68017
[20] Slobodová, A., On the power of communication in alternating computations, (), (in Slovak) · Zbl 0649.68050
[21] Slobodová, A., On the power of communication in alternating machines, (), Acta inform., 29, 425-441, (1992), extended version: Communication for alternating machines · Zbl 0769.68022
[22] Slobodová, A., Some properties of space-bounded synchronized alternating Turing machines with only universal states, (), 411-419 · Zbl 0754.68047
[23] Slobodová, A., One-way globally deterministic synchronized alternating finite automata recognize exactly deterministic context-sensitive languages, Inform. process. lett., 36, 69-72, (1990) · Zbl 0704.68068
[24] Slobodová, A., Some properties of space-bounded synchronized alternating Turing machines with universal states only, Theoret. comput. sci., 96, 411-419, (1992) · Zbl 0754.68047
[25] Szelepcsényi, R., The method of forced enumeration for nondeterministic automata, Acta inform., 26, 279-284, (1988) · Zbl 0638.68046
[26] Wagner, K.; Wechsung, G., Computational complexity, Vol. 19, (1986), Deutscher Verlag der Wissenschaften Berlin, Mathematische Monographien
[27] Wiedermann, J., On the power of synchronization, J. inform. process. cybern. EIK, 25, 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. 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.