{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T08:38:52Z","timestamp":1725525532966},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540926863"},{"type":"electronic","value":"9783540926870"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-92687-0_13","type":"book-chapter","created":{"date-parts":[[2009,2,10]],"date-time":"2009-02-10T04:25:38Z","timestamp":1234239938000},"page":"180-196","source":"Crossref","is-referenced-by-count":4,"title":["Complete Axiomatizations of MSO, FO(TC 1 ) and FO(LFP 1 ) on Finite Trees"],"prefix":"10.1007","author":[{"given":"Am\u00e9lie","family":"Gheerbrant","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Balder","family":"ten Cate","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"13_CR1","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/BF01048403","volume":"4","author":"R. Backofen","year":"1995","unstructured":"Backofen, R., Rogers, J., Vijay-Shankar, K.: A first-order axiomatization of the theory of finite trees. Journal of Logic, Language and Information\u00a04(4), 5\u201339 (1995)","journal-title":"Journal of Logic, Language and Information"},{"key":"13_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1007\/3-540-56992-8_8","volume-title":"Computer Science Logic","author":"U. Bosse","year":"1993","unstructured":"Bosse, U.: An Ehrenfeucht-Fra\u00efss\u00e9 game for fixpoint logic and stratified fixpoint logic. In: Martini, S., B\u00f6rger, E., Kleine B\u00fcning, H., J\u00e4ger, G., Richter, M.M. (eds.) CSL 1992. LNCS, vol.\u00a0702, pp. 100\u2013114. Springer, Heidelberg (1993)"},{"key":"13_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/BFb0023863","volume-title":"Logical Foundations of Computer Science - Tver \u201992","author":"A. Calo","year":"1992","unstructured":"Calo, A., Makowsky, J.A.: The Ehrenfeucht-Fra\u00efss\u00e9 games for transitive closure. In: Nerode, A., Taitslin, M.A. (eds.) LFCS 1992. LNCS, vol.\u00a0620, pp. 57\u201368. Springer, Heidelberg (1992)"},{"key":"13_CR4","unstructured":"Doets, K.: Completeness and Definability: Applications of the Ehrenfeucht Game in Second-Order and Intensional Logic. PhD thesis, Universiteit van Amsterdam (1987)"},{"key":"13_CR5","series-title":"Perspectives in Mathematical Logic","volume-title":"Finite Model Theory","author":"H.-D. Ebbinghaus","year":"1995","unstructured":"Ebbinghaus, H.-D., Flum, J.: Finite Model Theory. Perspectives in Mathematical Logic. Springer, Berlin (1995)"},{"key":"13_CR6","volume-title":"A mathematical introduction to Logic","author":"H. Enderton","year":"1972","unstructured":"Enderton, H.: A mathematical introduction to Logic. Academic Press, New York (1972)"},{"key":"13_CR7","doi-asserted-by":"crossref","first-page":"57","DOI":"10.4064\/fm-47-1-57-103","volume":"47","author":"S. Feferman","year":"1959","unstructured":"Feferman, S., Vaught, R.: The first-order properties of algebraic systems. Fundamenta Mathematicae\u00a047, 57\u2013103 (1959)","journal-title":"Fundamenta Mathematicae"},{"key":"13_CR8","doi-asserted-by":"crossref","unstructured":"Gottlob, G., Koch, C.: Monadic datalog and the expressive power of languages for web information extraction. In: Proceedings of PODS 2002, pp. 17\u201328 (2002)","DOI":"10.1145\/543613.543617"},{"key":"13_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/BFb0023764","volume-title":"Computer Science Logic","author":"E. Gr\u00e4del","year":"1992","unstructured":"Gr\u00e4del, E.: On transitive closure logic. In: Kleine B\u00fcning, H., J\u00e4ger, G., B\u00f6rger, E., Richter, M.M. (eds.) CSL 1991. LNCS, vol.\u00a0626, pp. 149\u2013163. Springer, Heidelberg (1992)"},{"issue":"2","key":"13_CR10","doi-asserted-by":"publisher","first-page":"81","DOI":"10.2307\/2266967","volume":"15","author":"L. Henkin","year":"1950","unstructured":"Henkin, L.: Completeness in the theory of types. The Journal of Symbolic Logic\u00a015(2), 81\u201391 (1950)","journal-title":"The Journal of Symbolic Logic"},{"issue":"4","key":"13_CR11","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1007\/s10849-004-2116-8","volume":"13","author":"S. Kepser","year":"2004","unstructured":"Kepser, S.: Querying linguistic treebanks with monadic second-order logic in linear time. J. of Logic, Lang. and Inf.\u00a013(4), 457\u2013470 (2004)","journal-title":"J. of Logic, Lang. and Inf."},{"key":"13_CR12","unstructured":"Kepser, S.: Properties of binary transitive closure logic over trees. In: Satta, G., Monachesi, P., Penn, G., Wintner, S. (eds.) Formal Grammar 2006, pp. 77\u201389 (2006)"},{"key":"13_CR13","unstructured":"Lafitte, G., Mazoyer, J.: Th\u00e9orie des mod\u00e8les et complexit\u00e9. Technical report, Ecole Normale Sup\u00e9rieure de Lyon (1998)"},{"issue":"1-3","key":"13_CR14","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/j.apal.2003.11.002","volume":"126","author":"J.A. Makowsky","year":"2004","unstructured":"Makowsky, J.A.: Algorithmic uses of the Feferman-Vaught theorem. Annals of Pure and Applied Logic\u00a0126(1-3), 159\u2013213 (2004)","journal-title":"Annals of Pure and Applied Logic"},{"key":"13_CR15","volume-title":"Extensions of First-Order logic","author":"M. Manzano","year":"1996","unstructured":"Manzano, M.: Extensions of First-Order logic. Cambridge University Press, New York (1996)"},{"key":"13_CR16","unstructured":"Matz, O., Schweikardt, N.: Expressive power of monadic logics on words, trees, pictures, and graphs. In: Gr\u00e4del, E., Flum, J., Wilke, T. (eds.) Logic and Automata: History and Perspectives, Texts in Logic and Games, pp. 531\u2013552. Amsterdam University Press (2007)"},{"key":"13_CR17","volume-title":"Descriptive Approach to Language - Theoretic Complexity","author":"J. Rogers","year":"1998","unstructured":"Rogers, J.: Descriptive Approach to Language - Theoretic Complexity. CSLI Publications, Stanford (1998)"},{"key":"13_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1007\/11965893_10","volume-title":"Database Theory \u2013 ICDT 2007","author":"B. Cate ten","year":"2006","unstructured":"ten Cate, B., Marx, M.: Axiomatizing the logical core of XPath 2.0. In: Schwentick, T., Suciu, D. (eds.) ICDT 2007. LNCS, vol.\u00a04353, pp. 134\u2013148. Springer, Heidelberg (2006)"},{"key":"13_CR19","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1145\/1376916.1376952","volume-title":"PODS 2008: Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems","author":"B. Cate ten","year":"2008","unstructured":"ten Cate, B., Segoufin, L.: XPath, transitive closure logic, and nested tree walking automata. In: PODS 2008: Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pp. 251\u2013260. ACM, New York (2008)"},{"key":"13_CR20","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/j.entcs.2006.05.044","volume":"165","author":"H.-J. Tiede","year":"2006","unstructured":"Tiede, H.-J., Kepser, S.: Monadic second-order logic and transitive closure logics over trees. Electron. Notes Theor. Comput. Sci.\u00a0165, 189\u2013199 (2006)","journal-title":"Electron. Notes Theor. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Logical Foundations of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-92687-0_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,5]],"date-time":"2019-03-05T03:01:14Z","timestamp":1551754874000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-92687-0_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540926863","9783540926870"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-92687-0_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}