Paper Info
Title
On Regular Paths with Counting and Data Tests.
Abstract
Regular path expressions represent the navigation core of the XPath query language for semi-structured data (XML), and it has been characterized as the First Order Logic with Two Variables (FO2). Data tests refers to (dis)equality comparisons on data tree models, which are unranked trees with two kinds of labels, propositions from a finite alphabet, and data values from a possibly infinite alphabet. Node occurrences on tree models can be constrained by counting/arithmetic constructors. In this paper, we identify an EXPTIME extension of regular paths with data tests and counting operators. This extension is characterized in terms of a closed under negation Presburger tree logic. As a consequence, the EXPTIME bound also applies for standard query reasoning (emptiness, containment and equivalence).
Year
DOI
Venue
2016
10.1016/j.entcs.2016.11.002
Electr. Notes Theor. Comput. Sci.
Keywords
Field
DocType
Modal Logics,XPath,Automated Reasoning,Data Trees,Counting
Discrete mathematics,Automated reasoning,Query language,EXPTIME,Computer science,Tree (data structure),Path expression,Theoretical computer science,Equivalence (measure theory),XPath,First-order logic
Journal
Volume
Issue
ISSN
328
C
1571-0661
Citations 
PageRank 
References 
0
0.34
0
Authors
3
Name
Order
Citations
PageRank
Everardo Bárcenas1239.15
Edgard Benítez-Guerrero2910.06
jesus lavalle3102.32