Global numerical constraints on trees

DOI10.2168/LMCS-10(2:10)2014MaRDI QIDQ4979448zbMATH OpenOpenAlexFDO

Authors Everardo Bárcenas, Jesús Lavalle

Publication date 23 June 2014

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

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

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)

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.

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

Cited in

(8)

• CTL^ with graded path modalities
• Mu-calculus satisfiability with arithmetic constraints
• Counting in trees
• Automata, Languages and Programming
• 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)