Article
Full entry |
PDF
(0.7 MB)
Feedback
PDF
(0.7 MB)
Feedback
References:
[1] BORODIN A. B., COOK S. A.: A time-space tradeoff for sorting on a general model of computation. In: Proc. 12th Annual ACM STOC, Los Angeles, ACM 1980, pp. 294-301.
[2] CHANDRA A. K., KOZEN D. C., STOCKMEYER L. J.: Alternation. J. ACM, 28, 1981, 114-133. MR 0603186 | Zbl 0473.68043
[3] COBHAM A.: The recognition for perfect squares. In: Proc. 7th Annual IEEE Symp. on SWAT, Berkeley 1966, pp. 78-87.
[4] DURIS P., GALIL Z.: A time-space tradeoff for language recognition. Math. Systems Theory, 17, 1984, 3-12. MR 0738748 | Zbl 0533.68047
[5] DURIS P., GALIL Z., PAUL W., REISCHUK R.: Two nonlinear lower bounds. In: Proc. 15th Annual ACM STOC, ACM 1983, pp. 127-132.
[6] FREIVALDS R.: Quadratic lower bound for nondeterministic Turing machines. Unpublished communication at the 11th MFCS '84, Prague 1984.
[7] LUPANOV O. B.: Ob odnom metode sinteza schem. (Russian.) Izv. Vuzov Radiofiz., 1, 1958, 120-140.
[8] HROMKOVIČ J.: One-way multihead deterministic finite automata. Acta Inform., 19, 1983, 377-384. MR 0717992 | Zbl 0504.68049
[9] HROMKOVIČ J.: On the power of alternation in automata theory. J. Comput. Syst. Sci., 31. 1985, 28-39. MR 0813367 | Zbl 0582.68018
[10] HROMKOVIČ J.: Pooling a two-way multihead automaton with reversal number restriction. Acta Inform., 22, 1985, 589-594. MR 0822328
[11] HROMKOVIČ J.: Tradeoffs for language recognition on alternating machines. Theor. Comput. Sci., 63, 1989, 203-221. MR 0984317 | Zbl 0667.68060
[12] JANIGA L.: Real-time computations of two-way multihead finite automata. In: Proc. FCT '79, ed. L. Budach. Academic Verlag, Berlin 1979, pp. 214-219. MR 0563679 | Zbl 0413.68085
[13] KING K. N.: Alternating multihead finite automata. In: Proc. 8th ICALP'81. Lecture Notes in Computer Science 115. Springer-Verlag, Berlin 1981, pp 506-520. Zbl 0471.68060
[14] MAASS W.: Quadratic lower bounds for deterministic and nondeterministic one-tape Turing machines. In: Proc. 16th Annual ACM STOC, ACM 1984, pp. 401-408.
[15] MATSUNO H., INOUE K., TANIGUCHI H., TAKANAMI I.: Alternating simple multihead finite automata. Theor. Comput. Sci., 36, 1985, 299-308. MR 0796305 | Zbl 0565.68055
[16] LI M.: On one tape versus two stacks. Technical Report, 84 591, January 1984, Dept. of Computer Science, Cornell University, Ithaca, New York.
[17] RIVEST R. L., YAO A. C: k + 1 heads are better than k. J. ACM, 25, 1978, 337-340. MR 0483728 | Zbl 0372.68017
[18] SUDBOROUGH I. H.: Bounded-reversal multihead finite automata languages. Informat. Control, 25, 1974, 317-328 MR 0400818 | Zbl 0282.68033
Search
Partner of
