Bárcenas, Everardo and Lavalle, Jesús - Global Numerical Constraints on Trees

lmcs:985 - Logical Methods in Computer Science, June 16, 2014, Volume 10, Issue 2
Global Numerical Constraints on Trees

Authors: Bárcenas, Everardo and Lavalle, Jesús

We introduce a logical foundation to reason on tree structures with constraints on the number of node occurrences. Related formalisms are limited to express occurrence constraints on particular tree regions, as for instance the children of a given node. By contrast, the logic introduced in the present work can concisely express numerical bounds on any region, descendants or ancestors for instance. We prove that the logic is decidable in single exponential time even if the numerical constraints are in binary form. We also illustrate the usage of the logic in the description of numerical constraints on multi-directional path queries on XML documents. Furthermore, numerical restrictions on regular languages (XML schemas) can also be concisely described by the logic. This implies a characterization of decidable counting extensions of XPath queries and XML schemas. Moreover, as the logic is closed under negation, it can thus be used as an optimal reasoning framework for testing emptiness, containment and equivalence.


Source : oai:arXiv.org:1405.1295
DOI : 10.2168/LMCS-10(2:10)2014
Volume: Volume 10, Issue 2
Published on: June 16, 2014
Submitted on: July 1, 2013
Keywords: Computer Science - Logic in Computer Science


Share

Consultation statistics

This page has been seen 76 times.
This article's PDF has been downloaded 51 times.