Tradeoffs for language recognition on alternating machines. (English) Zbl 0667.68060

Hromkovič, Juraj

Theor. Comput. Sci. 63, No. 2, 203-221 (1989).

From the author’s abstract: “The alternating machine having a separate input tape with k two-way, read-only heads, and a certain number of internal configurations, AM(k), is considered as a parallel computing model. For the complexity measure TIME-SPACE-PARALLELISM, the optimal lower bounds \(\Omega (n^ 2)\) and \(\Omega (n^{3/2})\) respectively are proved for the recognition of specific languages on AM(1) and AM(k) respectively. For the complexity measure REVERSALS-SPACE-PARALLELISM, the lower bound \(\Omega (n^{1/2})\) is established for the recognition of a specific language on AM(k). This result implies a polynomial lower bound PARALLEL TIME-HARDWARE of parallel RAMS’s. Lower bounds on the complexity measures TIME-SPACE and REVERSALS-SPACE of nondeterministic machines are direct consequences of the result introduced above.”

Reviewer: M.Clausen

MSC:

68Q25	Analysis of algorithms and problem complexity
68Q05	Models of computation (Turing machines, etc.) (MSC2010)
03D15	Complexity of computation (including implicit computational complexity)

Keywords:

language recognition; alternating machine; complexity measure; TIME- SPACE-PARALLELISM; RAMS

References:

