A space lower bound for acceptance by one-way ${\Pi }_2$-alternating machines

 Access to full text

 Full (PDF)

1. [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. Zbl0574.68040MR821218
2. [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. [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. Zbl1193.68119MR1467265
4. [4] A. Bertoni, C. Mereghetti and G. Pighizzini, Space and reversal complexity of nonregular languages, Technical Report, University of Milano (1998). Zbl0810.68089
5. [5] A. K. Chandra, D. C. Kozen and L. J. Stockmeyer, Alternation. J. Assoc. Comput. Math. 28 (1981) 114-33. Zbl0473.68043MR603186
6. [6] P. Van Emde Boas, Machine models and simulations, edited by J. van Leeuwen, Handbook of Theoretical Computer Science. Elsevier Science (1989). Zbl0900.68265MR1127167
7. [7] R. Freivalds, On the work time of deterministic and nondeterministic Turing machines. Latv. Mat. Ezhegodnik 23 (1979) 158-65 (in Russian). Zbl0462.68028MR562395
8. [8] V. Geffert, Nondeterministic computations in sublogarithmic space and space constructibility. SIAM J. Comput. 20 (1991) 484-98. Zbl0762.68022MR1094527
9. [9] V. Geffert, A hierarchy that does not collapse: Alternations in low level space. RAIRO: Theoret Informatics Appl. 28 (1994) 465-512. Zbl0884.68054MR1296648
10. [10] V. Geffert, C. Mereghetti and G. Pighizzini, Sublogarithmic bounds on space and reversals. SIAM J. Comput. 28 (1999) 325-40. Zbl0914.68068MR1630493
11. [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. Zbl0229.02033
12. [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. Zbl0272.68054
13. [13] J. E. Hopcroft and J. D. Ullman, Some results on tape-bounded Turing machines. J. Assoc. Comput. Mach. 16 (1969) 168-77. Zbl0188.33501
14. [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. Zbl0821.68056
15. [15] K. Iwama, ASPACE(o(log log n)) is regular. SIAM J. Comput. 22 (1993) 136-46. Zbl0767.68039
16. [16] B. E. Ladner, R. J. Lipton and L. R. Stockmeyer, Alternation bounded auxiliary pushdown automata. Inform. and Control 62 (1984) 93-108. Zbl0589.68058
17. [17] C. Mereghetti and G. Pighizzini, A remark on middle space bounded alternating Turing machines. Inform. Process. Lett. 56 (1995) 229-32. Zbl0875.68395
18. [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). Zbl0980.68048MR1650797
19. [19] W. J. Savitch, Relationships between nondeterministic and deterministic tape complexities. J. Comput. System Sci. 4 (1970) 177-92. Zbl0188.33502MR266702
20. [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. [21] A. Szepietowski, Remarks on languages acceptable in log log n space. Inform. Process Lett. 27 (1988) 201-3. Zbl0652.68055MR935245