×

A time-space tradeoff for language recognition. (English) Zbl 0533.68047

This paper presents a language L and proves that if L is recognized in time T(n) and space S(n), then it must be \(T^ 2(n)S(n)>cn^ 3\) for some constant c. The underlying nondeterministic machine model allows an arbitrary (but constant) number k of heads on the (read-only) input tape. The storage can be organized arbitrarily, even random access is allowed. The multiple access to the input is an improvement over the previously known lower bounds of \(\Omega(n^ 2)\) for \(S\cdot T\) for the recognition of certain languages, because there only one head was allowed. The proof of the lower bound is based on a counting argument on the number of different configurations for a given time and space. From the main result it follows as a corollary that the class of languages recognizable by 2- way multihead deterministic finite automata is properly contained in the corresponding nondeterministic class, if T(n) grows more slowly than \((n^ 3/\log n)^{1/2}\) for infinitely many n.
Reviewer: H.Alt

MSC:

68Q25 Analysis of algorithms and problem complexity
68Q45 Formal languages and automata
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A. Cobham, The recognition problem for perfect squares,Proceedings 7th IEEE Symposium on SWAT, Berkeley, Calif., October 1966, 78–87.
[2] A. B. Borodin, M. J. Fischer, D. G. Kirkpatrick, N. A. Lynch, and M. Tompa, A time-space tradeoff for sorting on non-oblivious machines.Proceedings 20th IEEE Symposium on FOCS, San Juan, Puerto Rico, October 1979, 319–327. · Zbl 0462.68011
[3] A. B. Borodin and S. A. Cook, A time-space tradeoff for sorting on a general sequential model of computation,Proceedings 12th ACM, STOC., Los Angeles, Calif., April 1980, 294–301.
[4] Z. Galil and J. Seiferas, Time-space-optimal string matching,J. Computer Sys. Sciences 26 (1983), 280–294. · Zbl 0509.68101 · doi:10.1016/0022-0000(83)90002-8
[5] R. L. Rivest and A. C. C. Yao,k+1 heads are better thank, JACM 25, 2(1978), 337–340. · Zbl 0372.68011 · doi:10.1145/322063.322065
[6] L. Janiga, Real-time computations of two-way multihead finite automata, inFundamentals of Computation Theory (FCT 79) (L. Budach ed.), Akademic Verlag, Berlin, 214–219.
[7] P. Dúriś and Z. Galil, Fooling a two way automaton or One pushdown store is better than one counter for two way machines,Theoretical Computer Science 21 (1982), 39–53. · Zbl 0486.68084 · doi:10.1016/0304-3975(82)90087-1
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.