This paper provides several examples of how modal logic can be used in studying the XML document navigation language XPath. More specifically, we derive complete axiomatizations, computational complexity and expressive power results for XPath fragments from known results for corresponding logics. A secondary aim of the paper is to introduce XPath in a way that makes it accessible to an audience of modal logicians.

In this work, we study Hilbert-style proof systems for logics based on the data-aware language CoreDataXPath(↓) where the comparison relation between nodes is not necessarily an equivalence relation. We give a sound and complete axiomatization of the class of tree-like Kripke frames endowed with a general comparison relation between nodes. Modular extensions of this axiomatization are also discussed, including cases where the comparison relation is reflexive, symmetric, transitive and an equivalence. A notable highlight that we recover an axiomatization for CoreDataXPath(↓) (...) over any data-tree when the comparison is by ‘equal data’. Moreover, we prove that all these systems are decidable by leveraging the finite model property of their corresponding frame classes. (shrink)

In this work, we study Hilbert-style proof systems for logics based on the data-aware language CoreDataXPath(↓) where the comparison relation between nodes is not necessarily an equivalence relation. We give a sound and complete axiomatization of the class of tree-like Kripke frames endowed with a general comparison relation between nodes. Modular extensions of this axiomatization are also discussed, including cases where the comparison relation is reflexive, symmetric, transitive and an equivalence. A notable highlight that we recover an axiomatization for CoreDataXPath(↓) (...) over any data-tree when the comparison is by ‘equal data’. Moreover, we prove that all these systems are decidable by leveraging the finite model property of their corresponding frame classes. (shrink)

This paper provides several examples of how modal logic can be used in studying the XML document navigation language XPath. More specifically, we derive complete axiomatizations, computational complexity and expressive power results for XPath fragments from known results for corresponding logics. A secondary aim of the paper is to introduce XPath in a way that makes it accessible to an audience of modal logicians.

Version Control systems like CVS and Subversion have transformed collaboration workflows in software engineering, and made possible the globally distributed project teams we know from the Open Source Phenomenon. On the other hand, XML is coming of age as a basis for document formats, and even though XML as a text-based format is amenable to version control in principle, the fact that version control systems work on files makes difficult the integration of fragment access techniques like XPath, XQuery that (...) are currently revolutionizing XML workflows. In this paper we present the TNTBase system, an open-source versioned XML database obtained by integrating Berkeley DB XML into the Subversion Server. The.. (shrink)

Large databases of linguistic annotations are used for testing linguistic hypotheses and for training language processing models. These linguistic annotations are often syntactic or prosodic in nature, and have a hierarchical structure. Query languages are used to select particular structures of interest, or to project out large slices of a corpus for external analysis. Existing languages suffer from a variety of problems in the areas of expressiveness, efficiency, and naturalness for linguistic query. We describe the domain of linguistic trees and (...) discuss the expressive requirements for a query language. Then we present a language that can express a wide range of queries over these trees, and show that the language is first-order complete over trees. (shrink)