On uniform circuit complexity. (English) Zbl 0462.68013

Ruzzo, Walter L.

J. Comput. Syst. Sci. 22, 365-383 (1981).

MSC:

68Q25	Analysis of algorithms and problem complexity
68Q05	Models of computation (Turing machines, etc.) (MSC2010)
94C10	Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
68Q45	Formal languages and automata

Keywords:

parallel complexity; alternating Turing machines; context-free language recognition

References:

[1]	Aho, A.V.; Hopcroft, J.E.; Ullman, J.D., The design and analysis of computer algorithms, (1974), Addison-Wesley Reading, Mass · Zbl 0286.68029
[2]	Borodin, A., On relating time and space to size and depth, SIAM J. comput., 6, No. 4, 733-743, (1977) · Zbl 0366.68039
[3]	Colbourn, C.J.; Booth, K.S., Linear time automorphism algorithms for trees, interval graphs, and planar graphs, () · Zbl 0456.05024
[4]	Cook, S.A., Characterizations of pushdown machines in terms of time-bounded computers, J. assoc. comput. Mach., 18, No. 1, 4-18, (1971) · Zbl 0222.02035
[5]	Cook, S.A., Deterministic CFL’s are accepted simultaneously in polynomial time and log squared space, (), 338-345
[6]	Chandra, A.K.; Kozen, D.C.; Stockemeyer, L.J., Alternation, J. assoc. comput. Mach., 28, No. 1, 114-133, (1981) · Zbl 0473.68043
[7]	Csanky, L., Fast parallel matrix inversion algorithms, (), 11-12 · Zbl 0353.68063
[8]	Dymond, P.W.; Cook, S.A., Hardware complexity and parallel computation, (), 360-372
[9]	W. Erni, Some Further Languages Log-Tape Reducible to Context-Free Languages, Institüt für Angewandte Informatik ünd Formale, Beschreibüngverfahren, Universität Karlsrühe, Karlsrühe, West Germany.
[10]	Fortune, S.; Wyllie, J., Parallelism in random access machines, (), 114-118 · Zbl 1282.68104
[11]	Goldschlager, L.M., Synchronous parallel computation, ()
[12]	Goldschlager, L.M., A unified approach to models of synchronous parallel machines, (), 89-94 · Zbl 1282.68105
[13]	Hartmanis, J.; Simon, J., On the power of multiplication in random access machines, (), 13-23
[14]	Ladner, R.E., The circuit value problem is log space complete for P, SIGACT news, 7, No. 1, 18-20, (1975)
[15]	Pippenger, N.; Fischer, M.J., Relations among complexity measures, J. assoc. comput. Mach., 26, No. 2, 361-381, (1979) · Zbl 0405.68041
[16]	Pippenger, N., Fast simulation of combinational logic networks by machines without random-access storage, IBM research report RC 6582, (1977)
[17]	Pippenger, N., On simultaneous resource bounds, ()
[18]	Pippenger, N., Pebbling with an auxiliary pushdown, IBM research report RJ3012, (1980) · Zbl 0468.68067
[19]	Pratt, V.R.; Rabin, M.O.; Stockmeyer, L.J., A characterization of the power of vector machines, (), 122-134
[20]	Pratt, V.R.; Stockmeyer, L.J., A characterization of the power of vector machines, J. comput. system sci., 12, 198-221, (1976) · Zbl 0342.68033
[21]	Paul, W.J.; Tarjan, R.E., Time-space trade-offs in a pebble game, Acta inform., 10, 111-115, (1978) · Zbl 0399.05030
[22]	Ruzzo, W.L., Tree-sized bounded alternation, J. comput. system sci., 21, 218-235, (1980) · Zbl 0445.68034
[23]	W. L. Ruzzo, “An improved characterization of the power of vector machines,” University of Washington, Computer Science Department Technical Report 78-10-01, in preparation.
[24]	Savitch, W.J., Parallel and nondeterministic time complexity classes, (), 411-424
[25]	Schnorr, C.P., The network complexity and the Turing machine complexity of finite functions, Acta inform., 7, 95-107, (1976) · Zbl 0338.02019
[26]	Savitch, W.J.; Stimson, M.J., Time bounded random access machines with parallel processing, J. assoc. comput. Mach., 26, No. 1, 103-118, (1979) · Zbl 0398.68014
[27]	Stockmeyer, L.J., The polynomial-time hierarchy, Theoret. comput. sci., 3, 1-22, (1976) · Zbl 0353.02024
[28]	Sudborough, I.H., Time and tape bounded auxiliary pushdown automata, (), 493-503 · Zbl 0366.68037
[29]	Sudborough, I.H., The complexity of the membership problem for some extensions of context-free languages, Internat. J. comput. math. A, 6, 191-215, (1977) · Zbl 0398.68037