On Regular Paths with Counting and Data Tests | Zendy

Everardo Bárcenas | Zendy; Edgard Benítez–Guerrero | Zendy; Jesús Lavalle | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

On Regular Paths with Counting and Data Tests

Author(s) -

Everardo Bárcenas,

Edgard Benítez–Guerrero,

Jesús Lavalle

Publication year - 2016

Publication title -

electronic notes in theoretical computer science

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.242

H-Index - 60

ISSN - 1571-0661

DOI - 10.1016/j.entcs.2016.11.002

Subject(s) - xpath , mathematics , path expression , computer science , decidability , exptime , negation , extension (predicate logic) , theoretical computer science , path (computing) , query language , discrete mathematics , xml , algorithm , programming language , computational complexity theory , database , pspace , xml validation , operating system

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).

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research