{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:47:26Z","timestamp":1725558446049},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540408017"},{"type":"electronic","value":"9783540452201"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-45220-1_20","type":"book-chapter","created":{"date-parts":[[2010,6,25]],"date-time":"2010-06-25T23:33:58Z","timestamp":1277508838000},"page":"226-240","source":"Crossref","is-referenced-by-count":9,"title":["Comparing the Succinctness of Monadic Query Languages over Finite Trees"],"prefix":"10.1007","author":[{"given":"Martin","family":"Grohe","sequence":"first","affiliation":[]},{"given":"Nicole","family":"Schweikardt","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"20_CR1","volume-title":"Data on the Web: From Relations to Semistructured Data and XML","author":"S. Abiteboul","year":"1999","unstructured":"Abiteboul, S., Buneman, P., Suciu, D.: Data on the Web: From Relations to Semistructured Data and XML. Morgan Kaufmann, San Francisco (1999)"},{"key":"20_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)"},{"issue":"3","key":"20_CR3","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1093\/jigpal\/8.3.325","volume":"8","author":"N. Alechina","year":"2000","unstructured":"Alechina, N., Immerman, N.: Reachability logic: An efficient fragment of transitive closure logic. Logic Journal of the IGPL\u00a08(3), 325\u2013338 (2000)","journal-title":"Logic Journal of the IGPL"},{"key":"20_CR4","doi-asserted-by":"crossref","unstructured":"Adler, M., Immerman, N.: An n! lower bound on formula size. In: Proceedings of the 16th IEEE Symposium on Logic in Computer Science, pp. 197\u2013206 (2001)","DOI":"10.1109\/LICS.2001.932497"},{"key":"20_CR5","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0022-0000(82)90012-5","volume":"25","author":"A. Chandra","year":"1982","unstructured":"Chandra, A., Harel, D.: Structure and complexity of relational queries. Journal of Computer and Systems Sciences\u00a025, 99\u2013128 (1982)","journal-title":"Journal of Computer and Systems Sciences"},{"issue":"1","key":"20_CR6","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/S0304-3975(01)00174-8","volume":"289","author":"E. Dantsin","year":"2002","unstructured":"Dantsin, E., Goerdt, A., Hirsch, E.A., Kannan, R., Kleinberg, J., Papadimitriou, C., Raghavan, P., Sch\u00f6ning, U.: A deterministic (2 \u22122\/(k+1)) n algorithm for k-SAT based on local search. Theoretical Computer Science\u00a0289(1), 69\u201383 (2002); Revised version of: Deterministic algorithms for k-SAT based on covering codes and local search. In: ICALP 2000. LNCS, vol. 1853 (2000)","journal-title":"Theoretical Computer Science"},{"key":"20_CR7","volume-title":"Finite model theory","author":"H.-D. Ebbinghaus","year":"1999","unstructured":"Ebbinghaus, H.-D., Flum, J.: Finite model theory, 2nd edn. Springer, New York (1999)","edition":"2"},{"issue":"2","key":"20_CR8","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1006\/inco.2001.2953","volume":"179","author":"K. Etessami","year":"2002","unstructured":"Etessami, K., Vardi, M.Y., Wilke, T.: First-order logic with two variables and unary temporal logic. Information and Computation\u00a0179(2), 279\u2013295 (2002)","journal-title":"Information and Computation"},{"key":"20_CR9","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1002\/malq.19750210112","volume":"21","author":"R. Fagin","year":"1975","unstructured":"Fagin, R.: Monadic generalized spectra. Zeitschrift f\u00fcr mathematische Logik und Grundlagen der mathematik\u00a021, 89\u201396 (1975)","journal-title":"Zeitschrift f\u00fcr mathematische Logik und Grundlagen der mathematik"},{"key":"20_CR10","unstructured":"Frick, M., Grohe, M.: The complexity of first-order and monadic second-order logic revisited. Journal version of LICS 2002 paper (2003), Available at http:\/\/www.dcs.ed.ac.uk\/home\/grohe\/pub.html"},{"key":"20_CR11","doi-asserted-by":"crossref","unstructured":"Frick, M., Grohe, M., Koch, C.: Query evaluation on compressed trees. In: 18th IEEE Symposium on Logic in Computer Science (LICS 2003), Ottawa, Canada (June 2003)","DOI":"10.1109\/LICS.2003.1210058"},{"key":"20_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1007\/3-540-44450-5_2","volume-title":"FST TCS 2000: Foundations of Software Technology and Theoretical Science","author":"M.F. Fernandez","year":"2000","unstructured":"Fernandez, M.F., Sim\u00e9on, J., Wadler, P.: An algebra for XML query. In: Kapoor, S., Prasad, S. (eds.) FST TCS 2000. LNCS, vol.\u00a01974, pp. 11\u201345. Springer, Heidelberg (2000)"},{"key":"20_CR13","doi-asserted-by":"crossref","unstructured":"Gottlob, G., Koch, C.: Monadic datalog and the expressive power of web information extraction languages. Journal version of PODS 2002 paper. Available as CoRR report arXiv:cs.DB\/0211020 (November 2002) (submitted)","DOI":"10.1145\/543613.543617"},{"key":"20_CR14","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/S0304-3975(98)00308-9","volume":"224","author":"E. Gr\u00e4del","year":"1999","unstructured":"Gr\u00e4del, E., Otto, M.: On Logics with Two Variables. Theoretical Computer Science\u00a0224, 73\u2013113 (1999)","journal-title":"Theoretical Computer Science"},{"key":"20_CR15","doi-asserted-by":"crossref","unstructured":"Grohe, M., Schweikardt, N.: Comparing the succinctness of monadic query languages over finite trees. Technical Report EDI-INF-RR-0168, School of Informatics, University of Edinburgh (2003)","DOI":"10.1007\/978-3-540-45220-1_20"},{"key":"20_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1007\/3-540-45271-0_15","volume-title":"The World Wide Web and Databases","author":"H. Hosoya","year":"2001","unstructured":"Hosoya, H., Pierce, B.C.: XDuce: A typed XML processing language (preliminary report). In: Suciu, D., Vossen, G. (eds.) WebDB 2000. LNCS, vol.\u00a01997, p. 226. Springer, Heidelberg (2001)"},{"key":"20_CR17","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0539-5","volume-title":"Descriptive complexity","author":"N. Immerman","year":"1999","unstructured":"Immerman, N.: Descriptive complexity. Springer, New York (1999)"},{"key":"20_CR18","unstructured":"Kamp, H.: Tense Logic and the theory of linear order. PhD thesis, University of California, Los Angeles (1968)"},{"key":"20_CR19","doi-asserted-by":"crossref","unstructured":"Koch, C.: Efficient processing of expressive node-selecting queries on XML data in secondary storage: A tree-automata based approach. In: Proceedings of the 29th Conference on Very Large Data Bases (2003) (to appear)","DOI":"10.1016\/B978-012722442-8\/50030-6"},{"key":"20_CR20","unstructured":"Neven, F.: Design and Analysis of Query Languages for Structured Documents \u2013 A Formal and Logical Approach. PhD thesis, Limburgs Universitair Centrum (1999)"},{"issue":"1-2","key":"20_CR21","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. Theoretical Computer Science\u00a0275(1-2), 633\u2013674 (2002); Journal version of PODS 2000 paper","journal-title":"Theoretical Computer Science"},{"key":"20_CR22","volume-title":"Handbook of formal languages","author":"W. Thomas","year":"1996","unstructured":"Thomas, W.: Languages, automata, and logic. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of formal languages, vol.\u00a03, Springer, New York (1996)"},{"key":"20_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"628","DOI":"10.1007\/BFb0055090","volume-title":"Automata, Languages and Programming","author":"M.Y. Vardi","year":"1998","unstructured":"Vardi, M.Y.: Reasoning about the past with two-way automata. In: Larsen, K.G., Skyum, S., Winskel, G. (eds.) ICALP 1998. LNCS, vol.\u00a01443, pp. 628\u2013641. Springer, Heidelberg (1998)"},{"key":"20_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1007\/3-540-46691-6_9","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"T. Wilke","year":"1999","unstructured":"Wilke, T.: CTL+ is exponentially more succinct than CTL. In: Pandu Rangan, C., Raman, V., Sarukkai, S. (eds.) FST TCS 1999. LNCS, vol.\u00a01738, pp. 110\u2013121. Springer, Heidelberg (1999)"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-45220-1_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T13:01:53Z","timestamp":1559221313000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-45220-1_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540408017","9783540452201"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-45220-1_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}