×

Tree-size bounded alternation. (English) Zbl 0445.68034


MSC:

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

References:

[1] Berman, L., Precise bounds for Presberger arithmetic and the reals with addition, (Proceedings, IEEE 18th Symposium on the Foundations of Computer Science (1977)), 95-99
[2] Borodin, A., On relating time and space to size and depth, SIAM J. Comput., 6, 4, 733-743 (1977) · Zbl 0366.68039
[3] Chomsky, N., Context Free Grammars and Pushdown Storage, MIT Research Lab. of Electronics, Quarterly Progress Report 65 (1962)
[4] Cook, S. A., Path systems and language recognition, (Proceedings, 2nd Annual ACM Symposium on Theory of Computing (1970)), 70-72
[5] Cook, S. A., Characterizations of pushdown machines in terms of time-bounded computers, J. Assoc. Comput. Mach., 18, 1, 4-18 (Jan 1971) · Zbl 0222.02035
[6] Chandra, A. K.; Stockmeyer, L. J., Alternation, (Proceedings, IEEE 17th Annual Symposium on Foundations of Computer Science (1976)), 98-108
[7] Chandra, A. K.; Kozen, D.; Stockmeyer, L. J., Alternation, (Report RC 7489 (1978), IBM research division: IBM research division Yorktown Heights, N.Y) · Zbl 0473.68043
[8] W. Erni, “Some Further Languages Log-Tape Reducible to Context-Free Languages,” Institut fur Angewandte Informatik and Formale Beschreibungverfahren, Universität Karlsruhe, W. Germany.; W. Erni, “Some Further Languages Log-Tape Reducible to Context-Free Languages,” Institut fur Angewandte Informatik and Formale Beschreibungverfahren, Universität Karlsruhe, W. Germany.
[9] Fischer, M. J.; Ladner, R. E., Parallel Prefix Computations, Univ. of Washington TR 77-03-02 (March 1977)
[10] Fischer, M. J.; Ladner, R. E., Propositional modal logic of programs, (Proceedings, 9th Annual ACM Symposium on Theory of Computing (1977)), 286-294
[11] Gurari, E. M.; Ibarra, O. H., Path systems: constructions, solutions, and applications, SIAM J. Comput., 9, 2, 348-374 (1980) · Zbl 0447.68049
[12] Goldschlager, L. M., A unified approach to models of synchronous parallel machines, (Proceedings, 9th ACM Symposium on Theory of Computing (1978)), 89-94 · Zbl 1282.68105
[13] Jones, N. D., Space bounded reducibility among combinatorial problems, J. Comput. System Sci., 11, 68-85 (Aug 1975) · Zbl 0317.02039
[14] Kozen, D., On parallelism in Turing machines, (Proceedings, IEEE 17th Annual Symposium on Foundations of Computer Science (1976)), 89-97
[15] Kozen, D., Complexity of Boolean Algebras, (Report RC 7488 (1979), IBM research division: IBM research division Yorktown Heights, N.Y) · Zbl 0428.03036
[16] Lewis, H. R., Complexity Results for Classes of Quantificational Formulas, Harvard Univ. Aiken Computation Laboratory, TR-02-79 (1979)
[17] Ladner, R. E.; Lipton, R. J.; Stockmeyer, L. J., Alternating pushdown automata, (Proceedings, 19th IEEE Symposium on Foundations of Computer Science (1978)), 92-106
[18] Lewis, P. M.; Stearns, R. E.; Hartmanis, J., Memory bounds for recognition of contextfree and context sensitive languages, (Proceedings, IEEE 6th Annual Symposium on Switching Circuit Theory and Logic Design (1965)), 191-202 · Zbl 0272.68054
[19] Monien, B., Relationships between pushdown automata and tape-bounded Turing machines, (Vivat, M., Automata, Languages, and Programming (1972), American Elsevier: American Elsevier New York), 575-583 · Zbl 0268.68032
[20] Ofman, Yu. P., On the algorithmic complexity of discrete functions, Sov. Phys. Dokl., 7, 589-591 (1963) · Zbl 0132.24803
[21] Pippenger, N., On simultaneous resource bounds, (Proceedings, IEEE 20th Symposium on Foundations of Computer Science (1979)), 307-311
[22] Pratt, V. R.; Rabin, M. O.; Stockmeyer, L. J., A characterization of the power of vector machines, (Proceedings, 6th Annual ACM Symposium on Theory of Computing (1974)), 122-134 · Zbl 0381.68039
[23] Pratt, V. R.; Stockmeyer, L. J., A characterization of the power of vector machines, J. Comput. Systems Sci., 12, 2, 198-221 (1976) · Zbl 0342.68033
[24] Ruzzo, W. L., General Context-Free Language Recognition, (Ph.D. Dissertation (1978), University of California: University of California Berkeley) · Zbl 0596.68047
[25] Ruzzo, W. L., Tree-size bounded alternation, (Proceedings, 11th ACM Symposium on Theory of Computing (1979)), 352-359 · Zbl 0445.68034
[26] Ruzzo, W. L., On uniform circuit complexity, (Proceedings, IEEE 20th Symposium on Foundations of Computer Science (1979)), 312-318
[27] W. L. Ruzzo, “An Improved Characterization of the Power of Vector Machines,” University of Washington Computer Science Department Technical Report 78-10-01, in press.; W. L. Ruzzo, “An Improved Characterization of the Power of Vector Machines,” University of Washington Computer Science Department Technical Report 78-10-01, in press.
[28] Savitch, W. J., Relationships between nondeterministic and deterministic tape complexities, J. Comput. System Sci., 4, 2, 177-192 (1970) · Zbl 0188.33502
[29] Schützenberger, M. P., On context-free languages and pushdown automata, Inform. Contr., 6, 246-264 (1963) · Zbl 0123.12502
[30] Stockmeyer, L. J.; Chandra, A. K., Provably difficult combinatorial games, SIAM J. Comput., 8, 151-174 (May 1979) · Zbl 0421.68044
[31] Stockmeyer, L. J.; Meyer, A. R., Word problems requiring exponential time, (Proceedings, 5th ACM Symposium on Theory of Computing (1973)), 1-9 · Zbl 0359.68050
[32] Sudborough, I. H., A note on tape-bounded complexity classes and linear context-free languages, J. Assoc. Comput. Mach., 22, 4, 499-500 (Oct 1975) · Zbl 0318.68048
[33] Sudborough, I. H., Time and tape bounded auxiliary pushdown automata, (Mathematical Foundations of Computer Science. Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, No. 53 (1977), Springer-Verlag: Springer-Verlag Berlin/New York), 493-503 · Zbl 0366.68037
[34] Sudborough, I. H., The complexity of the membership problem for some extensions of context-free languages, Internat. J. Comput. Math. Sect. A, 6, 191-215 (1977) · Zbl 0398.68037
[35] Sudborough, I. H., On the tape complexity of deterministic context-free languages, J. Assoc. Comput. Mach., 25, 3, 405-414 (1978) · Zbl 0379.68054
[36] Sudborough, I. H., Relating open problems on the tape complexity of context-free languages and path system problems, (Proceedings, 12th Conference on Information Sciences and Systems (1978), Johns Hopkins Press: Johns Hopkins Press Baltimore), 329-335
[37] Harju, T., A simulation result for the auxiliary pushdown automata, J. Comput. System Sci., 19, 119-132 (1979) · Zbl 0427.68051
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.