Previous |  Up |  Next


[1] Borodin A. B., Cook S. A.: A time-space tradeoff for sorting on a general sequential model of computation. Proc. 12th ACM STOC, Los Angeles, Calif. (1980), 294-301.
[2] Borodin A. B., Fischer M. J., Kirkpatrick D. G., Lynch N. A., Tompa M.: A time-space tradeoff for sorting on non-obliviona machines. Proc. 20th IEEE Symp. on FOCS, San Juan, Puerto Rico (1979), 319-327.
[3] Ďuriš P., Galil Z.: On reversal-bounded counter machines and on pushdown automata with a bound on the size of the pushdown store. Information and Control 54 (1982), 217-227. MR 0719444
[4] Galil Z.: Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages. Math. Systems Th. 10 (1977), 211-228. MR 0438812 | Zbl 0356.68064
[5] Chan T.: Reversal complexity of counter machines. Proc. 13th ACM STOC, Milwauke (1981), 146-157.
[6] Chrobak M.: Variations on the technique of Ďurš and Galil. J. Comput. and Syst. Sci. 30 (1985), 77-85. MR 0788832
[7] Janiga L.: Real-time computations of two-way multihead finite automata. in "L. Budach, Ed.: Fundamentals of computation theory FCT 79", Akademie Verlag, Berlin, 1979, 214-218 MR 0563679 | Zbl 0413.68085
[8] Yao A. C., Rivest R. L.: $K+1$ heads are better than k. Journal of ACM 25 (1978), 337-340. MR 0483728 | Zbl 0372.68017
Partner of
EuDML logo