Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/20496
Title: | Structural characterizations of the navigational expressiveness of relation algebras on a tree | Authors: | Fletcher, George H. L. GYSSENS, Marc Paredaens, Jan Van Gucht, Dirk Wu, Yuqing |
Issue Date: | 2016 | Publisher: | ACADEMIC PRESS INC ELSEVIER SCIENCE | Source: | JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 82 (2), p. 229-259 | Abstract: | We study the expressiveness on a given document of various fragments of XPath, the core navigational language on XML documents. Viewing these languages as fragments of Tarski's relation algebra, we give characterizations for when a binary relation on the document's nodes (i.e., a set of paths) is definable by an expression in these algebras. In contrast with this "global view" on language semantics, there is also a "local view" where one is interested in the nodes to which one can navigate starting from a particular node. In this view, we characterize when a set of nodes can be defined as the result of applying an expression to a given node. All of these global and local definability results are obtained using a two-step methodology, which consists of first characterizing when two nodes cannot be distinguished by an expression in the language, and then bootstrapping these characterizations to the desired results. (C) 2015 Elsevier Inc. All rights reserved. | Notes: | [Fletcher, George H. L.] Eindhoven Univ Technol, NL-5600 MB Eindhoven, Netherlands. [Gyssens, Marc] Hasselt Univ, Hasselt, Belgium. [Paredaens, Jan] Univ Antwerp, B-2020 Antwerp, Belgium. [Van Gucht, Dirk] Indiana Univ, Bloomington, IN USA. [Wu, Yuqing] Pomona Coll, Claremont, CA 91711 USA. | Keywords: | trees; relation algebra; XML; XPath; bisimulation; instance expressivity;Trees; Relation algebra; XML; XPath; Bisimulation; Instance expressivity | Document URI: | http://hdl.handle.net/1942/20496 | ISSN: | 0022-0000 | e-ISSN: | 1090-2724 | DOI: | 10.1016/j.jcss.2015.10.002 | ISI #: | 000366240700005 | Rights: | © 2015 Elsevier Inc. All rights reserved. | Category: | A1 | Type: | Journal Contribution | Validations: | ecoom 2017 |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
fletcher 1.pdf Restricted Access | Published version | 923.12 kB | Adobe PDF | View/Open Request a copy |
raontrees (1).pdf | Non Peer-reviewed author version | 608.01 kB | Adobe PDF | View/Open |
SCOPUSTM
Citations
1
checked on Sep 3, 2020
WEB OF SCIENCETM
Citations
3
checked on Sep 27, 2024
Page view(s)
74
checked on Sep 7, 2022
Download(s)
118
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.