{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T18:27:34Z","timestamp":1764872854642,"version":"3.32.0"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"1-4","license":[{"start":{"date-parts":[[1988,11,1]],"date-time":"1988-11-01T00:00:00Z","timestamp":594345600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1988,11]]},"DOI":"10.1007\/bf01762108","type":"journal-article","created":{"date-parts":[[2005,6,16]],"date-time":"2005-06-16T10:22:38Z","timestamp":1118917358000},"page":"5-42","source":"Crossref","is-referenced-by-count":88,"title":["Parallel complexity of logical query programs"],"prefix":"10.1007","volume":"3","author":[{"given":"Jeffrey D.","family":"Ullman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Allen","family":"Van Gelder","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"doi-asserted-by":"crossref","unstructured":"F. Afrati and C. H. Papadimitriou. The parallel complexity of simple chain queries. In6th ACM Symposium on Principles of Database Systems, pp. 210\u2013213, 1987.","key":"BF01762108_CR1","DOI":"10.1145\/28659.28682"},{"doi-asserted-by":"crossref","unstructured":"A. V. Aho and J. D. Ullman. Universality of data retrieval languages. In6th ACM Symposium on Principles of Programming Languages, pp. 110\u2013120, 1979.","key":"BF01762108_CR2","DOI":"10.1145\/567752.567763"},{"issue":"3","key":"BF01762108_CR3","doi-asserted-by":"crossref","first-page":"841","DOI":"10.1145\/322326.322339","volume":"29","author":"K. R. Apt","year":"1982","unstructured":"K. R. Apt and M. H. Van Emden. Contributions to the theory of logic programming.J. Assoc. Comput. Math.,29(3):841\u2013862, 1982.","journal-title":"J. Assoc. Comput. Math."},{"doi-asserted-by":"crossref","unstructured":"M. J. Atallah and S. E. Hambrusch. Solving tree problems on a mesh-connected processor array. In26th FOCS, pp. 222\u2013231, 1985.","key":"BF01762108_CR4","DOI":"10.1109\/SFCS.1985.53"},{"issue":"1","key":"BF01762108_CR5","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0022-0000(82)90012-5","volume":"25","author":"A. Chandra","year":"1982","unstructured":"A. Chandra and D. Harel. Structure and complexity of relational queries.J. Comput. System Sci.,25(1):99\u2013128, 1982.","journal-title":"J. Comput. System Sci."},{"issue":"3","key":"BF01762108_CR6","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1016\/S0022-0000(74)80046-2","volume":"9","author":"S. A. Cook","year":"1974","unstructured":"S. A. Cook. An observation on time-storage trade-off.J. Comput. System Sci.,9(3):308\u2013316, 1974.","journal-title":"J. Comput. System Sci."},{"issue":"1","key":"BF01762108_CR7","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/S0019-9958(85)80041-3","volume":"64","author":"S. A. Cook","year":"1985","unstructured":"S. A. Cook. A taxonomy of problems with fast parallel algorithms.Inform. and Control,64(1):2\u201322, 1985.","journal-title":"Inform. and Control"},{"doi-asserted-by":"crossref","unstructured":"S. S. Cosmadakis and P. C. Kanellakis. Parallel evaluation of recursive rule queries. In5th ACM Symposium on Principles of Database Systems, pp. 280\u2013293, 1986.","key":"BF01762108_CR8","DOI":"10.1145\/6012.15421"},{"issue":"3","key":"BF01762108_CR9","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1137\/0304034","volume":"4","author":"S. Ginsburg","year":"1966","unstructured":"S. Ginsburg and E. H. Spanier. Finite turn pushdown automata.SIAM J. Control,4(3):429\u2013453, 1966.","journal-title":"SIAM J. Control"},{"issue":"1","key":"BF01762108_CR10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01691341","volume":"2","author":"S. A. Greibach","year":"1968","unstructured":"S. A. Greibach. A note on undecidable properties of formal languages.Math Systems Theory,2(1):1\u20136, 1968.","journal-title":"Math Systems Theory"},{"issue":"4","key":"BF01762108_CR11","doi-asserted-by":"crossref","first-page":"304","DOI":"10.1137\/0202025","volume":"2","author":"S. A. Greibach","year":"1973","unstructured":"S. A. Greibach. The hardest context-free language.SIAM J. Comput.,2(4):304\u2013310, 1973.","journal-title":"SIAM J. Comput."},{"key":"BF01762108_CR12","volume-title":"Introduction to Automata Theory, Languages, and Computation.","author":"J. E. Hopcroft","year":"1979","unstructured":"J. E. Hopcroft and J. D. Ullman.Introduction to Automata Theory, Languages, and Computation. Addision-Wesley, Reading, MA, 1979."},{"issue":"1","key":"BF01762108_CR13","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0304-3975(76)90068-2","volume":"3","author":"N. D. Jones","year":"1976","unstructured":"N. D. Jones and W. T. Laaser. Complete problems for deterministic polynomial time.Theor. Comput. Sci. 3(1):105\u2013117, 1976.","journal-title":"Theor. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"G. L. Miller and J. H. Reif. Parallel tree contraction and its applications. In26th FOCS, pp. 478\u2013489, 1985.","key":"BF01762108_CR14","DOI":"10.1109\/SFCS.1985.43"},{"key":"BF01762108_CR15","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1007\/3-540-16766-8_21","volume-title":"VLSI Algorithms and Architectures","author":"G. L. Miller","year":"1986","unstructured":"G. L. Miller, V. Ramachandran, and E. Kaltofen. Efficient parallel evaluation of straight-line code and arithmetic circuits. InVLSI Algorithms and Architectures, pp. 236\u2013245, Springer-Verlag, New York, 1986."},{"issue":"2","key":"BF01762108_CR16","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1016\/0022-0000(80)90036-7","volume":"21","author":"W. L. Ruzzo","year":"1980","unstructured":"W. L. Ruzzo. Tree-size bounded alternation.J. Comput. System Sci.,21(2):218\u2013235, 1980.","journal-title":"J. Comput. System Sci."},{"issue":"1","key":"BF01762108_CR17","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/0743-1066(84)90021-9","volume":"1","author":"E. Shapiro","year":"1984","unstructured":"E. Shapiro. Alternation and the computational complexity of logic programs.J. Logic Programming. 1(1):19\u201323, 1984.","journal-title":"J. Logic Programming."},{"issue":"2","key":"BF01762108_CR18","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1137\/0213027","volume":"13","author":"L. Stockmeyer","year":"1984","unstructured":"L. Stockmeyer and U. Vishkin. Simulation of parallel random access machines by circuits.SIAM J. Comput.,13(2):409\u2013422, 1984.","journal-title":"SIAM J. Comput."},{"key":"BF01762108_CR19","series-title":"Technical Report STAN-CS-85-1089","volume-title":"Parallel Complexity of Logical Query Programs","author":"J. D. Ullman","year":"1985","unstructured":"J. D. Ullman and A. Van Gelder. Parallel Complexity of Logical Query Programs. Technical Report STAN-CS-85-1089, Dept. of Computer Science, Stanford University, Stanford, CA, 1985 (short version presented at27th FOCS, 1986)."},{"issue":"4","key":"BF01762108_CR20","doi-asserted-by":"crossref","first-page":"641","DOI":"10.1137\/0212043","volume":"12","author":"L. G. Valiant","year":"1983","unstructured":"L. G. Valiant, S. Skyum, S. Berkowitz, and C. Rackoff. Fast parallel computation on polynomials using few processors.SIAM J. Comput.,12(4):641\u2013644, 1983.","journal-title":"SIAM J. Comput."},{"issue":"4","key":"BF01762108_CR21","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1145\/321978.321991","volume":"23","author":"M. H. Emden Van","year":"1976","unstructured":"M. H. Van Emden and R. A. Kowalski. The semantics of predicate logic as a programming language.J. Assoc. Comput. Math.,23(4):733\u2013742, 1976.","journal-title":"J. Assoc. Comput. Math."},{"unstructured":"A. Van Gelder. Negation as failure using tight derivations for general logic programs. InProc. Third IEEE Symposium on Logic Programming, 1986 (preliminary version also presented in Workshop on Foundations of Deductive Databases and Logic Programming, Washington, DC, 1986).","key":"BF01762108_CR22"},{"doi-asserted-by":"crossref","unstructured":"M. Vardi. Complexity of relational queries. In14th ACM Symposium on Theory of Computing, pp. 137\u2013145, 1982.","key":"BF01762108_CR23","DOI":"10.1145\/800070.802186"},{"doi-asserted-by":"crossref","unstructured":"M. Y. Vardi. Querying logical databases. In4th PODS, pp. 57\u201365, 1985.","key":"BF01762108_CR24","DOI":"10.1145\/325405.325413"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01762108.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01762108\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01762108","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T19:04:56Z","timestamp":1735758296000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01762108"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988,11]]},"references-count":24,"journal-issue":{"issue":"1-4","published-print":{"date-parts":[[1988,11]]}},"alternative-id":["BF01762108"],"URL":"https:\/\/doi.org\/10.1007\/bf01762108","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[1988,11]]}}}