{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T20:19:57Z","timestamp":1725567597277},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642162411"},{"type":"electronic","value":"9783642162428"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"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":[[2010]]},"DOI":"10.1007\/978-3-642-16242-8_18","type":"book-chapter","created":{"date-parts":[[2010,10,4]],"date-time":"2010-10-04T12:51:59Z","timestamp":1286196719000},"page":"248-262","source":"Crossref","is-referenced-by-count":6,"title":["On the Satisfiability of Two-Variable Logic over Data Words"],"prefix":"10.1007","author":[{"given":"Claire","family":"David","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leonid","family":"Libkin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tony","family":"Tan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"18_CR1","unstructured":"http:\/\/homepages.inf.ed.ac.uk\/ttan\/publications\/2010\/sdw-lpar10.pdf"},{"key":"18_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":"18_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"862","DOI":"10.1007\/978-3-540-73420-8_74","volume-title":"Automata, Languages and Programming","author":"H. Bj\u00f6rklund","year":"2007","unstructured":"Bj\u00f6rklund, H., Bojanczyk, M.: Bounded depth data trees. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596, pp. 862\u2013874. Springer, Heidelberg (2007)"},{"key":"18_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1007\/BFb0017306","volume-title":"Theoretical Computer Science","author":"L. Boasson","year":"1981","unstructured":"Boasson, L.: Some applications of CFL\u2019s over infinte alphabets. In: Deussen, P. (ed.) GI-TCS 1981. LNCS, vol.\u00a0104, pp. 146\u2013151. Springer, Heidelberg (1981)"},{"key":"18_CR5","doi-asserted-by":"crossref","unstructured":"Bojanczyk, M., Muscholl, A., Schwentick, T., Segoufin, L.: Two-variable logic on data trees and XML reasoning. J.\u00a0ACM\u00a056(3) (2009)","DOI":"10.1145\/1516512.1516515"},{"key":"18_CR6","doi-asserted-by":"crossref","unstructured":"Bojanczyk, M., David, C., Muscholl, A., Schwentick, T., Segoufin, L.: Two-variable logic on words with data. In: LICS 2006, pp. 7\u201316 (2006)","DOI":"10.1109\/LICS.2006.51"},{"key":"18_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1007\/3-540-44685-0_17","volume-title":"CONCUR 2001 - Concurrency Theory","author":"P. Bouyer","year":"2001","unstructured":"Bouyer, P., Petit, A., Th\u00e9rien, D.: An algebraic characterization of data and timed languages. In: Larsen, K.G., Nielsen, M. (eds.) CONCUR 2001. LNCS, vol.\u00a02154, pp. 248\u2013261. Springer, Heidelberg (2001)"},{"key":"18_CR8","doi-asserted-by":"crossref","unstructured":"Dal-Zilio, S., Lugiez, D., Meyssonnier, C.: A logic you can count on. In: POPL 2004, pp. 135\u2013146 (2004)","DOI":"10.1145\/964001.964013"},{"key":"18_CR9","doi-asserted-by":"crossref","unstructured":"Demri, S., Lazic, R.: LTL with the freeze quantifier and register automata. ACM TOCL\u00a010(3) (2009)","DOI":"10.1145\/1507244.1507246"},{"issue":"3","key":"18_CR10","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1145\/567112.567117","volume":"49","author":"W. Fan","year":"2002","unstructured":"Fan, W., Libkin, L.: On XML integrity constraints in the presence of DTDs. J. ACM\u00a049(3), 368\u2013406 (2002)","journal-title":"J. ACM"},{"key":"18_CR11","doi-asserted-by":"crossref","unstructured":"Figueira, D.: Satisfiability of downward XPath with data equality tests. In: PODS 2009, pp. 197\u2013206 (2009)","DOI":"10.1145\/1559795.1559827"},{"key":"18_CR12","doi-asserted-by":"publisher","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 J. Math.\u00a016, 285\u2013296 (1966)","journal-title":"Pacific J. Math."},{"issue":"1","key":"18_CR13","first-page":"53","volume":"3","author":"E. Gr\u00e4del","year":"1997","unstructured":"Gr\u00e4del, E., Kolaitis, P., Vardi, M.: On the decision problem for two-variable first-order logic. BSL\u00a03(1), 53\u201369 (1997)","journal-title":"BSL"},{"key":"18_CR14","doi-asserted-by":"crossref","unstructured":"Jurdzinski, M., Lazic, R.: Alternation-free modal mu-calculus for data trees. In: LICS 2007, pp. 131\u2013140 (2007)","DOI":"10.1109\/LICS.2007.11"},{"key":"18_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"386","DOI":"10.1007\/978-3-540-78127-1_21","volume-title":"Pillars of Computer Science","author":"M. Kaminski","year":"2008","unstructured":"Kaminski, M., Tan, T.: Tree automata over infinite alphabets. In: Avron, A., Dershowitz, N., Rabinovich, A. (eds.) Pillars of Computer Science. LNCS, vol.\u00a04800, pp. 386\u2013423. Springer, Heidelberg (2008)"},{"key":"18_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/11523468_4","volume-title":"Automata, Languages and Programming","author":"L. Libkin","year":"2005","unstructured":"Libkin, L.: Logics for unranked trees: an overview. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 35\u201350. Springer, Heidelberg (2005)"},{"key":"18_CR17","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":"3","key":"18_CR18","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1145\/1013560.1013562","volume":"5","author":"F. Neven","year":"2004","unstructured":"Neven, F., Schwentick, T., Vianu, V.: Finite state machines for strings over infinite alphabets. ACM TOCL\u00a05(3), 403\u2013435 (2004)","journal-title":"ACM TOCL"},{"issue":"2","key":"18_CR19","doi-asserted-by":"publisher","first-page":"685","DOI":"10.2307\/2695037","volume":"66","author":"M. Otto","year":"2001","unstructured":"Otto, M.: Two variable first-order logic over ordered domains. J. Symb. Log.\u00a066(2), 685\u2013702 (2001)","journal-title":"J. Symb. Log."},{"issue":"4","key":"18_CR20","doi-asserted-by":"publisher","first-page":"765","DOI":"10.1145\/322276.322287","volume":"28","author":"C. Papadimitriou","year":"1981","unstructured":"Papadimitriou, C.: On the complexity of integer programming. J. ACM\u00a028(4), 765\u2013768 (1981)","journal-title":"J. ACM"},{"issue":"4","key":"18_CR21","doi-asserted-by":"publisher","first-page":"570","DOI":"10.1145\/321356.321364","volume":"13","author":"R. Parikh","year":"1966","unstructured":"Parikh, R.: On context-free languages. J. ACM\u00a013(4), 570\u2013581 (1966)","journal-title":"J. ACM"},{"key":"18_CR22","first-page":"289","volume":"73","author":"T. Schwentick","year":"2007","unstructured":"Schwentick, T.: Automata for XML \u2013 a survey. JCSS\u00a073, 289\u2013315 (2007)","journal-title":"JCSS"},{"key":"18_CR23","doi-asserted-by":"crossref","unstructured":"Seidl, H., Schwentick, T., Muscholl, A.: Numerical document queries. In: PODS 2003, pp. 155\u2013166 (2003)","DOI":"10.1145\/773153.773169"},{"key":"18_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1136","DOI":"10.1007\/978-3-540-27836-8_94","volume-title":"Automata, Languages and Programming","author":"H. Seidl","year":"2004","unstructured":"Seidl, H., Schwentick, T., Muscholl, A., Habermehl, P.: Counting in trees for free. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 1136\u20131149. Springer, Heidelberg (2004)"},{"key":"18_CR25","doi-asserted-by":"crossref","unstructured":"Tan, T.: Graph reachability and pebble automata over infinite alphabets. In: LICS 2009, pp. 157\u2013166 (2009)","DOI":"10.1109\/LICS.2009.23"},{"key":"18_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"712","DOI":"10.1007\/978-3-642-03816-7_60","volume-title":"Mathematical Foundations of Computer Science 2009","author":"T. Tan","year":"2009","unstructured":"Tan, T.: On pebble automata for data languages with decidable emptiness problem. In: Kr\u00e1lovi\u010d, R., Niwi\u0144ski, D. (eds.) MFCS 2009. LNCS, vol.\u00a05734, pp. 712\u2013723. Springer, Heidelberg (2009)"},{"key":"18_CR27","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/978-3-642-59126-6_7","volume-title":"Handbook of Formal Languages","author":"W. Thomas","year":"1997","unstructured":"Thomas, W.: Languages, automata, and logic. In: Handbook of Formal Languages, vol.\u00a03, pp. 389\u2013455. Springer, Heidelberg (1997)"},{"key":"18_CR28","doi-asserted-by":"crossref","unstructured":"Vianu, V.: A web Odyssey: from Codd to XML. In: PODS 2001, pp. 1\u201315 (2001)","DOI":"10.1145\/375551.375554"}],"container-title":["Lecture Notes in Computer Science","Logic for Programming, Artificial Intelligence, and Reasoning"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-16242-8_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,5]],"date-time":"2019-06-05T06:02:23Z","timestamp":1559714543000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-16242-8_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642162411","9783642162428"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-16242-8_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}