[1]	Andreev, A. E., On a method of obtaining lower bounds to the complexity of individual monotone functions, Dokl. Akad. Nauk SSSR, 282, 5, 1033-1037 (1985), (in Russian) · Zbl 0616.94019
[2]	Blum, N. A., Boolean functions requiring \(3n\) network size, Theoret. Comput. Sci., 28, 337-345 (1984) · Zbl 0539.94036
[3]	Borodin, A. B.; Cook, S. A., A time-space tradeoff for sorting on a general model of computation, Proc. 12th ACMSTOC, 294-301 (1980)
[4]	Brandenburg, F. J., Three write heads are as good as \(k\), Math. Systems Theory, 14, 1-12 (1981) · Zbl 0437.68029
[5]	Brandenburg, F. J., On one-way auxiliary pushdown automata, (Lecture Notes in Computer Science, 48 (1979), Springer: Springer Berlin), 132-144 · Zbl 0359.68055
[6]	Chan, T., Reversal complexity of counter machines, Proc. 13th Ann. ACMSTOC, 147-157 (1981)
[7]	Chandra, A. K.; Kozen, D. C.; Stockmeyer, L. J., Alternation, J. ACM, 28, 114-133 (1981) · Zbl 0473.68043
[8]	Chrobak, M., Hierarchies of one-way multihead automata languages, (Proc. 12th ICALP ’85. Proc. 12th ICALP ’85, Lecture Notes in Computer Science, 194 (1985), Springer: Springer Berlin), 101-110 · Zbl 0638.68097
[9]	Cobham, A., The recognition problem for perfect squares, Proc. 7th IEEE Symp. on SWAT, 78-87 (1966)
[10]	Cook, S. A., An overview of computational complexity, Comm. ACM, 26, 400-408 (1983) · Zbl 0622.68039
[11]	Dˇurisˇ, P.; Galil, Z., Fooling a two-way automaton or one pushdown store is better than one counter for two-way machines, Theoret. Comput. Sci., 21, 39-53 (1982) · Zbl 0486.68084
[12]	Dˇurisˇ, P.; Galil, Z., A time-space tradeoff for language recognition, Math. Systems Theory, 17, 3-12 (1984) · Zbl 0533.68047
[13]	Dˇurisˇ, P.; Galil, Z., On reversal-bounded counter machines and on pushdown automata with a bound on the pushdown store, Inform. and Control, 54, 217-227 (1982) · Zbl 0523.68037
[14]	Dˇurisˇ, P.; Galil, Z.; Paul, W.; Reischik, R., Two nonlinear lower bounds, Proc. 15th ACM STOC, 127-132 (1983)
[15]	Dˇurisˇ, P.; Hromkovicˇ, J., One-way simple multihead finite automata are not closed under concatenation, Theoret. Comput. Sci., 27, 121-125 (1983) · Zbl 0523.68070
[16]	Dymond, P. W.; Cook, S. A., Hardware complexity and parallel computation, Proc. 21st Ann. IEEE FOCS, 360-372 (1980)
[17]	R. Freivalds, Relation between probabilistic and nondeterministic Turing machines, Unpublished communication presented at the 11th MFCS ’84, Prague.; R. Freivalds, Relation between probabilistic and nondeterministic Turing machines, Unpublished communication presented at the 11th MFCS ’84, Prague.
[18]	Hopcroft, J. E.; Ullman, J. D., Formal Languages and their Relation to Automata (1969), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0196.01701
[19]	Hromkovicˇ, J., One-way multihead deterministic finite automata, Acta Inform., 19, 377-384 (1983) · Zbl 0504.68049
[20]	Hromkovicˇ, J., Hierarchy of reversal and zero-testing bounded multicounter machines, (Proc. 11th MFCS ’84. Proc. 11th MFCS ’84, Lecture Notes in Computer Science, 176 (1984), Springer: Springer Berlin), 312-321 · Zbl 0582.68049
[21]	Hromkovicˇ, J., Fooling a two-way nondeterministic multihead automaton with reversal number restriction, Acta Inform., 22, 589-594 (1985) · Zbl 0565.68078
[22]	Hromkovicˇ, J., On the power of alternation in automata theory, J. Comput. System Sci., 31, 28-39 (1985) · Zbl 0582.68018
[23]	Hromkovicˇ, J., On one-way two-head deterministic finite state automata, Computers AI, 4, 503-526 (1985) · Zbl 0605.68079
[24]	Hromkovicˇ, J., Reversals-Space-Parallelism tradeoff for language recognition (1985), Unpublished manuscript
[25]	Ibarra, O. H., Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata, J. Comput. System Sci., 5, 81-117 (1971) · Zbl 0255.68012
[26]	Ibarra, O. H., On two-way multihead automata, J. Comput. System Sci., 7, 28-37 (1973) · Zbl 0256.68028
[27]	Ibarra, O. H.; Kim, C. E., On 3-head versus 2-head finite automata, Acta Inform., 4, 173-200 (1975) · Zbl 0291.94029
[28]	Inoue, K.; Takanami, I.; Nakamura, A.; Ae, T., One-way simple multihead finite automata, Theoret. Comput. Sci., 9, 311-328 (1979) · Zbl 0408.68050
[29]	Inoue, K.; Matsuno, H.; Taniguschi, H.; Takanami, I., Alternating simple multihead finite automata, Theoret. Comput. Sci., 36, 291-308 (1985) · Zbl 0565.68055
[30]	Janiga, L., Real-time computations of two-way multihead finite automata, (Budach, L., Proc. FCT ’79 (1979), Akademie Verlag: Akademie Verlag Berlin), 214-219 · Zbl 0413.68085
[31]	King, K. N., Alternating multihead finite automata, (Proc. 8th ICALP ’81. Proc. 8th ICALP ’81, Lecture Notes in Computer Science, 115 (1981), Springer: Springer Berlin), 506-520 · Zbl 0665.68064
[32]	Lupanov, O. B., Ob odnom metode sinteza schem, Izv. Vazov Radiofiz., 1, 120-140 (1958), (in Russian)
[33]	Lupanov, O. B., O sinteze nekatorych klassov upravljajusˇcˇich sistem, Problemi Kibernetiki, 10, 63-97 (1963), (in Russian)
[34]	Maas, W., Quadratic lower bounds for deterministic and nondeterministic one-tape Turing machines, Proc. 16th Ann. ACM STOC, 401-408 (1984)
[35]	Ming, Li, On one tape versus two stacks, (Tech. Rept. 84-591 (January 1984), Dept. of Computer Science, Cornell University: Dept. of Computer Science, Cornell University Ithaca, New York)
[36]	Ming, Li, Simulating two pushdowns by one tape in \(n^{1.5}(log_2\) n)\(^{0.5}\) time, Proc. 26th Ann. IEEE FOCS, 56-64 (1985)
[37]	Ming, Li; Vitányi, P. M.B., Tape versus queue and stack: The lower bounds, Centrum voor Wiskunde en Informatica, Rept. CS-R8519 (September 1985)
[38]	Monien, B., Two-way multihead automata over a one-letter alphabet, RAIRO Inform. Théor., 14, 67-82 (1980) · Zbl 0442.68039
[39]	Monien, B.; Sudborough, I. H., The interface between language theory and complexity theory, (Book, R. V., Formal Language Theory, Perspectives and Open Problems (1981), Academic Press: Academic Press New York), 287-323
[40]	Necˇiporuk, E. J., A Boolean function, Dokl. Akad. Nauk SSSR, 169, 765-766 (1966) · Zbl 0161.00901
[41]	Nigmatulin, R. G., Proc. 8th ICALP ’81 (1983), Kazan State University Press, (in Russian)
[42]	Paul, W. J., On time hierarchies, J. Comput. System Sci., 19, 197-202 (1979) · Zbl 0428.68055
[43]	Piatkowski, T. F., \(N\)-head finite-state machines, (Ph.D. Dissertation (1963), University of Michigan) · Zbl 0173.01503
[44]	Pudlák, P., A lower bound on complexity of branching programs, (Proc. 11th MFCS ’84. Proc. 11th MFCS ’84, Lecture Notes in Computer Science, 176 (1984), Springer: Springer Berlin), 480-490 · Zbl 0572.68033
[45]	Razborov, A. A., Lower bounds on the monotone complexity of some Boolean functions, Soviet Math. Doklady, 281, 798-801 (1985) · Zbl 0621.94027
[46]	Rivest, R. L.; Yao, A. C., \(k+1\) heads are better than \(k\), J. ACM, 25, 337-340 (1978) · Zbl 0372.68017
[47]	Rosenberg, A. L., On multihead finite automata, IBM J. Res. Develop., 10, 388-394 (1966) · Zbl 0168.01303
[48]	Sakoda, W. J.; Sipser, M., Nondeterminism and the size of two-way finite automata, Proc. 10th Ann. ACM STOC, 275-286 (1978) · Zbl 1282.68160
[49]	Sudborough, I. H., Bounded-reversal multihead finite automata languages, Inform. and Control, 25, 317-328 (1974) · Zbl 0282.68033
[50]	Sudborough, I. H., One-way multihead writing finite automata, Inform. and Control, 39, 1-20 (1976) · Zbl 0337.02023
[51]	Vitányi, P. M.B., The simple roots of real-time computation hierarchies, (Proc. 11th ICALP ’84. Proc. 11th ICALP ’84, Lecture Notes in Computer Science, 172 (1984), Springer: Springer Berlin), 486-489 · Zbl 0477.68047
[52]	Vitányi, P. M.B., Square time is optimal for simulation of one pushdown store or one queue by an oblivious one-head tape unit, Inform. Process. Lett, 21, 87-91 (1985) · Zbl 0575.68051
[53]	Vitányi, P. M.B., An \(n^{1.618}\) lower bound one the time to simulate one queue or two pushdown stores by one tape, Inform. Process. Lett., 21, 147-152 (1985) · Zbl 0582.68019
[54]	Wagner, K.; Wechsung, G., Computational Complexity, (Matematische Monographien (1986), VEB Deutshcer Verlag der Wissenshaften: VEB Deutshcer Verlag der Wissenshaften Berlin) · Zbl 0584.68061