{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T16:10:02Z","timestamp":1742659802637,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642287169"},{"type":"electronic","value":"9783642287176"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-28717-6_22","type":"book-chapter","created":{"date-parts":[[2012,3,6]],"date-time":"2012-03-06T15:13:04Z","timestamp":1331046784000},"page":"274-288","source":"Crossref","is-referenced-by-count":8,"title":["Regular Expressions for Data Words"],"prefix":"10.1007","author":[{"given":"Leonid","family":"Libkin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Domagoj","family":"Vrgo\u010d","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"22_CR1","doi-asserted-by":"crossref","unstructured":"Angles, R., Guti\u00e9rrez, C.: Survey of graph database models. ACM Comput. Surv.\u00a040(1) (2008)","DOI":"10.1145\/1322432.1322433"},{"key":"22_CR2","doi-asserted-by":"crossref","unstructured":"Barcel\u00f3, P., Hurtado, C., Libkin, L., Wood, P.: Expressive languages for path queries over graph-structured data. In: PODS 2010, pp. 3\u201314 (2010)","DOI":"10.1145\/1807085.1807089"},{"key":"22_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1007\/978-3-642-15205-4_12","volume-title":"Computer Science Logic","author":"M. Benedikt","year":"2010","unstructured":"Benedikt, M., Ley, C., Puppis, G.: Automata vs. Logics on Data Words. In: Dawar, A., Veith, H. (eds.) CSL 2010. LNCS, vol.\u00a06247, pp. 110\u2013124. Springer, Heidelberg (2010)"},{"key":"22_CR4","doi-asserted-by":"crossref","unstructured":"Bojanczyk, M., Parys, P.: XPath evaluation in linear time. In: PODS 2008, pp. 241\u2013250 (2008)","DOI":"10.1145\/1376916.1376951"},{"key":"22_CR5","doi-asserted-by":"crossref","unstructured":"Bojanczyk, M., David, C., Muscholl, A., Schwentick, T., Segoufin, L.: Two-variable logic on words with data. ACM TOCL\u00a012(4) (2011)","DOI":"10.1145\/1970398.1970403"},{"key":"22_CR6","doi-asserted-by":"crossref","unstructured":"Bojanczyk, M., Lasota, S.: An extension of data automata that captures XPath. In: LICS 2010, pp. 243\u2013252 (2010)","DOI":"10.1109\/LICS.2010.33"},{"issue":"3","key":"22_CR7","first-page":"443","volume":"64","author":"D. Calvanese","year":"2002","unstructured":"Calvanese, D., de Giacomo, G., Lenzerini, M., Vardi, M.Y.: Rewriting of regular expressions and regular path queries. JCSS\u00a064(3), 443\u2013465 (2002)","journal-title":"JCSS"},{"key":"22_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/978-3-642-22993-0_24","volume-title":"Mathematical Foundations of Computer Science 2011","author":"T. Colcombet","year":"2011","unstructured":"Colcombet, T., Ley, C., Puppis, G.: On the Use of Guards for Logics with Data. In: Murlak, F., Sankowski, P. (eds.) MFCS 2011. LNCS, vol.\u00a06907, pp. 243\u2013255. Springer, Heidelberg (2011)"},{"key":"22_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"},{"key":"22_CR10","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":"22_CR11","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/0020-0190(96)00095-6","volume":"59","author":"I. Glaister","year":"1996","unstructured":"Glaister, I., Shallit, J.: A lower bound technique for the size of nondeterministic finite automata. IPL\u00a059, 75\u201377 (1996)","journal-title":"IPL"},{"key":"22_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1007\/978-3-642-13089-2_47","volume-title":"Language and Automata Theory and Applications","author":"O. Grumberg","year":"2010","unstructured":"Grumberg, O., Kupferman, O., Sheinvald, S.: Variable Automata over Infinite Alphabets. In: Dediu, A.-H., Fernau, H., Mart\u00edn-Vide, C. (eds.) LATA 2010. LNCS, vol.\u00a06031, pp. 561\u2013572. Springer, Heidelberg (2010)"},{"issue":"2","key":"22_CR13","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1016\/0304-3975(94)90242-9","volume":"134","author":"M. Kaminski","year":"1994","unstructured":"Kaminski, M., Francez, N.: Finite memory automata. Theoretical Computer Science\u00a0134(2), 329\u2013363 (1994)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"22_CR14","doi-asserted-by":"crossref","first-page":"301","DOI":"10.3233\/FUN-2006-69304","volume":"69","author":"M. Kaminski","year":"2006","unstructured":"Kaminski, M., Tan, T.: Regular expressions for languages over infinite alphabets. Fundam. Inform.\u00a069(3), 301\u2013318 (2006)","journal-title":"Fundam. Inform."},{"key":"22_CR15","doi-asserted-by":"crossref","unstructured":"Libkin, L.: Logics for unranked trees: an overview. Logical Methods in Computer Science\u00a02(3) (2006)","DOI":"10.2168\/LMCS-2(3:2)2006"},{"key":"22_CR16","unstructured":"Libkin, L., Vrgo\u010d, D.: Regular path queries on graphs with data. In: ICDT 2012 (to appear, 2012)"},{"key":"22_CR17","doi-asserted-by":"publisher","first-page":"929","DOI":"10.1145\/1114244.1114247","volume":"30","author":"M. Marx","year":"2005","unstructured":"Marx, M.: Conditional XPath. ACM TODS\u00a030, 929\u2013959 (2005)","journal-title":"ACM TODS"},{"issue":"6","key":"22_CR18","doi-asserted-by":"publisher","first-page":"1235","DOI":"10.1137\/S009753979122370X","volume":"24","author":"A.O. Mendelzon","year":"1995","unstructured":"Mendelzon, A.O., Wood, P.T.: Finding regular simple paths in graph databases. SIAM J. Comput.\u00a024(6), 1235\u20131258 (1995)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"22_CR19","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1145\/601858.601869","volume":"31","author":"F. Neven","year":"2002","unstructured":"Neven, F.: Automata theory for XML researchers. SIGMOD Record\u00a031(3), 39\u201346 (2002)","journal-title":"SIGMOD Record"},{"issue":"3","key":"22_CR20","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":"22_CR21","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/S0304-3975(99)00105-X","volume":"231","author":"H. Sakamoto","year":"2000","unstructured":"Sakamoto, H., Ikeda, D.: Intractability of decision problems for finite-memory automata. Theor. Comput. Sci.\u00a0231(2), 297\u2013308 (2000)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"22_CR22","first-page":"289","volume":"73","author":"T. Schwentick","year":"2007","unstructured":"Schwentick, T.: Automata for XML \u2013 A survey. JCSS\u00a073(3), 289\u2013315 (2007)","journal-title":"JCSS"},{"key":"22_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/11874683_3","volume-title":"Computer Science Logic","author":"L. Segoufin","year":"2006","unstructured":"Segoufin, L.: Automata and Logics for Words and Trees over an Infinite Alphabet. In: \u00c9sik, Z. (ed.) CSL 2006. LNCS, vol.\u00a04207, pp. 41\u201357. Springer, Heidelberg (2006)"},{"key":"22_CR24","unstructured":"Sipser, M.: Introduction to the Theory of Computation. PWS Publishing (1997)"},{"key":"22_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"}],"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-28717-6_22.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T14:59:11Z","timestamp":1742655551000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-28717-6_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642287169","9783642287176"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-28717-6_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}