A space lower bound for acceptance by one-way Π 2 -alternating machines
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 34 (2000) no. 5, pp. 357-372. 
@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},
     pages = {357--372},
     publisher = {EDP-Sciences},
     volume = {34},
     number = {5},
     year = {2000},
     mrnumber = {1829232},
     zbl = {0987.68038},
     language = {en},
     url = {http://archive.numdam.org/item/ITA_2000__34_5_357_0/}
}
TY  - JOUR
AU  - Geffert, Viliam
AU  - Popély, Norbert
TI  - A space lower bound for acceptance by one-way $\Pi _2$-alternating machines
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2000
SP  - 357
EP  - 372
VL  - 34
IS  - 5
PB  - EDP-Sciences
UR  - http://archive.numdam.org/item/ITA_2000__34_5_357_0/
LA  - en
ID  - ITA_2000__34_5_357_0
ER  - 
%0 Journal Article
%A Geffert, Viliam
%A Popély, Norbert
%T A space lower bound for acceptance by one-way $\Pi _2$-alternating machines
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2000
%P 357-372
%V 34
%N 5
%I EDP-Sciences
%U http://archive.numdam.org/item/ITA_2000__34_5_357_0/
%G en
%F 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) no. 5, pp. 357-372. http://archive.numdam.org/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 | Zbl

[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 | Zbl

[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 | Zbl

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

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

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

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

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

[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

[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

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

[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

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

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

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

[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 | Zbl

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

[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 | Zbl