{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:13:29Z","timestamp":1725664409157},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540601784"},{"type":"electronic","value":"9783540447207"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60178-3_100","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:49:29Z","timestamp":1330278569000},"page":"503-514","source":"Crossref","is-referenced-by-count":0,"title":["A query language for NC (extended abstract)"],"prefix":"10.1007","author":[{"given":"Dan","family":"Suciu","sequence":"first","affiliation":[]},{"given":"Val","family":"Breazu-Tannen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"25_CR1","doi-asserted-by":"crossref","unstructured":"S. Abiteboul, M. Vardi, and V. Vianu. Fixpoint logics, relational machines, and computational complexity. In Structure and Complexity, 1992.","DOI":"10.1109\/SCT.1992.215391"},{"key":"25_CR2","unstructured":"Serge Abiteboul and Catriel Beeri. On the power of languages for the manipulation of complex objects. In Proceedings of International Workshop on Theory and Applications of Nested Relations and Complex Objects, Darmstadt, 1988. Also available as INRIA Technical Report 846."},{"key":"25_CR3","doi-asserted-by":"crossref","unstructured":"Serge Abiteboul and Victor Vianu. Generic computation and its complexity. In Proceedings of 23rd ACM Symposium on the Theory of Computing, 1991.","DOI":"10.1145\/103418.103444"},{"key":"25_CR4","unstructured":"F. Bancilhon, T. Briggs, S. Khoshafian, and P. Valduriez. A powerful and simple database language. In Proceedings of 14th International Conference on Very Large Data Bases, pages 97\u2013105, 1988."},{"key":"25_CR5","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1016\/0022-0000(90)90022-D","volume":"41","author":"D. M. Barrington","year":"1990","unstructured":"David Mix Barrington, Neil Immerman, and Howard Straubing. On uniformity within NC 1. Journal of Computer and System Sciences, 41:274\u2013306, 1990.","journal-title":"Journal of Computer and System Sciences"},{"key":"25_CR6","unstructured":"V. Breazu-Tannen, P. Buneman, and S. Naqvi. Structural recursion as a query language. In Proceedings of 3rd International Workshop on Database Programming Languages, Naphlion, Greece, pages 9\u201319. Morgan Kaufmann, August 1991. Also available as UPenn Technical Report MS-CIS-92-17."},{"key":"25_CR7","first-page":"60","volume-title":"Logical and computational aspects of programming with Sets\/Bags\/Lists","author":"V. Breazu-Tannen","year":"1991","unstructured":"V. Breazu-Tannen and R. Subrahmanyam. Logical and computational aspects of programming with Sets\/Bags\/Lists. In LNCS 510: Proceedings of 18th International Colloquium on Automata, Languages, and Programming, Madrid, Spain, July 1991, pages 60\u201375. Springer Verlag, 1991."},{"key":"25_CR8","first-page":"140","volume-title":"Naturally embedded query languages","author":"V. Breazu-Tannen","year":"1992","unstructured":"Val Breazu-Tannen, Peter Buneman, and Limsoon Wong. Naturally embedded query languages. In J. Biskup and R. Hull, editors, LNCS 646: Proceedings of 4th International Conference on Database Theory, Berlin, Germany, October, 1992, pages 140\u2013154. Springer-Verlag, October 1992. Available as UPenn Technical Report MS-CIS-92-47."},{"issue":"4","key":"25_CR9","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/BF01305232","volume":"12","author":"J. Cai","year":"1992","unstructured":"Jin-Yi Cai, Martin Furer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4):389\u2013410, 1992.","journal-title":"Combinatorica"},{"issue":"2","key":"25_CR10","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1016\/0022-0000(80)90032-X","volume":"21","author":"A. Chandra","year":"1980","unstructured":"Ashok Chandra and David Harel. Computable queries for relational databases. Journal of Computer and System Sciences, 21(2):156\u2013178, 1980.","journal-title":"Journal of Computer and System Sciences"},{"key":"25_CR11","volume-title":"Feasible Mathematics","author":"P. Clote","year":"1990","unstructured":"P. Clote. Sequential, machine-independent characterizations of the parallel complexity classes AlogTime, AC k, NCk, and NC. In Samuel R. Buss and Philip J. Scot, editors, Feasible Mathematics. Birkh\u00e4user, Boston, 1990."},{"issue":"1\/2","key":"25_CR12","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1016\/0890-5401(90)90063-N","volume":"87","author":"K. L. Compton","year":"1990","unstructured":"Kevin L. Compton and Claude Laftamme. An algebra and a logic for NC. Information and Computation, 87(1\/2):240\u2013262, 1990.","journal-title":"Information and Computation"},{"key":"25_CR13","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/S0019-9958(85)80041-3","volume":"64","author":"S. Cook","year":"1985","unstructured":"S. Cook. A taxonomy of problems with fast parallel algorithms. Information and Control, 64:2\u201322, 1985.","journal-title":"Information and Control"},{"key":"25_CR14","unstructured":"Anuj Dawar, Steven Lindell, and Scott Weinstein. Infinitary logic and inductive definability over finite structures. Information and Computation, 1993. To appear. Available as UPenn Technical Report MS-CIS-91-97."},{"key":"25_CR15","first-page":"191","volume-title":"Expressiveness and complexity of restricted languages for complex objects","author":"S. Grumbach","year":"1991","unstructured":"Stephane Grumbach and Victor Vianu. Expressiveness and complexity of restricted languages for complex objects. In Proceedings of 3rd International Workshop on Database Programming Languages, Naphlion, Greece, pages 191\u2013202. Morgan Kaufmann, August 1991."},{"key":"25_CR16","series-title":"Extended abstract appeared in PODS 91","volume-title":"Technical Report 1573","author":"S. Grumbach","year":"1991","unstructured":"Stephane Grumbach and Victor Vianu. Tractable query languages for complex object databases. Technical Report 1573, INRIA, Rocquencourt BP 105, 78153 Le Chesnay, France, December 1991. Extended abstract appeared in PODS 91."},{"key":"25_CR17","doi-asserted-by":"crossref","unstructured":"Y. Gurevich. Algebra of feasible functions. In Proceedings of 24th IEEE Symposium on Foundations of Computer Science, pages 210\u2013214. IEEE Computer Society Press, 1983.","DOI":"10.1109\/SFCS.1983.5"},{"key":"25_CR18","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/S0019-9958(86)80029-8","volume":"68","author":"N. Immerman","year":"1986","unstructured":"Neil Immerman. Relational queries computable in polynomial time. Information and Control, 68:86\u2013104, 1986.","journal-title":"Information and Control"},{"key":"25_CR19","doi-asserted-by":"crossref","unstructured":"Neil Immerman. Expressibility as a complexity measure: Results and directions. In Proceedings of 2nd Conference on Structure in Complexity Theory, pages 194\u2013202, 1987.","DOI":"10.1109\/PSCT.1987.10319271"},{"key":"25_CR20","doi-asserted-by":"publisher","first-page":"760","DOI":"10.1137\/0216051","volume":"16","author":"N. Immerman","year":"1987","unstructured":"Neil Immerman. Languages that capture complexity classes. SIAM Journal of Computing, 16:760\u2013778, 1987.","journal-title":"SIAM Journal of Computing"},{"key":"25_CR21","doi-asserted-by":"crossref","first-page":"625","DOI":"10.1137\/0218043","volume":"18","author":"N. Immerman","year":"1989","unstructured":"Neil Immerman. Expressibility and parallel complexity. SIAM Journal of Computing, 18:625\u2013638, 1989.","journal-title":"SIAM Journal of Computing"},{"key":"25_CR22","doi-asserted-by":"crossref","unstructured":"Neil Immerman, Sushant Patnaik, and David Stemple. The expressiveness of a family of finite set languages. In Proceedings of 10th ACM Symposium on Principles of Database Systems, pages 37\u201352, 1991.","DOI":"10.1145\/113413.113417"},{"key":"25_CR23","unstructured":"Y. N. Moschovakis. Elementary Induction on Abstract Structures. North Holland, 1974."},{"key":"25_CR24","doi-asserted-by":"crossref","unstructured":"A. Ohori, P. Buneman, and V. Breazu-Tannen. Database programming in Machiavelli, a polymorphic language with static type inference. In James Clifford, Bruce Lindsay, and David Maier, editors, Proceedings of ACM-SIGMOD International Conference on Management of Data, pages 46\u201357, Portland, Oregon, June 1989.","DOI":"10.1145\/67544.66931"},{"key":"25_CR25","doi-asserted-by":"crossref","unstructured":"Jan Paredaens and Dirk Van Gucht. Possibilities and limitations of using flat operators in nested algebra expressions. In Proceedings of 7th ACM Symposium on Principles of Database Systems,Austin, Texas, pages 29\u201338, 1988.","DOI":"10.1145\/308386.308402"},{"issue":"1","key":"25_CR26","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1145\/128765.128768","volume":"17","author":"J. Paredaens","year":"1992","unstructured":"Jan Paredaens and Dirk Van Gucht. Converting nested relational algebra expressions into flat algebra expressions. ACM Transaction on Database Systems, 17(1):65\u201393, March 1992.","journal-title":"ACM Transaction on Database Systems"},{"key":"25_CR27","first-page":"115","volume-title":"SVP: A model capturing sets, streams, and parallelism","author":"D. S. Parker","year":"1992","unstructured":"D. Stott Parker, Eric Simon, and Patrick Valduriez. SVP: A model capturing sets, streams, and parallelism. In Li-Yan Yuan, editor, Proceedings of 18th International Conference on Very Large Databases, Vancouver, August 1992, pages 115\u2013126, San Mateo, California, August 1992. Morgan-Kaufmann."},{"issue":"2","key":"25_CR28","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/0306-4379(86)90003-7","volume":"11","author":"H.-J. Schek","year":"1986","unstructured":"H.-J. Schek and M. H. Scholl. The relational model with relation-valued attributes. Information Systems, 11(2):137\u2013147, 1986.","journal-title":"Information Systems"},{"key":"25_CR29","doi-asserted-by":"crossref","unstructured":"Dan Suciu. Fixpoints and bounded fixpoints for complex objects. In Catriel Beeri, Atsushi Ohori, and Dennis Shasha, editors, Proceedings of 4th International Workshop on Database Programming Languages, New York, August 1993, pages 263\u2013281. Springer-Verlag, January 1994. See also UPenn Technical Report MS-CIS-93-32.","DOI":"10.1007\/978-1-4471-3564-7_15"},{"key":"25_CR30","doi-asserted-by":"crossref","unstructured":"Dan Suciu and Val Breazu-Tannen. A query language for NC. In Proceedings of 13th ACM Symposium on Principles of Database Systems, pages 167\u2013178, Minneapolis, Minnesota, May 1994. See also UPenn Technical Report MS-CIS-94-05.","DOI":"10.1145\/182591.182610"},{"key":"25_CR31","first-page":"269","volume-title":"Advances in Computing Research: The Theory of Databases","author":"S. J. Thomas","year":"1986","unstructured":"S. J. Thomas and P. C. Fischer. Nested relational structures. In P. C. Kanellakis and F. P. Preparata, editors, Advances in Computing Research: The Theory of Databases, pages 269\u2013307, London, England, 1986. JAI Press."},{"key":"25_CR32","doi-asserted-by":"crossref","unstructured":"M. Y. Vardi. The complexity of relational query languages. In Proceedings of 14th ACM SIGACT Symposium on the Theory of Computing, pages 137\u2013146, San Francisco, California, 1982.","DOI":"10.1145\/800070.802186"},{"key":"25_CR33","doi-asserted-by":"crossref","unstructured":"Limsoon Wong. Normal forms and conservative properties for query languages over collection types. In Proceedings of 12th ACM Symposium on Principles of Database Systems, pages 26\u201336, Washington, D. C., May 1993. See also UPenn Technical Report MS-CIS-92-59.","DOI":"10.1145\/153850.153853"}],"container-title":["Lecture Notes in Computer Science","Logic and Computational Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60178-3_100.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,20]],"date-time":"2024-04-20T16:44:20Z","timestamp":1713631460000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60178-3_100"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540601784","9783540447207"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/3-540-60178-3_100","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}