{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T19:49:05Z","timestamp":1725738545603},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642392115"},{"type":"electronic","value":"9783642392122"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-39212-2_10","type":"book-chapter","created":{"date-parts":[[2013,7,2]],"date-time":"2013-07-02T13:09:19Z","timestamp":1372770559000},"page":"74-88","source":"Crossref","is-referenced-by-count":9,"title":["Complexity of Two-Variable Logic on Finite Trees"],"prefix":"10.1007","author":[{"given":"Saguy","family":"Benaim","sequence":"first","affiliation":[]},{"given":"Michael","family":"Benedikt","sequence":"additional","affiliation":[]},{"given":"Witold","family":"Charatonik","sequence":"additional","affiliation":[]},{"given":"Emanuel","family":"Kiero\u0144ski","sequence":"additional","affiliation":[]},{"given":"Rastislav","family":"Lenhardt","sequence":"additional","affiliation":[]},{"given":"Filip","family":"Mazowiecki","sequence":"additional","affiliation":[]},{"given":"James","family":"Worrell","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"10_CR1","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1023\/A:1004275029985","volume":"27","author":"H. Andr\u00e9ka","year":"1998","unstructured":"Andr\u00e9ka, H., van Benthem, J., N\u00e9meti, I.: Modal languages and bounded fragments of predicate logic. J. Phil. Logic\u00a027, 217\u2013274 (1998)","journal-title":"J. Phil. Logic"},{"unstructured":"Benaim, S., Benedikt, M., Lenhardt, R., Worrell, J.: Controlling the depth, size, and number of subtrees in two variable logic over trees. CoRR abs\/1304.6925 (2013)","key":"10_CR2"},{"issue":"2","key":"10_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1346330.1346333","volume":"55","author":"M. Benedikt","year":"2008","unstructured":"Benedikt, M., Fan, W., Geerts, F.: XPath satisfiability in the presence of DTDs. J. ACM\u00a055(2), 8:1\u20138:79 (2008)","journal-title":"J. ACM"},{"issue":"1","key":"10_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1456650.1456653","volume":"41","author":"M. Benedikt","year":"2008","unstructured":"Benedikt, M., Koch, C.: XPath Leashed. ACM Comput. Surv.\u00a041(1), 3:1\u20133:54 (2008)","journal-title":"ACM Comput. Surv."},{"doi-asserted-by":"crossref","unstructured":"Benedikt, M., Lenhardt, R., Worrell, J.: Verification of two-variable logic revisited. In: QEST, pp. 114\u2013123. IEEE (2012)","key":"10_CR5","DOI":"10.1109\/QEST.2012.38"},{"doi-asserted-by":"crossref","unstructured":"Boja\u0144czyk, M., Muscholl, A., Schwentick, T., Segoufin, L.: Two-variable logic on data trees and XML reasoning. J. ACM\u00a056(3) (2009)","key":"10_CR6","DOI":"10.1145\/1516512.1516515"},{"unstructured":"Charatonik, W., Kiero\u0144ski, E., Mazowiecki, F.: Satisfiability of the two-variable fragment of first-order logic over trees. CoRR abs\/1304.7204 (2013)","key":"10_CR7"},{"unstructured":"Charatonik, W., Witkowski, P.: Two-variable logic with counting and trees. In: LICS. IEEE (to appear, 2013)","key":"10_CR8"},{"issue":"2","key":"10_CR9","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. Inf. Comput.\u00a0179(2), 279\u2013295 (2002)","journal-title":"Inf. Comput."},{"unstructured":"Figueira, D.: Satisfiability for two-variable logic with two successor relations on finite linear orders. CoRR abs\/1204.2495 (2012)","key":"10_CR10"},{"issue":"1","key":"10_CR11","doi-asserted-by":"publisher","first-page":"53","DOI":"10.2307\/421196","volume":"3","author":"E. Gr\u00e4del","year":"1997","unstructured":"Gr\u00e4del, E., Kolaitis, P.G., Vardi, M.Y.: On the decision problem for two-variable first-order logic. Bull. Symb. Logic\u00a03(1), 53\u201369 (1997)","journal-title":"Bull. Symb. Logic"},{"key":"10_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"608","DOI":"10.1007\/3-540-45841-7_50","volume-title":"STACS 2002","author":"E. Kiero\u0144ski","year":"2002","unstructured":"Kiero\u0144ski, E.: EXPSPACE-complete variant of guarded fragment with transitivity. In: Alt, H., Ferreira, A. (eds.) STACS 2002. LNCS, vol.\u00a02285, pp. 608\u2013619. Springer, Heidelberg (2002)"},{"key":"10_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1007\/11538363_22","volume-title":"Computer Science Logic","author":"E. Kiero\u0144ski","year":"2005","unstructured":"Kiero\u0144ski, E.: Results on the guarded fragment with equivalence or transitive relations. In: Ong, L. (ed.) CSL 2005. LNCS, vol.\u00a03634, pp. 309\u2013324. Springer, Heidelberg (2005)"},{"key":"10_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1007\/978-3-540-24741-8_28","volume-title":"Advances in Database Technology - EDBT 2004","author":"M. Marx","year":"2004","unstructured":"Marx, M.: XPath with conditional axis relations. In: Bertino, E., Christodoulakis, S., Plexousakis, D., Christophides, V., Koubarakis, M., B\u00f6hm, K. (eds.) EDBT 2004. LNCS, vol.\u00a02992, pp. 477\u2013494. Springer, Heidelberg (2004)"},{"unstructured":"Marxand, M., de Rijke, M.: Semantic characterization of navigational XPath. In: TDM. CTIT Workshop Proceedings Series, pp. 73\u201379 (2004)","key":"10_CR15"},{"unstructured":"Szwast, W., Tendera, L.: FO2 with one transitive relation is decidable. In: STACS. LIPIcs, vol.\u00a020, pp. 317\u2013328, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2013)","key":"10_CR16"},{"unstructured":"Stockmeyer, L.J.: The Complexity of Decision Problems in Automata Theory and Logic. PhD thesis, Massachusetts Institute of Technology (1974)","key":"10_CR17"},{"doi-asserted-by":"crossref","unstructured":"Thomas, W.: Languages, automata, and logic. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages. Springer (1997)","key":"10_CR18","DOI":"10.1007\/978-3-642-59126-6_7"},{"unstructured":"Weis, P.: Expressiveness and Succinctness of First-Order Logic on Finite Words. PhD thesis, University of Massachusetts (2011)","key":"10_CR19"}],"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-642-39212-2_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T09:32:32Z","timestamp":1557912752000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-39212-2_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642392115","9783642392122"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-39212-2_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}