{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T15:44:48Z","timestamp":1775058288049,"version":"3.50.1"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2005,6,1]],"date-time":"2005-06-01T00:00:00Z","timestamp":1117584000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMOD Rec."],"published-print":{"date-parts":[[2005,6]]},"abstract":"<jats:p>We give semantic characterizations of the expressive power of navigational XPath (a.k.a. Core XPath) in terms of first order logic. XPath can be used to specify sets of nodes and sets of paths in an XML document tree. We consider both uses. For sets of nodes, XPath is equally expressive as first order logic in two variables. For paths, XPath can be defined using four simple connectives, which together yield the class of first order definable relations which are safe for bisimulation. Furthermore, we give a characterization of the XPath expressible paths in terms of conjunctive queries.<\/jats:p>","DOI":"10.1145\/1083784.1083792","type":"journal-article","created":{"date-parts":[[2005,11,9]],"date-time":"2005-11-09T22:23:27Z","timestamp":1131575007000},"page":"41-46","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":55,"title":["Semantic characterizations of navigational XPath"],"prefix":"10.1145","volume":"34","author":[{"given":"Maarten","family":"Marx","sequence":"first","affiliation":[{"name":"University of Amsterdam, Amsterdam, The Netherlands"}]},{"given":"Maarten","family":"de Rijke","sequence":"additional","affiliation":[{"name":"University of Amsterdam, Amsterdam, The Netherlands"}]}],"member":"320","published-online":{"date-parts":[[2005,6]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Rijke. CTL Model Checking for Processing Simple XPath Queries. In Proc. TIME 2004","author":"Afanasiev L.","year":"2004"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/645505.656448"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0306-4379(01)00033-3"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/381193"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/647845.736734"},{"key":"e_1_2_1_6_1","unstructured":"K. Etessami M. Vardi and Th. Wilke. First-order logic with two variables and unary temporal logic.  K. Etessami M. Vardi and Th. Wilke. First-order logic with two variables and unary temporal logic."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/645683.664569"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773171"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055585"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055562"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30570-5_8"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543623"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/335168.335171"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/375551.375569"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/335168.335217"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/375551.375554"},{"key":"e_1_2_1_17_1","unstructured":"W3C. XML path language (XPath): Version 1.0. http:\/\/www.w3.org\/TR\/xpath.html.  W3C. XML path language (XPath): Version 1.0. http:\/\/www.w3.org\/TR\/xpath.html."},{"key":"e_1_2_1_18_1","unstructured":"W3C. XML path language (XPath): Version 2.0. http:\/\/www.w3.org\/TR\/xpath20\/.  W3C. XML path language (XPath): Version 2.0. http:\/\/www.w3.org\/TR\/xpath20\/."},{"key":"e_1_2_1_19_1","unstructured":"W3C. XML schema part 1: Structures. http:\/\/www.w3.org\/TR\/xmlschema-1.  W3C. XML schema part 1: Structures. http:\/\/www.w3.org\/TR\/xmlschema-1."},{"key":"e_1_2_1_20_1","unstructured":"W3C. XQuery 1.0: A query language for XML. http:\/\/www.w3.org\/TR\/\/xquery\/.  W3C. XQuery 1.0: A query language for XML. http:\/\/www.w3.org\/TR\/\/xquery\/."},{"key":"e_1_2_1_21_1","unstructured":"W3C. XSL transformations language (XSLT): Version 2.0. http:\/\/www.w3.org\/TR\/xslt20\/.  W3C. XSL transformations language (XSLT): Version 2.0. http:\/\/www.w3.org\/TR\/xslt20\/."},{"key":"e_1_2_1_22_1","volume-title":"Bell Labs","author":"Wadler P.","year":"2000"}],"container-title":["ACM SIGMOD Record"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1083784.1083792","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1083784.1083792","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:08:23Z","timestamp":1750262903000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1083784.1083792"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,6]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2005,6]]}},"alternative-id":["10.1145\/1083784.1083792"],"URL":"https:\/\/doi.org\/10.1145\/1083784.1083792","relation":{},"ISSN":["0163-5808"],"issn-type":[{"value":"0163-5808","type":"print"}],"subject":[],"published":{"date-parts":[[2005,6]]},"assertion":[{"value":"2005-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}