Global numerical constraints on trees

DOI10.2168/LMCS-10(2:10)2014zbMATH Open1314.68113arXiv1405.1295OpenAlexW1998912565MaRDI QIDQ4979448FDOQ4979448

Authors: Everardo Bárcenas, Jesús Lavalle 

Publication date: 23 June 2014

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1405.1295

Recommendations

• Numerical Constraints for XML
• Counting in trees
• Automata, Languages and Programming
• Numerical constraints on XML data
• Two-variable logic on data trees and XML reasoning

zbMATH Keywords

satisfiabilityXML schemascounting constraintsquery reasoning

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Database theory (68P15) Decidability of theories and sets of sentences (03B25) Logic in computer science (03B70)

Cited In (8)

• CTL\(^\ast\) with graded path modalities
• Mu-calculus satisfiability with arithmetic constraints
• Automata, Languages and Programming
• Counting in trees
• On regular paths with counting and data tests
• Numerical constraints on XML data
• Uniform tree approximation by global optimization techniques
• Finite and Rational Tree Constraints

This page was built for publication: Global numerical constraints on trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4979448)