On the Count of Trees

Details On the Count of Trees On the Count of Trees

2010-08-30

arxiv.org/abs/1008.5073v1

Computer Science

Databases

Scientific paper

Regular tree grammars and regular path expressions constitute core constructs widely used in programming languages and type systems. Nevertheless, there has been little research so far on frameworks for reasoning about path expressions where node cardinality constraints occur along a path in a tree. We present a logic capable of expressing deep counting along paths which may include arbitrary recursive forward and backward navigation. The counting extensions can be seen as a generalization of graded modalities that count immediate successor nodes. While the combination of graded modalities, nominals, and inverse modalities yields undecidable logics over graphs, we show that these features can be combined in a decidable tree logic whose main features can be decided in exponential time. Our logic being closed under negation, it may be used to decide typical problems on XPath queries such as satisfiability, type checking with relation to regular types, containment, or equivalence.

Affiliated with

Also associated with

No associations

Rating

On the Count of Trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Count of Trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Count of Trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-400865