{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T16:41:15Z","timestamp":1725468075596},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540638766"},{"type":"electronic","value":"9783540696599"}],"license":[{"start":{"date-parts":[[1997,1,1]],"date-time":"1997-01-01T00:00:00Z","timestamp":852076800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/bfb0058027","type":"book-chapter","created":{"date-parts":[[2006,8,3]],"date-time":"2006-08-03T06:48:04Z","timestamp":1154587684000},"page":"123-137","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["On the complexity of parallel implementation of logic programs"],"prefix":"10.1007","author":[{"given":"E.","family":"Pontelli","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D.","family":"Ranjan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"G.","family":"Gupta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"issue":"6","key":"10_CR1","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1007\/BF01397627","volume":"19","author":"K.A.M. Ali","year":"1991","unstructured":"K.A.M. Ali and R. Karlsson. Full Prolog and Scheduling Or-parallelism in Muse. International Journal of Parallel Programming, 1991. 19(6):445\u2013475.","journal-title":"International Journal of Parallel Programming"},{"key":"10_CR2","doi-asserted-by":"crossref","unstructured":"N. Blum. On the single-operation worst-case time complexity of the disjoint set union problem. SIAM Journal on Computing, 15(4), 1986.","DOI":"10.1137\/0215072"},{"key":"10_CR3","unstructured":"M. Carlsson,G. Gupta, K.M. Ali and M.V. Hermenegildo. Parallel execution of prolog programs: a survey. Journal of Logic Programming, 1998. to appear."},{"key":"10_CR4","doi-asserted-by":"crossref","unstructured":"M. Fredman, M. Saks. The Cell Probe Complexity of Dynamic Data Structures. In Procs. of 21st ACM Symposium on Theory of Computing. ACM, 1989.","DOI":"10.1145\/73007.73040"},{"key":"10_CR5","unstructured":"H.N. Gabow. Data structures for weighted matching and nearest common ancestor. In ACM Symp. on Discrete Algorithms, 1990."},{"issue":"1","key":"10_CR6","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/0743-1066(95)00092-5","volume":"27","author":"G. Gupta","year":"1996","unstructured":"G. Gupta and V. Santos Costa. Cuts and Side-effects in And\/Or Parallel Prolog. Journal of Logic Programming, 27(1):45\u201371, 1996.","journal-title":"Journal of Logic Programming"},{"issue":"4","key":"10_CR7","doi-asserted-by":"publisher","first-page":"659","DOI":"10.1145\/155183.155220","volume":"15","author":"G. Gupta","year":"1993","unstructured":"G. Gupta and B. Jayaraman. Analysis of or-parallel execution models. ACM TOPLAS, 15(4):659\u2013680, 1993.","journal-title":"ACM TOPLAS"},{"key":"10_CR8","doi-asserted-by":"crossref","unstructured":"D. Harel and R.E. Tarjan. Fast Algorithms for Finding Nearest Common Ancestor. SIAM Journal of Computing, 13(2), 1984.","DOI":"10.1137\/0213024"},{"key":"10_CR9","unstructured":"M. Hermenegildo and K. Greene. &-Prolog and its Performance. In Int'l Conf. on Logic Prog., MIT Press, 1990."},{"key":"10_CR10","doi-asserted-by":"crossref","unstructured":"J.C. Kergommeaux and P. Codognet. Parallel logic programming systems. ACM Computing Surveys, 26(3), 1994.","DOI":"10.1145\/185403.185453"},{"key":"10_CR11","unstructured":"D.E. Knuth. The Art of Computer Programming, volume 1. Addison-Wesley, 1968."},{"key":"10_CR12","doi-asserted-by":"crossref","unstructured":"J. W. Lloyd. Foundations of Logic Programming. Springer-Verlag, 1987.","DOI":"10.1007\/978-3-642-83189-8"},{"key":"10_CR13","doi-asserted-by":"crossref","unstructured":"E. Lusk and al. The Aurora Or-parallel Prolog System. New Generation Computing, 7(2,3), '90.","DOI":"10.1007\/BF03037208"},{"key":"10_CR14","unstructured":"E. Pontelli and G. Gupta. Implementation mechanisms for dependent andparallelism. In International Conference on Logic Programming. MIT Press, 1997."},{"key":"10_CR15","unstructured":"E. Pontelli, G. Gupta, and M. Hermenegildo. &ACE: A High-performance Parallel Prolog System. In IPPS 95. IEEE Computer Society, 1995."},{"key":"10_CR16","unstructured":"E. Pontelli, D. Ranjan, and G. Gupta. On the complexity of the Parallelism in Logic Programming. Technical report, New Mexico State University, 1997."},{"key":"10_CR17","unstructured":"E. Pontelli, D. Ranjan, and G. Gupta. On the complexity of the insertion\/precedes problem. Technical report, New Mexico State University, 1997."},{"key":"10_CR18","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1006\/jcss.1996.0008","volume":"52","author":"H. L. Poutr\u00e9","year":"1996","unstructured":"H. La Poutr\u00e9. Lower Bounds for the Union-Find and the Split-Find Problem on Pointer Machines. Journal of Computer and System Sciences, 52:87\u201399, 1996.","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"10_CR19","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1137\/0209036","volume":"9","author":"A. Sch\u00f6nhage","year":"1980","unstructured":"A. Sch\u00f6nhage. Storage Modification Machines. SIAM Journal of Computing, 9(3):490\u2013508, August 1980.","journal-title":"SIAM Journal of Computing"},{"key":"10_CR20","doi-asserted-by":"crossref","unstructured":"D.D. Sleator and R.E. Tarjan. A data structure for dynamic trees. Journal of Computer and System Sciences, 26, 1983.","DOI":"10.1016\/0022-0000(83)90006-5"},{"key":"10_CR21","doi-asserted-by":"crossref","unstructured":"R.E. Tarjan. A Class of Algorithms which Require Nonlinear Time to Mantain Disjoint Sets. Journal of Computer and System Sciences, 2(18), 1979.","DOI":"10.1016\/0022-0000(79)90042-4"},{"key":"10_CR22","doi-asserted-by":"crossref","unstructured":"R.E. Tarjan. Data Structures and Network Algorithms. CBMS-NSF, 1983. 23. A.K. Tsakalidis. The Nearest Common Ancestor in a Dynamic Tree. ACTA Informatica, 25, 1988.","DOI":"10.1007\/BF00268844"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0058027","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T15:47:49Z","timestamp":1578498469000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0058027"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540638766","9783540696599"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/bfb0058027","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]},"assertion":[{"value":"13 July 2006","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}