A space lower bound for acceptance by one-way Π 2 -alternating machines
Geffert, Viliam ; Popély, Norbert
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 34 (2000), p. 357-372 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 2000-01-01
@article{ITA_2000__34_5_357_0,
     author = {Geffert, Viliam and Pop\'ely, Norbert},
     title = {A space lower bound for acceptance by one-way $\Pi \_2$-alternating machines},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {34},
     year = {2000},
     pages = {357-372},
     mrnumber = {1829232},
     zbl = {0987.68038},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2000__34_5_357_0}
}

Geffert, Viliam; Popély, Norbert. A space lower bound for acceptance by one-way $\Pi _2$-alternating machines. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 34 (2000) pp. 357-372. http://gdmltest.u-ga.fr/item/ITA_2000__34_5_357_0/

[1] M. Alberts, Space complexity of alternating Turing machines, in Proc. Fund. Comput. Theory. Springer-Verlag, Lecture Notes in Comput Sci. 199 (1985) 1-7. | MR 821218 | Zbl 0574.68040

[2] H. Alt and K. Mehlhorn, A language over a one symbol alphabet requiring only O (log log n) space. SIGACT News 7 (1975) 31-33.

[3] A. Bertoni, C. Mereghetti and G. Pighizzini, Strong optimal lower bounds for Turing machines that accept nonregular languages, in Proc. Math. Found. Comput. Sci. Springer-Verlag, Lecture Notes in Comput. Sci. 969 (1995) 309-18. | MR 1467265 | Zbl 1193.68119

[4] A. Bertoni, C. Mereghetti and G. Pighizzini, Space and reversal complexity of nonregular languages, Technical Report, University of Milano (1998).

[5] A. K. Chandra, D. C. Kozen and L. J. Stockmeyer, Alternation. J. Assoc. Comput. Math. 28 (1981) 114-33. | MR 603186 | Zbl 0473.68043

[6] P. Van Emde Boas, Machine models and simulations, edited by J. van Leeuwen, Handbook of Theoretical Computer Science. Elsevier Science (1989). | MR 1127167 | Zbl 0900.68265

[7] R. Freivalds, On the work time of deterministic and nondeterministic Turing machines. Latv. Mat. Ezhegodnik 23 (1979) 158-65 (in Russian). | MR 562395 | Zbl 0462.68028

[8] V. Geffert, Nondeterministic computations in sublogarithmic space and space constructibility. SIAM J. Comput. 20 (1991) 484-98. | MR 1094527 | Zbl 0762.68022

[9] V. Geffert, A hierarchy that does not collapse: Alternations in low level space. RAIRO: Theoret Informatics Appl. 28 (1994) 465-512. | Numdam | MR 1296648 | Zbl 0884.68054

[10] V. Geffert, C. Mereghetti and G. Pighizzini, Sublogarithmic bounds on space and reversals. SIAM J. Comput. 28 (1999) 325-40. | MR 1630493 | Zbl 0914.68068

[11] J. Hartmanis, P. M. Lewis Ii and R. E. Stearns, Hierarchies of memory limited computations, in IEEE Conf. Record on Switching Circuit Theory and Logical Design (1965) 179-90. | Zbl 0229.02033

[12] J. Hartmanis, P. M. Lewis Ii and R. E. Stearns, Memory bounds for recognition of context-free and context-sensitive languages, in IEEE Conf. Record on Switching Circuit Theory and Logical Design (1965) 191-202. | Zbl 0272.68054

[13] J. E. Hopcroft and J. D. Ullman, Some results on tape-bounded Turing machines. J. Assoc. Comput. Mach. 16 (1969) 168-77. | Zbl 0188.33501

[14] J. Hromkovič, B. Rovan and A. Slobodová, Deterministic versus nondeterministic space in terms of synchronized alternating machines. Theoret Comput. Sci. 132 (1994) 319-36. | Zbl 0821.68056

[15] K. Iwama, ASPACE(o(log log n)) is regular. SIAM J. Comput. 22 (1993) 136-46. | Zbl 0767.68039

[16] B. E. Ladner, R. J. Lipton and L. R. Stockmeyer, Alternation bounded auxiliary pushdown automata. Inform. and Control 62 (1984) 93-108. | Zbl 0589.68058

[17] C. Mereghetti and G. Pighizzini, A remark on middle space bounded alternating Turing machines. Inform. Process. Lett. 56 (1995) 229-32. | Zbl 0875.68395

[18] C. Mereghetti and G. Pighizzini, Optimal simulations between unary automata, in Proc. Symp. Theoret. Aspects Comput. Sci. Springer-Verlag, Lecture Notes in Comput Sci. 1373 (1998) 139-149 (to appear in SIAM J. Comput). | MR 1650797 | Zbl 0980.68048

[19] W. J. Savitch, Relationships between nondeterministic and deterministic tape complexities. J. Comput. System Sci. 4 (1970) 177-92. | MR 266702 | Zbl 0188.33502

[20] I. H. Sudborough, Efficient algorithms for path system problems and applications to alternating and time-space complexity classes, in Proc. IEEE Symp. Found, of Comput. Sci. (1980) 62-73.

[21] A. Szepietowski, Remarks on languages acceptable in log log n space. Inform. Process Lett. 27 (1988) 201-3. | MR 935245 | Zbl 0652.68055