{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,30]],"date-time":"2025-06-30T12:09:45Z","timestamp":1751285385999},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2008,4,15]],"date-time":"2008-04-15T00:00:00Z","timestamp":1208217600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2009,5]]},"DOI":"10.1007\/s00224-008-9110-5","type":"journal-article","created":{"date-parts":[[2008,4,14]],"date-time":"2008-04-14T11:17:06Z","timestamp":1208171826000},"page":"590-619","source":"Crossref","is-referenced-by-count":6,"title":["Structural Recursion as a Query Language on Lists and\u00a0Ordered Trees"],"prefix":"10.1007","volume":"44","author":[{"given":"Edward L.","family":"Robertson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lawrence V.","family":"Saxton","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dirk","family":"Van Gucht","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stijn","family":"Vansummeren","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2008,4,15]]},"reference":[{"issue":"4","key":"9110_CR1","doi-asserted-by":"crossref","first-page":"727","DOI":"10.1007\/BF01354881","volume":"4","author":"S. Abiteboul","year":"1995","unstructured":"Abiteboul, S., Beeri, C.: The power of languages for the manipulation of complex values. VLDB\u00a0J. 4(4), 727\u2013794 (1995)","journal-title":"VLDB\u00a0J."},{"key":"9110_CR2","volume-title":"Foundations of Databases","author":"S. Abiteboul","year":"1995","unstructured":"Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley, Reading (1995)"},{"key":"9110_CR3","first-page":"283","volume-title":"STOC 1992","author":"S. Bellantoni","year":"1992","unstructured":"Bellantoni, S., Cook, S.: A new recursion-theoretic characterization of the polytime functions (extended abstract). In: STOC 1992, pp. 283\u2013293. ACM Press, New York (1992)"},{"key":"9110_CR4","unstructured":"Boag, S., Chamberlin, D., Fern\u00e1ndez, M.F., Florescu, D., Robie, J., Sim\u00e9on, J.: XQuery 1.0: An XML Query Language. W3C Recommendation, January 2007"},{"issue":"3","key":"9110_CR5","doi-asserted-by":"crossref","first-page":"234","DOI":"10.1006\/jcss.1998.1562","volume":"57","author":"A.J. Bonner","year":"1998","unstructured":"Bonner, A.J., Mecca, G.: Sequences, datalog, and transducers. J. Comput. Syst. Sci. 57(3), 234\u2013259 (1998)","journal-title":"J. Comput. Syst. Sci."},{"key":"9110_CR6","volume-title":"Computability and Logic","author":"G.S. Boolos","year":"1989","unstructured":"Boolos, G.S., Jeffrey, R.C.: Computability and Logic, 3rd edn. Cambridge University Press, Cambridge (1989)","edition":"3"},{"issue":"1","key":"9110_CR7","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1007\/s007780050084","volume":"9","author":"P. Buneman","year":"2000","unstructured":"Buneman, P., Fernandez, M.F., Suciu, D.: UnQL: a query language and algebra for semistructured data based on structural recursion. VLDB\u00a0J. 9(1), 76\u2013110 (2000)","journal-title":"VLDB\u00a0J."},{"issue":"1","key":"9110_CR8","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/0304-3975(95)00024-Q","volume":"149","author":"P. Buneman","year":"1995","unstructured":"Buneman, P., Naqvi, S.A., Tannen, V., Wong, L.: Principles of programming with complex objects and collection types. Theor. Comput. Sci. 149(1), 3\u201348 (1995)","journal-title":"Theor. Comput. Sci."},{"key":"9110_CR9","unstructured":"Caseiro, V.-H.: Equations for defining poly-time functions. PhD thesis, University of Oslo (1997)"},{"issue":"2","key":"9110_CR10","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1016\/0022-0000(80)90032-X","volume":"21","author":"A.K. Chandra","year":"1980","unstructured":"Chandra, A.K., Harel, D.: Computable queries for relational data bases. J. Comput. Syst. Sci. 21(2), 156\u2013178 (1980)","journal-title":"J. Comput. Syst. Sci."},{"key":"9110_CR11","first-page":"24","volume-title":"Logic, Methodology, and Philosophy of Science\u00a0II","author":"A. Cobham","year":"1965","unstructured":"Cobham, A.: The intrinsic computational difficulty of functions. In: Logic, Methodology, and Philosophy of Science\u00a0II, pp. 24\u201330. Springer, Berlin (1965)"},{"key":"9110_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1007\/3-540-62222-5_64","volume-title":"ICDT 1997","author":"L.S. Colby","year":"1997","unstructured":"Colby, L.S., Libkin, L.: Tractable iteration mechanisms for bag languages. In: ICDT 1997. Lecture Notes in Computer Science, vol. 1186, pp. 461\u2013475. Springer, Berlin (1997)"},{"key":"9110_CR13","first-page":"179","volume-title":"PODS 1994","author":"L.S. Colby","year":"1994","unstructured":"Colby, L.S., Robertson, E.L., Saxton, L.V., Van Gucht, D.: A query language for list-based complex objects. In: PODS 1994, pp. 179\u2013189. ACM Press, New York (1994)"},{"key":"9110_CR14","unstructured":"Draper, D., Fankhauser, P., Fern\u00e1ndez, M.F., Malhotra, A., Rose, K., Rys, M., Sim\u00e9on, J., Wadler, P.: XQuery 1.0 and XPath 2.0 Formal Semantics. W3C Recommendation, January 2007"},{"key":"9110_CR15","unstructured":"Fern\u00e1ndez, M.F., Malhotra, A., Marsh, J., Nagy, M., Walsh, N.: XQuery 1.0 and XPath 2.0 Data Model. W3C Recommendation, January 2007"},{"issue":"2","key":"9110_CR16","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1006\/inco.1998.2700","volume":"143","author":"J.-Y. Girard","year":"1998","unstructured":"Girard, J.-Y.: Light linear logic. Inf. Comput. 143(2), 175\u2013204 (1998)","journal-title":"Inf. Comput."},{"issue":"4","key":"9110_CR17","doi-asserted-by":"crossref","first-page":"653","DOI":"10.2307\/2272468","volume":"36","author":"M.D. Gladstone","year":"1971","unstructured":"Gladstone, M.D.: Simplifications of the recursion scheme. J.\u00a0Symb. Log. 36(4), 653\u2013665 (1971)","journal-title":"J.\u00a0Symb. Log."},{"key":"9110_CR18","unstructured":"Grumbach, S., Milo, T.: Personal communication"},{"issue":"2","key":"9110_CR19","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1006\/inco.1998.2777","volume":"150","author":"S. Grumbach","year":"1999","unstructured":"Grumbach, S., Milo, T.: An algebra for pomsets. Inf. Comput. 150(2), 268\u2013306 (1999)","journal-title":"Inf. Comput."},{"key":"9110_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1007\/BFb0028020","volume-title":"CSL 1997","author":"M. Hofmann","year":"1998","unstructured":"Hofmann, M.: A mixed modal\/linear lambda calculus with applications to Bellantoni-Cook safe recursion. In: CSL 1997. Lecture Notes in Computer Science, vol. 1414, pp. 275\u2013294. Springer, Berlin (1998)"},{"key":"9110_CR21","doi-asserted-by":"crossref","unstructured":"Hofmann, M.: Linear types and non-size-increasing polynomial time computation. In: LICS, pp.\u00a0464\u2013473 (1999)","DOI":"10.1109\/LICS.1999.782641"},{"issue":"3","key":"9110_CR22","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1017\/S0956796899003433","volume":"9","author":"M. Hofmann","year":"1999","unstructured":"Hofmann, M.: Semantics of linear\/modal lambda calculus. J.\u00a0Funct. Program. 9(3), 247\u2013277 (1999)","journal-title":"J.\u00a0Funct. Program."},{"key":"9110_CR23","doi-asserted-by":"crossref","unstructured":"Hofmann, M., Jost, S.: Static prediction of heap space usage for first-order functional programs. In: POPL, pp.\u00a0185\u2013197 (2003)","DOI":"10.1145\/604131.604148"},{"issue":"1","key":"9110_CR24","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/0022-0000(93)90022-O","volume":"47","author":"R. Hull","year":"1993","unstructured":"Hull, R., Su, J.: Algebraic and calculus query languages for recursively typed complex objects. J.\u00a0Comput. Syst. Sci. 47(1), 121\u2013156 (1993)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"issue":"1","key":"9110_CR25","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/0304-3975(94)00287-8","volume":"155","author":"N. Immerman","year":"1996","unstructured":"Immerman, N., Patnaik, S., Stemple, D.W.: The expressiveness of a family of finite set languages. Theor. Comput. Sci. 155(1), 111\u2013140 (1996)","journal-title":"Theor. Comput. Sci."},{"key":"9110_CR26","first-page":"325","volume-title":"POPL 1993","author":"D. Leivant","year":"1993","unstructured":"Leivant, D.: Stratified functional programs and computational complexity. In: POPL 1993, pp. 325\u2013333. ACM Press, New York (1993)"},{"issue":"2","key":"9110_CR27","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1006\/jcss.1997.1523","volume":"55","author":"L. Libkin","year":"1997","unstructured":"Libkin, L., Wong, L.: Query languages for bags and aggregate functions. J. Comput. Syst. Sci. 55(2), 241\u2013272 (1997)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"9110_CR28","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/0304-3975(93)90345-T","volume":"119","author":"V.Yu. Sazonov","year":"1993","unstructured":"Sazonov, V.Yu.: Hereditarily-finite sets, data bases and polynomial-time computability. Theor. Comput. Sci. 119(1), 187\u2013214 (1993)","journal-title":"Theor. Comput. Sci."},{"issue":"1\u20132","key":"9110_CR29","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1016\/S0304-3975(96)00293-9","volume":"176","author":"D. Suciu","year":"1997","unstructured":"Suciu, D.: Bounded fixpoints for complex objects. Theor. Comput. Sci. 176(1\u20132), 283\u2013328 (1997)","journal-title":"Theor. Comput. Sci."},{"key":"9110_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/3-540-58907-4_10","volume-title":"ICDT 1995","author":"D. Suciu","year":"1995","unstructured":"Suciu, D., Wong, L.: On two forms of structural recursion. In: ICDT 1995. Lecture Notes in Computer Science, vol. 893, pp. 111\u2013124. Springer, Berlin (1995)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-008-9110-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-008-9110-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-008-9110-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T07:51:35Z","timestamp":1558684295000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-008-9110-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,4,15]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2009,5]]}},"alternative-id":["9110"],"URL":"https:\/\/doi.org\/10.1007\/s00224-008-9110-5","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,4,15]]}}}