  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.
