{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,11]],"date-time":"2026-11-11T07:11:11Z","timestamp":1794381071903,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540228493","type":"print"},{"value":"9783540278368","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27836-8_94","type":"book-chapter","created":{"date-parts":[[2010,9,15]],"date-time":"2010-09-15T18:53:21Z","timestamp":1284576801000},"page":"1136-1149","source":"Crossref","is-referenced-by-count":50,"title":["Counting in Trees for Free"],"prefix":"10.1007","author":[{"given":"Helmut","family":"Seidl","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"Schwentick","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anca","family":"Muscholl","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peter","family":"Habermehl","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"94_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-45309-1_1","volume-title":"Programming Languages and Systems","author":"L. Cardelli","year":"2001","unstructured":"Cardelli, L., Ghelli, G.: A Query Language Based on the Ambient Logic. In: Sands, D. (ed.) ESOP 2001. LNCS, vol.\u00a02028, pp. 1\u201322. Springer, Heidelberg (2001)"},{"key":"94_CR2","doi-asserted-by":"crossref","unstructured":"Cardelli, L., Gordon, A.: Anytime, Anywhere: Modal Logics for Mobile Ambients. In: 27th ACM Conf. on Principles of Programming Languages (POPL), pp. 365\u2013377 (2000)","DOI":"10.1145\/325694.325742"},{"key":"94_CR3","doi-asserted-by":"crossref","unstructured":"Conforti, G., Ferrara, O., Ghelli, G.: TQL Algebra and its Implementation (Extended Abstract). In: IFIP Int. Conf. on Theoretical Computer Science (IFIP TCS), pp. 422\u2013434 (2002)","DOI":"10.1007\/978-0-387-35608-2_35"},{"key":"94_CR4","unstructured":"Conforti, G., Ghelli, G., Albano, A., Colazzo, D., Manghi, P., Sartiani, C.: The Query Language TQL. In: 5th Int. Workshop on the Web and Databases, WebDB (2002)"},{"key":"94_CR5","doi-asserted-by":"crossref","unstructured":"Dal-Zilio, S., Lugiez, D., Meyssonnier, C.: A Logic you can Count on. In: 31st ACM Symp. on Principles of Programming Languages (POPL), pp. 135\u2013146 (2004)","DOI":"10.1145\/964001.964013"},{"key":"94_CR6","unstructured":"Fischer, M.J., Rabin, M.O.: Superexponential Complexity of Presburger Arithmetic. In: AMS Symp. on the Complexity of Computational Computational Processes, vol.\u00a07, pp. 27\u201341 (1974)"},{"issue":"2","key":"94_CR7","doi-asserted-by":"crossref","first-page":"285","DOI":"10.2140\/pjm.1966.16.285","volume":"16","author":"S. Ginsburg","year":"1966","unstructured":"Ginsburg, S., Spanier, E.H.: Semigroups, Presburger Formulas and Languages. Pacific Journal of Mathematics\u00a016(2), 285\u2013296 (1966)","journal-title":"Pacific Journal of Mathematics"},{"key":"94_CR8","doi-asserted-by":"crossref","unstructured":"Gottlob, G., Koch, C.: Monadic Datalog and the Expressive Power of Languages forWeb Information Extraction. In: PODS, pp. 17\u201328 (2001)","DOI":"10.1145\/543613.543617"},{"key":"94_CR9","doi-asserted-by":"crossref","unstructured":"Klaedtke, F., Ruess, H.: Parikh Automata and Monadic Second-Order Logics with Linear Cardinality Constraints. Technical Report 177, Institute of CS at Freiburg University (2002)","DOI":"10.1007\/3-540-45061-0_54"},{"key":"94_CR10","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1007\/3-540-45620-1_34","volume-title":"Automated Deduction - CADE-18","author":"O. Kupferman","year":"2002","unstructured":"Kupferman, O., Sattler, U., Vardi, M.Y.: The Complexity of the Graded \u03bc-Calculus. In: Voronkov, A. (ed.) CADE 2002. LNCS (LNAI), vol.\u00a02392, pp. 423\u2013437. Springer, Heidelberg (2002)"},{"key":"94_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1007\/3-540-44881-0_18","volume-title":"Rewriting Techniques and Applications","author":"D. Lugiez","year":"2003","unstructured":"Lugiez, D., Dal Zilio, S.: XML Schema, Tree Logic and Sheaves Automata. In: Nieuwenhuis, R. (ed.) RTA 2003. LNCS, vol.\u00a02706, pp. 246\u2013263. Springer, Heidelberg (2003)"},{"key":"94_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1007\/3-540-36285-1_5","volume-title":"Database Theory - ICDT 2003","author":"W. Martens","year":"2002","unstructured":"Martens, W., Neven, F.: Typechecking Top-down Uniform Unranked Tree Transducers. In: Calvanese, D., Lenzerini, M., Motwani, R. (eds.) ICDT 2003. LNCS, vol.\u00a02572, pp. 64\u201378. Springer, Heidelberg (2002)"},{"key":"94_CR13","doi-asserted-by":"crossref","unstructured":"Neumann, A., Seidl, H.: Locating Matches of Tree Patterns in Forests. TR 98-08, Trier (1998)","DOI":"10.1007\/978-3-540-49382-2_12"},{"key":"94_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/3-540-45793-3_2","volume-title":"Computer Science Logic","author":"F. Neven","year":"2002","unstructured":"Neven, F.: Automata, Logic, and XML. In: Bradfield, J.C. (ed.) CSL 2002 and EACSL 2002. LNCS, vol.\u00a02471, pp. 2\u201326. Springer, Heidelberg (2002)"},{"issue":"1-2","key":"94_CR15","doi-asserted-by":"publisher","first-page":"633","DOI":"10.1016\/S0304-3975(01)00301-2","volume":"275","author":"F. Neven","year":"2002","unstructured":"Neven, F., Schwentick, T.: Query Automata over Finite Trees. TCS\u00a0275(1-2), 633\u2013674 (2002)","journal-title":"TCS"},{"issue":"1","key":"94_CR16","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1145\/505241.505245","volume":"49","author":"F. Neven","year":"2002","unstructured":"Neven, F., Van den Bussche, J.: Expressiveness of Structured Document Query Languages Based on Attribute Grammars. Journal of the ACM\u00a049(1), 56\u2013100 (2002)","journal-title":"Journal of the ACM"},{"key":"94_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"356","DOI":"10.1007\/3-540-56610-4_76","volume-title":"TAPSOFT \u201993: Theory and Practice of Software Development","author":"J. Niehren","year":"1993","unstructured":"Niehren, J., Podelski, A.: Feature Automata and Recognizable Sets of Feature Trees. In: Gaudel, M.-C., Jouannaud, J.-P. (eds.) CAAP 1993, FASE 1993, and TAPSOFT 1993. LNCS, vol.\u00a0668, pp. 356\u2013375. Springer, Heidelberg (1993)"},{"issue":"4","key":"94_CR18","doi-asserted-by":"publisher","first-page":"765","DOI":"10.1145\/322276.322287","volume":"28","author":"C.H. Papadimitriou","year":"1981","unstructured":"Papadimitriou, C.H.: On the Complexity of Integer Programming. J. ACM\u00a028(4), 765\u2013768 (1981)","journal-title":"J. ACM"},{"issue":"4","key":"94_CR19","doi-asserted-by":"publisher","first-page":"570","DOI":"10.1145\/321356.321364","volume":"13","author":"R.J. Parikh","year":"1966","unstructured":"Parikh, R.J.: On Context-free Languages. J. of the ACM\u00a013(4), 570\u2013581 (1966)","journal-title":"J. of the ACM"},{"key":"94_CR20","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1080\/014453409108837187","volume":"12","author":"M. Presburger","year":"1991","unstructured":"Presburger, M.: On the Completeness of a Certain System of Arithmetic of Whole Numbers in which Addition Occurs as the only Operation. Hist. Philos. Logic\u00a012, 225\u2013233 (1991); English translation of the original paper from 1929.","journal-title":"Hist. Philos. Logic"},{"key":"94_CR21","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/0020-0190(94)00130-8","volume":"54","author":"H. Seidl","year":"1994","unstructured":"Seidl, H.: Haskell Overloading is DEXPTIME Complete. Inf. Proc. Lett (IPL)\u00a054, 57\u201360 (1994)","journal-title":"Inf. Proc. Lett. (IPL)"},{"key":"94_CR22","doi-asserted-by":"crossref","unstructured":"Seidl, H., Schwentick, T., Muscholl, A.: Numerical Document Queries. In: PODS, pp. 155\u2013166 (2003)","DOI":"10.1145\/773153.773169"},{"key":"94_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1007\/3-540-48168-0_34","volume-title":"Computer Science Logic","author":"H. Seidl","year":"1999","unstructured":"Seidl, H., Neumann, A.: On Guarding Nested Fixpoints. In: Flum, J., Rodr\u00edguez-Artalejo, M. (eds.) CSL 1999. LNCS, vol.\u00a01683, pp. 484\u2013498. Springer, Heidelberg (1999)"},{"key":"94_CR24","doi-asserted-by":"crossref","unstructured":"Stockmeyer, L.J., Meyer, A.R.: Word problems requiring exponential time: Preliminary report. In: STOC, pp. 1\u20139 (1973)","DOI":"10.1145\/800125.804029"},{"issue":"2","key":"94_CR25","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1006\/inco.2000.2894","volume":"164","author":"I. Walukiewicz","year":"2001","unstructured":"Walukiewicz, I.: Pushdown Processes: Games and Model-Checking. Information and Computation\u00a0164(2), 234\u2013263 (2001)","journal-title":"Information and Computation"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27836-8_94.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,18]],"date-time":"2020-11-18T23:24:09Z","timestamp":1605741849000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27836-8_94"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540228493","9783540278368"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27836-8_94","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/b99859","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004]]}}}