{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:10:46Z","timestamp":1760202646802,"version":"3.41.2"},"reference-count":14,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2012,2,16]],"date-time":"2012-02-16T00:00:00Z","timestamp":1329350400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"funder":[{"DOI":"10.13039\/501100000780","name":"European Commission","doi-asserted-by":"crossref","award":["233599"],"award-info":[{"award-number":["233599"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>We define a new kind of automata recognizing properties of data words or data trees and prove that the automata capture all queries definable in Regular XPath. We show that the automata-theoretic approach may be applied to answer decidability and expressibility questions for XPath.<\/jats:p>","DOI":"10.2168\/lmcs-8(1:5)2012","type":"journal-article","created":{"date-parts":[[2012,9,6]],"date-time":"2012-09-06T10:03:11Z","timestamp":1346925791000},"source":"Crossref","is-referenced-by-count":7,"title":["An extension of data automata that captures XPath"],"prefix":"10.46298","volume":"Volume 8, Issue 1","author":[{"given":"Miko\u0142aj","family":"Boja\u0144czyk","sequence":"first","affiliation":[]},{"given":"S\u0142awomir","family":"Lasota","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2012,2,16]]},"reference":[{"key":"10.2168\/LMCS-8(1:5)2012_DBLP:journals\/jacm\/BenediktFG08","doi-asserted-by":"publisher","DOI":"10.1145\/1346330.1346333"},{"key":"10.2168\/LMCS-8(1:5)2012_BjorklundS07","doi-asserted-by":"crossref","unstructured":"H. Bj\u00f6rklund and T. Schwentick. On notions of regularity for data languages. InFCT, pages 88-99, 2007.","DOI":"10.1007\/978-3-540-74240-1_9"},{"key":"10.2168\/LMCS-8(1:5)2012_BL10","doi-asserted-by":"crossref","unstructured":"M. Boja\u00cc\u00a4czyk and S. Lasota. An extension of data automata that captures XPath. InProc. LICS'10, pages 243-252, 2010.","DOI":"10.1109\/LICS.2010.33"},{"key":"10.2168\/LMCS-8(1:5)2012_BojanczykJACM09","doi-asserted-by":"crossref","unstructured":"M. Boja\u00cc\u00a4czyk, A. Muscholl, T. Schwentick, and L. Segoufin. Two-variable logic on data trees and XML reasoning.J. ACM, 56(3), 2009.","DOI":"10.1145\/1516512.1516515"},{"issue":"4","key":"10.2168\/LMCS-8(1:5)2012_BojanczykDMSS11","first-page":"27","volume":"12","author":"Mikolaj Bojanczyk, Claire David, Anca Mu","year":"2011","journal-title":"ACM Trans. Comput. Log."},{"key":"10.2168\/LMCS-8(1:5)2012_DBLP:conf\/icalp\/Colcombet07","doi-asserted-by":"crossref","unstructured":"T. Colcombet. A combinatorial theorem for trees. InICALP, pages 901-912, 2007.","DOI":"10.1007\/978-3-540-73420-8_77"},{"key":"10.2168\/LMCS-8(1:5)2012_CLT05","doi-asserted-by":"crossref","unstructured":"Julien Cristau, Christof L\u00f6ding, and Wolfgang Thomas. Deterministic automata on unranked trees. InFCT, pages 68-79, 2005.","DOI":"10.1007\/11537311_7"},{"key":"10.2168\/LMCS-8(1:5)2012_DBLP:journals\/tocl\/DemriL09","doi-asserted-by":"publisher","DOI":"10.1145\/1507244.1507246"},{"key":"10.2168\/LMCS-8(1:5)2012_DBLP:conf\/pods\/Figueira09","doi-asserted-by":"crossref","unstructured":"D. Figueira. Satisfiability of downward XPath with data equality tests. InPODS, pages 197-206, 2009.","DOI":"10.1145\/1559795.1559827"},{"key":"10.2168\/LMCS-8(1:5)2012_figueira-icdt2010","doi-asserted-by":"crossref","unstructured":"D. Figueira. Forward-XPath and extended register automata on data-trees. InICDT, pages 231-241, 2010.","DOI":"10.1145\/1804669.1804699"},{"key":"10.2168\/LMCS-8(1:5)2012_DBLP:conf\/dbpl\/GeertsF05","doi-asserted-by":"crossref","unstructured":"F. Geerts and W. Fan. Satisfiability of XPath queries with sibling axes. InDBPL, pages 122-137, 2005.","DOI":"10.1007\/11601524_8"},{"key":"10.2168\/LMCS-8(1:5)2012_DBLP:conf\/lics\/JurdzinskiL07","doi-asserted-by":"crossref","unstructured":"M. Jurdzi\u00cc\u00a4ski and R. Lazi\u00c4\u0087. Alternation-free modal mu-calculus for data trees. InLICS, pages 131-140, 2007.","DOI":"10.1109\/LICS.2007.11"},{"issue":"2","key":"10.2168\/LMCS-8(1:5)2012_KaminskiF94","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1016\/0304-3975(94)90242-9","volume":"134","author":"M. Kaminski and N. Francez","year":"1994","journal-title":"Theor. Comput. Sci."},{"key":"10.2168\/LMCS-8(1:5)2012_DBLP:conf\/csl\/Segoufin06","doi-asserted-by":"crossref","unstructured":"L. Segoufin. Automata and logics for words and trees over an infinite alphabet. InCSL, pages 41-57, 2006.","DOI":"10.1007\/11874683_3"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/672\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/672\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,7]],"date-time":"2025-04-07T23:09:42Z","timestamp":1744067382000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/672"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,2,16]]},"references-count":14,"URL":"https:\/\/doi.org\/10.2168\/lmcs-8(1:5)2012","relation":{"is-same-as":[{"id-type":"arxiv","id":"1201.0597","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1201.0597","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2012,2,16]]},"article-number":"672"}}