Reversals-space-parallelism tradeoffs for language recognition. (English) Zbl 0749.68030

Hromkovič, Juraj

Math. Slovaca 41, No. 2, 121-136 (1991).

Summary: This paper is devoted to the development of a lower bound proof technique for the general model of alternating computations. The produced, combinatorial technique enables to obtain \(\Omega (n^{1/3}/\log_ 2 n)\) lower bound on the tradeoff of complexity measures REVERSALS\(\cdot\)SPACE\(\cdot\)PARALLELISM for the recognition of a specific language on a general alternating machine with the multihead access to the input and an arbitrary organization of the memory.

MSC:

68Q05	Models of computation (Turing machines, etc.) (MSC2010)
03D15	Complexity of computation (including implicit computational complexity)
68Q45	Formal languages and automata
68Q10	Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q15	Complexity classes (hierarchies, relations among complexity classes, etc.)

Keywords:

alternation; lower bound; tradeoff of complexity measures

References:

[1]	BORODIN A. B., COOK S. A.: A time-space tradeoff for sorting on a general model of computation. 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. · Zbl 0473.68043 · doi:10.1145/322234.322243
[3]	COBHAM A.: The recognition for perfect squares. 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. · Zbl 0533.68047 · doi:10.1007/BF01744430
[5]	DURIS P., GALIL Z., PAUL W., REISCHUK R.: Two nonlinear lower bounds. 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. · Zbl 0504.68049 · doi:10.1007/BF00290734
[9]	HROMKOVIČ J.: On the power of alternation in automata theory. J. Comput. Syst. Sci., 31. 1985, 28-39. · Zbl 0582.68018 · doi:10.1016/0022-0000(85)90063-7
[10]	HROMKOVIČ J.: Pooling a two-way multihead automaton with reversal number restriction. Acta Inform., 22, 1985, 589-594. · Zbl 0565.68078
[11]	HROMKOVIČ J.: Tradeoffs for language recognition on alternating machines. Theor. Comput. Sci., 63, 1989, 203-221. · Zbl 0667.68060 · doi:10.1016/0304-3975(89)90078-9
[12]	JANIGA L.: Real-time computations of two-way multihead finite automata. Proc. FCT ’79 L. Budach. Academic Verlag, Berlin 1979, pp. 214-219. · Zbl 0413.68085
[13]	KING K. N.: Alternating multihead finite automata. 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. 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. · Zbl 0565.68055 · doi:10.1016/0304-3975(85)90048-9
[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. · Zbl 0372.68017 · doi:10.1145/322063.322076
[18]	SUDBOROUGH I. H.: Bounded-reversal multihead finite automata languages. Informat. Control, 25, 1974, 317-328 · Zbl 0282.68033 · doi:10.1016/S0019-9958(74)90994-2