Query Reasoning on Trees with Types, Interleaving, and Counting

1 Introduction

XML is a key technology for describing and exchanging a wide variety of data on the Web. Analyses of XML documents with complex constructions such as queries and types has recently been studied [Genev`es et al., 2007; Calvanese et al., 2010]. XML documents can be seen as finite labelled trees, queries are expressed by regular paths (XPath), and XML types (XML Schema, DTDs, RelaxNG) are written in terms of regular tree types. The expressive power of regular queries corresponds to first order logic with two variables FO2 and regular types to monadic second order logic MSO. Modal logics recently became popular in the context of XML due to their high expressiveness and nice computational properties [Genev`es et al., 2007; Calvanese et al., 2010]. We present in this work an analysis framework, based on modal logic, for regular path queries and types equipped with counting and interleaving.

Motivations The XPath query language is used to select nodes in documents. The entire XPath language contains some constructs for counting and others for performing equality tests on values. However, it is well-known that the general combination of these features makes query reasoning undecidable.

In the present work, paths are expressed in terms of a modal tree logic equipped with converse and recursive navigation, graded modalities (counting), and nominals. This logic is known to be undecidable when interpreted over graphs [Bonatti et al., 2008]. We show that the logic is decidable in exponential time when interpreted over finite trees.

Regular tree types can be seen as the arborescent version of regular expressions over strings. A tree type specifies a set of trees (called valid XML documents). The interleave operator of XML schema allows one to describe a complex combination of ordered and unordered contents in unranked trees: e1&e2&. . .&en denotes the set of trees matching the type expressions e1 to en regardless of their order.

Contributions and Outline We first define an extension of the navigational core of the XPath language. The extension consists in adding constructs for restricting the cardinality of children paths. We also extend regular tree types with constructs for interleaving and counting. We proceed to develop a tree logic equipped with recursion, backward navigation, counting, and nominals. We also show that the logic can capture regular queries and types in a compact manner. We describe a satisfiability algorithm for the logic with exponential time complexity resulting in an efficient reasoning framework for regular paths and types with counting and interleaving.

2 Regular Path Queries

Navigation paths constitute the core of the XPath standard query language. In their simplest form, XPath queries look like directory navigation paths. For example, from a given context node, the expression ch :: a/ac :: b navigates to the children (ch) labelled with a, and from there it selects the ancestor (ac) nodes labelled with b. Qualifier (filter) expressions may also be used. For instance the expression ch :: a[ac :: b], selects the a children nodes with at least one ancestor node b.

We extend path queries with numerical constraints on children nodes. We support for instance expressions like ac :: a[ch::b ≤ 5]. This expression selects a ancestors with less than 5 children labelled b. Formally, the syntax of a path query P is defined as follows.

Relations between nodes are expressed with axes: ch stands for children, fs for following siblings, pn for parent, ps for previous sibling, ds for descendants, and ac for ancestors. In its basic form, a path P consists of a step a::p, which selects the nodes reachable by the axis a and labelled with p. Steps without restrictions on the labeling are written a. The label of the current node is simply written p. The composition of paths is written P1/P2. A qualified path P[Q] selects the nodes in the path P that satisfy the boolean condition over paths denoted by the qualifier Q. In addition, the number of children satisfying a qualifier can be bounded: ch :: p > k is true if and only if the number of p children is greater than the natural number k; ¬(ch :: p > k) holds iff the number of p children is less or equal than k. Numerical restrictions can also be imposed on children nodes regardless of their label: ch > k. Finally, /P denotes the nodes that are reachable by P starting from the root. Intersection and union of paths are interpreted as set intersection and union. P1 \ P2 denotes the nodes in P1 that are not in P2. We refer the reader to [Genev`es et al., 2007] for a formal semantics of XPath node-selection.

3 Regular Tree Types

Regular tree types describe structural constraints for unranked trees (XML documents). They encompass most of the features found in schemas such as DTDs, XML Schemas, and RelaxNGs except interleaving and counting. Interleaving is however a common construct in formal languages. The expression e1&e2 interleaves the words (or trees) denoted by e1 and e2 in every possible way. It is inductively defined:

where ϵ is denotes the empty word (or tree), pi are propositions and ei and e can be any expression. + stands for disjunction (alternation) and concatenation is expressed as usual.

The interleave operator is in general exponentially more succinct that its full expansion [Gelade, 2010]. For instance:

We extend regular tree types with operators for interleaving and counting on children nodes. Specifically, the syntax of extended regular tree types is defined as follows:

Disjunction-free types T ′ are as follows, where the valuation of x′ is a disjunction-free type T ′ .

We refer the reader to [Hosoya et al., 2005] for a denotational semantics of regular tree types. We use the following common syntactic sugar through the paper: T ? = ϵ + T , T ⋆ = let x.T in T x+ ϵ, and T + = T T ⋆ .

Notice that expressions like p [p1 [ϵ]⋆ &p2 [ϵ]] are not allowed. This is because the Kleene star is not supported at top level of interleaving. Notice however that recursion can be used if it is not occurring at top level: p [p1 [p3 [ϵ]⋆ ] &p2 [ϵ]].

In XML schemas, counting constructors are used to impose bounds on the number of occurrences of nodes matching regular expressions. The semantics is analog to counting on regular path queries. For instance, p0 [p1 [ϵ]>5 ] denotes trees whose root is labelled with p0 has at least 6 children leaves labelled with p1. Notice that the children are not required to be immediate siblings, in constrast with other forms of counting in formal languages [Gelade, 2010].

4 XML Logic

We now present a unified reasoning framework for regular path queries and tree types, as a modal tree logic equipped with recursion, backward navigation, counting, and nominals. We then show how to use the logic to efficiently encode regular queries and types with counting and interleaving.

There is a well known bijective encoding between unranked trees and binary trees: one edge is interpreted as the first child relation, and a second edge is used for the next sibling relation. We therefore consider binary trees as models for our logic, without loss of generality.

The syntax of logical formulas, in negation normal form, is defined as follows:

Formulas are interpreted as sets of tree nodes. We follow the traditional transition systems semantics of formulas in the Kripke style but interpreted over finite tree models. A Kripke tree K is a triple (N , R, L), where N is a finite set of nodes, R : N ×M ↦→ N is transition relation of nodes and modalities (M is the set of modalities) forming a tree structure, and L is a function that labels nodes with propositions. Informally, ⊤ denotes the full set of nodes, propositions p label nodes, and modalities m denote the transitions between nodes, i.e., shortdownarrow (first child), shortrightarrow (next sibling), shortuparrow (parent), and shortleftarrow (previous sibling). A formula 〈m〉φ denotes the nodes that can access at least one node through m such that φ holds. Conjunction and disjunction are interpreted as set intersection and union.

A fixpoint μ is interpreted as a least fixpoint and is used for finite recursion. The formula φ = p1 ∧μx.〈shortuparrow〉(p0 ∨x)∨〈shortleftarrow〉x denotes the p1 descendants of p0. We assume that variables cannot be free and that they can only occur under the scope of a modality or a graded operator. In order to prove correctness of our satisfiability algorithm, we disallow variables to occur under the scope of both a modality and its converse.

A graded formula φ〈k〉 denotes the set of nodes which have at least k + 1 children where φ holds. φ[k] stands for the nodes where φ holds in all but at most k children nodes. For example, p〈100〉 2 holds at nodes with at least 101 children p2.

Negation normal form of formulas can be obtained from usual DeMorgan's rules and ¬〈m〉φ = 〈m〉¬φ ∨ ¬〈m〉⊤, ¬μx.φ = μx.¬φ [x /¬x], ¬(φ〈k〉 ) = (¬φ)[k] , and ¬(φ[k] ) = (¬φ)〈k〉 . In the sequel, we thus implicitly consider ¬φ in negation normal form for any φ. We write φ=k instead of φ〈k-1〉 ∧ (¬φ)[k] for k > 0.

[Bonatti et al., 2008] presented a way to encode graded formulas into plain μ-calculus (without counting): p〈2〉 is equivalent to 〈shortrightarrow〉μx1.(p ∧ 〈shortrightarrow〉μx2.(p ∧ 〈shortrightarrow〉μx3.p ∨ 〈shortrightarrow〉x3) ∨ 〈shortrightarrow 〉x2)∨〈shortrightarrow〉x1. However, this encoding produces exponentially larger expressions. Since satisfiability of μ-calculus without graded modalities is already exponential time complete, such an encoding of graded modalities yields a doubly exponential time decision procedure.

A nominal can be easily expressed by a constant-size logical formula that explicitly enforces a proposition to occur exactly once, as noticed in [Calvanese et al., 2010].

4.1 Query Translation

We show how regular path queries with counting operators can be translated into logical formulas. First, notice that all axes in regular path queries can be expressed by formulas. The translation function F takes an axis and some context X as input and returns the corresponding logical formula:

Steps are thus translated as the following conjunction: F(a:: p,X) = F(a,X) ∧ p. For instance, given a context X, the query ac :: p is translated into the logic as the following formula: p ∧ 〈shortdownarrow〉μx.X ∨ 〈shortdownarrow〉x ∨ 〈shortrightarrow〉x.

For multi-step queries, the translation function is composed: F (P1/P2, X) = F (P2, F (P1, X)).

Qualified query paths are expressed by the following conjunction: F(P[Q],X) = F(P,X) ∧ F ′ (Q,⊤) where F ′ is defined below. Notice that the context is not duplicated in this formula. Boolean combinations of qualifiers are trivially translated as follows: F ′ (¬Q,X) = ¬F ′ (Q,X) and F ′ (Q1 ∨ Q2, X) = F ′ (Q1, X) ∨ F ′ (Q2, X).

Counting operators are translated as follows:

For instance, we translate ac :: p1[ch :: p2 > 5] for a given context X as: (p1 ∧ 〈shortdownarrow〉μx.X ∨ 〈shortdownarrow〉x ∨ 〈shortrightarrow〉x) ∧ p〈5〉 2 .

Paths occurring inside qualifiers cannot be translated in the same manner than paths occurring outside. Focus on the selected nodes remains outside the qualifiers:

where a = a, ch = pn, fs = ps and ds = ac. For instance, the query ch::p1[ch::p2] is translated, given a context X, as: (p1 ∧ μx.〈shortuparrow〉X ∨ 〈shortleftarrow〉x) ∧ 〈shortdownarrow〉μx.(p2 ∧ ⊤) ∨ 〈shortrightarrow〉x.

We now conclude the translation of queries: F(/P,X) = F (P, X ∧ ¬〈shortuparrow〉⊤ ∧ ¬〈shortleftarrow〉⊤), F (P1 ∩ P2, X) = F (P1, X) ∧ F(P2,X), F(P1 ∪ P2,X) = F(P1,X) ∨ F(P2,X) and F (P1 \ P2, X) = F (P1, X) ∧ ¬F (P2, X).

Theorem 4.1. Regular path queries with counting operators translate into logical formulas of linear size.

4.2 Type Translation

Regular tree types have the same expressive power than MSO and can be linearly translated (without counting and interleaving) into μ-calculus (see for instance [Genev`es et al., 2007]). We now show how graded modalities can be used to encode the counting and interleave operators. Given a linear translation of regular tree types without counting and interleaving operators F , we translate inductively the counting operator:

Graded formulas are now used to encode interleaving:

where k is the sum of the number of propositions of each Ti. For instance, p0 [p1 [ϵ]&p2 [ϵ]] is translated as p0 ∧ (φ ∧ @n1)=1∧(ψ∧@n2)=1∧⊤=2∧¬〈shortrightarrow〉⊤, where φ = p1∧¬〈shortdownarrow〉⊤ and ψ = p2 ∧ ¬〈shortdownarrow〉⊤. The number of occurrences of p1 and p2 is set to exactly one, and there is no restriction in the occurrence order of the labels.

A particular attention is paid to the occurrence order of labels in concatenations occurring at top level of the interleave operator. We translate these concatenations as follows:

For instance, p0 [p1 [ϵ]&(p2 [ϵ] p3 [ϵ])] is translated as p0 ∧ (φ∧@n1)=1 ∧(ξ ∧@n2)=1 ∧⊤=3 ∧¬〈shortrightarrow〉⊤, with φ as defined above, and ξ = p2 ∧ ¬〈shortdownarrow〉⊤ ∧ 〈shortrightarrow〉μx.(p3 ∧ ¬〈shortdownarrow〉⊤) ∨ 〈shortrightarrow〉x. The formula ξ enforces p3 to be a following sibling of p2.

Nominals are used to distinguish identical labels. For example, p0 [p1 [ϵ]&(p2 [ϵ] p1 [ϵ])] is translated as p0 ∧ (φ ∧ @n1)=1 ∧(ξ ′ ∧@n2)=1 ∧⊤=3 ∧¬〈shortrightarrow〉⊤, where ξ ′ = p2 ∧¬〈shortdownarrow 〉⊤ ∧ 〈shortrightarrow〉μx.(p1 ∧ ¬〈shortdownarrow〉⊤) ∨ 〈shortrightarrow〉x. As the label p1 occurs in both φ and ξ ′ , we distinguish nodes with the same label with a fresh nominal.

Theorem 4.2. Regular tree types with counting and interleaving translate into logical formulas whose sizes are at most polynomial.

Since the logic is closed under negation, we are able to formulate several typical query reasoning problems into the logic. For instance, consider two queries P1 and P2, and two types T1 and T2. If the formula F(P1, F(T1)) ∧ ¬F(P2, F(T2)) is unsatisfiable, then all nodes selected by P1 under type constraint T1 are also selected by P2 under T2. For solving such reasoning problems, we now present a satisfiability-testing algorithm for formulas of the logic.

5 Satisfiability

We introduce a satisfiability algorithm `a la Fischer-Ladner for the logic, in the style of [Genev`es et al., 2007; Demri and Lugiez, 2010]. This is done in two steps: we first define the nodes of tree models, then we show how the algorithm builds the candidate tree models. We also show that the algorithm is correct and that its complexity is exponential time.

5.1 Nodes and Trees

During the construction of candidate trees, we use counters of children nodes in order to test graded formulas. We assume that numbers occurring in graded formulas are coded in binary. We then define the counters in a binary form. A binary number is written as a boolean combination of atomic propositions. For instance, 1 is written p0 ∧ ¬p1 ∧ . . . ∧ ¬pn, the number 5 (101 in binary) is written p3 ∧p1 ∧¬p2 ∧. . .∧¬pn, for some bound n.

We define the following constant which is a bound for the counters. Given a formula φ, we define C = n(k + 1), where n is the number of subformulas ψ〈k′ 〉 occurring in φ, and k is the greatest number occurring in the subformulas ψ〈k′ 〉 .

Intuitively, the nodes of a given formula φ are defined as sets of subformulas of φ, such that a formula holds at a node iff such formula is contained in the node. In order to test graded formulas, we use counters to verify the number of children nodes. A bound for the sizes of the counters (number of children) in now introduced.

Theorem 5.1. If a formula φ is satisfiable, then there is a model of φ where each node has at most C children.

For the proof, we follow the construction of [Bonatti et al., 2008], where the bound is proven for possibly infinite models.

The Fischer-Ladner closure of a given formula is the set of its subformulas and their negation normal form, such that the fixpoints are expanded once, and a counter for each graded subformula is considered. Before defining the closure, consider the following relation for i = 1, 2:

For graded formulas, we also consider the fixpoint formulas that verify the existence of children nodes, and counters for each graded subformula:

where k′ = 0, . . . , C. ψk′ is a corresponding counter for each graded formula, that is, it is the number k′ coded in binary, as defined above with a set of fresh propositions.

For a given formula φ, the Fischer-Ladner closure FL(φ) is defined as FL(φ) = FL(φ)n, such that k is the smallest integer satisfying FL(φ)n+1 = FL(φ)n, where:

We are now ready to define the lean set, which contains the formulas forming the tree nodes. Consider a formula φ and a proposition σ not occurring in φ. Given that i = 1, . . . , C, we define the lean set of φ as follows:

We now show that the size of the lean is not significantly increased w.r.t. to the formula. The size of a formula is defined inductively in the standard way.

Lemma 5.1. Given a formula φ, the cardinality of lean(φ) is at most polynomial w.r.t. the size of φ.

A φ-node of a formula φ, written nφ , is defined as a subset of lean(φ), such that: at least one proposition (different than the ones used for counters) is present; at least one counter is present; when 〈m〉ψ occurs, also does 〈m〉⊤; and 〈shortuparrow〉⊤ and 〈shortleftarrow〉⊤ cannot occur simultaneously. N φ denotes the set of φ-nodes. In the sequel, we call a φ-node simply a node.

We define an entailment relation between nodes and formulas (in negation normal form) as follows:

A tree is inductively defined as: the empty set ∅; or a triple (n, X1, X2), where n is a node and X1 and X2 are trees. The root of a non-empty tree (n,X1,X2) is n.

The notion of entailment is extended to trees: a tree X entails a formula φ, written X ⊩ φ, iff there is a node n in X such that n ⊢ φ and there are no pending modalities, that is, formulas 〈shortuparrow〉ψ or 〈shortleftarrow〉ψ are not contained in the root of X. We write X ̸⊩ φ when X does not entail φ.

5.2 The Algorithm

The algorithm builds consistent candidate trees in a bottomup manner. At each step, it checks whether one of the newly built trees satisfies the formula. For a given formula φ, the algorithm is as follows:

return φ is satisfiable

end if

return φ is not satisfiable

Initially tested nodes are leaves. Given a set of nodes X, a node is a leaf n ∈ Leaves(X) iff n ∈ X, formulas 〈shortdownarrow〉ψ or 〈shortdownarrow〉ψ do not occur in n, and the counters are initialized, that is, for every ψk ∈ X we have that ψ0 ∈ n and n ⊢ ¬ψ, or ψ1 ∈ n and n ⊢ ψ.

At each step of the algorithm, if newly considered nodes do not satisfy the formula, then new candidate trees are built recursively by adding consistent parents to previously built trees. This process is achieved by the Update function. In order to define this function, we first define auxiliary notions.

Given a formula φ and two nodes n1 and n2, we say that the nodes are modally consistent for m ∈ {shortdownarrow,shortrightarrow}, written Δm(n1, n2) , if and only if, for all 〈m〉ψ and 〈m〉ψ in lean(φ), we have 〈m〉ψ ∈ n1 ⇔ n2 ⊢ ψ, and 〈m〉ψ ∈ n2 ⇔ n1 ⊢ ψ.

Given a formula φ, and two nodes n1 and n2, we define the counter consistency of the nodes as follows: #shortdownarrow(n1, n2) holds iff

• for all ψ〈k〉 ∈ lean(φ), we have that ψ〈k〉 ∈ n1 iff ψk′ ∈ n2 and k < k′ ; and
• for all ψ[k] ∈ lean(φ), we have that ψ[k] ∈ n1 iff ⊤k0 , ψk1 , (¬ψ)k2 ∈ n2, k0 = k1 + k2, and k2 ≤ k.

#shortrightarrow(n1, n2) holds iff

• for all ψk ∈ lean(φ), we have that ψk ∈ n1 and n1 ⊢ ψ iff ψk-1 ∈ n2, or
• ψk ∈ n1 and n1 ⊢ ¬ψ iff ψk ∈ n2.

The update function is in charge of checking that the newly formed triples are modally consistent, and that the counters are also consistent. Given the set X of triples and the set Y of nodes, we define Update(X, Y ) as the pair (X′ , Y ′ ): X′ is a set of triples (n,X1,X2) and Y ′ is the set containing the nodes in Y except n, such that X1,X2 ∈ X, Δshortdownarrow(n, n1), Δshortrightarrow(n, n2), and #shortdownarrow(n, n1), #shortrightarrow(n, n2).

5.3 Correctness and Complexity

Termination of the algorithm is straightforward since the set of nodes is finite and the update function is monotone. We now show that the algorithm is sound and complete.

Theorem 5.2 (Soundness). If the algorithm returns that φ is satisfiable, then there is a Kripke tree structure satisfying φ.

Proof sketch. Assume the algorithm builds a triple X such that X ⊩ φ, then we build a Kripke tree structure K = (N , R, L) from X, such that K satisfies φ.

N is the set of nodes of X. For every triple in (n,X1,X2) in X, we have that R(n, shortdownarrow) = n1 and R(n, shortrightarrow) = n2, where ni is the root of the non empty triples Xi (i = 1, 2). For every p ∈ lean(φ), if p ∈ n, then L(n) = p.

We now show K satisfies φ by induction on the structure of φ. All cases are immediate by induction and by relying on the fact that fixpoints have an equivalent finite unfolding (μx.ψ ≡ ψ [μx.ψ /x ]).

Theorem 5.3 (Completeness). If a formula φ is satisfiable, then the algorithm returns that φ is satisfiable.

Proof sketch. We first build a triple X from the smallest satisfying Kripke structure K, such that X ⊩ φ. We then show the algorithm can build X.

X is defined homomorphic to K, such that its nodes contain the lean formulas satisfied by the corresponding nodes of K. More precisely, for R(n, shortdownarrow) = n1 and R(n,shortrightarrow) = n2, there is a triple in X such that (n,X1,X2) and ni is the root of Xi. For every node n in K, we have that ψ ∈ nφ for every ψ ∈ lean(φ), such that nφ in X is the corresponding node of n in K. We proceed to add the counters to each node: for every non empty sequence of sibling nodes n1, . . . , nk in K, such that ni+1 is the following sibling of ni, and for every counter ψk ∈ lean(φ), if ψ is satisfied at k nodes of the sequence, then ψk ∈ nφ1 , where nφ1 is the corresponding node of ni.

It is now shown that X entails φ. We proceed by induction on the structure of φ. Most cases are immediate by the construction of X and by induction. For the fixpoint case μx.ψ, we test the equivalent formula ψ [μx.ψ /x ] and proceed again by structural induction. This is also immediate since variables, and then unfolded fixpoints, can only occur under the scope of a modality or a graded formula.

We now show the algorithm builds X by induction on the height of K. The base case is when K is a leaf, and it is immediate. For the induction step, first notice that the transition relation R is consistent with Δm. We know by induction that the left and right subtrees of X have been already produced by the algorithm. The root of X is still available in Y for the algorithm. This is because counters distinguish identical nodes, and we have a consistent bound for the counters (Theorem 5.1). We then conclude X is built by the algorithm.

Theorem 5.4 (Complexity of satisfiability). Satisfiability for the logic is EXPTIME-hard.

Proof sketch. First recall the cardinality of the lean is at most polynomial w.r.t. to the formula size (Lemma 5.1). We then show the algorithm is exponential w.r.t. the lean size.

The cardinality of N φ is exponential w.r.t. the lean size. Then the number of steps of the algorithm is bounded by 2m, where m is the lean size. The cost of Leaves(N φ ) relies on a traversal on N φ , and hence it is also exponential. Computing each relation ⊩ and ̸⊩ costs at most an exponential, since one traversal of the nodes of X is performed and the cost of computing the relation ⊢ is linear w.r.t. to the node size. The cost of computing the Update function consists in: the searches required to form triples (n, X1, X2), and the functions Δ and #. The searches are done on Y and X, each of them having exponential size. The cost of Δ and # relies on the one of the relation ⊢, which is linear. Hence, each step of the iteration costs at most an exponential time. Other set operations on X and Y can be done in linear time. Therefore, the total complexity is in EXPTIME. In addition, since the logic can encode all finite tree automata and is closed under negation, satisfiability for the logic is hard for EXPTIME.

Corollary 5.1. Reasoning (entailment, containment, equivalence) on regular path queries and regular tree types, with counting and interleaving, is decidable in EXPTIME.

6 RelatedWork

Recent research has focused on expressing counting on children nodes only [Dal-Zilio et al., 2004; Seidl et al., 2004; Demri and Lugiez, 2010]. In these works, modal tree logics are equipped with Presburger arithmetic in order to express cardinality constraints. However, all these approaches do not support converse navigation and cannot fully support the navigation core of XPath. The approach presented here allows the multi-directional and recursive navigation required for the full navigation core of XPath. In addition, we also support counting constraints on children w.r.t. a constant.

The sheaves automata were introduced in [Dal-Zilio and Lugiez, 2003] to study the relationship of counting and interleaving in order to solve the entailment (satisfiability) problem of tree types. For that purpose, Presburger arithmetic formulas are used to model the interleave operator. However, the use of type constructs at top level of the interleave operator is not allowed. The logic introduced here has a less restrictive use of interleaving on regular tree types, since concatenation can be used at top level. [Colazzo et al., 2009] identified fragments of tree types supporting interleaving with linear time complexity for containment. This came at the cost of drastic restrictions on the occurrence of identical labels. The approach presented here can support counting constructs for regular tree types in addition to interleaving.

Finally, from a general perspective, we recall that whenever adding a useful shorthand increasing the succinctness of a given logic, one must consider the impact to the complexity of the decision procedure of the original logic itself, but also, as importantly, consider the complexity of the translation of the added feature in terms of the original logic. The term "combined complexity" encompasses the two. We are notably interested in the combined complexity of deciding a μ-calculus for finite trees with backward modalities, nominals, and counting operators.

Similar logics but without a counting operator were considered in [Vardi, 1998] and [Calvanese et al., 2009]. A μcalculus with inverse plus counting operators is considered in [Barcel´o and Libkin, 2005]. However, a na¨ıve translation of this logic in terms of μ-calculus with inverse without counting operators (such as the one of [Vardi, 1998]) would be exponential. The goal of the present paper is precisely to show how this blowup can be avoided. Furthermore, the best known complexity of the decision procedure for the logic in [Vardi, 1998] is 2O(n4 ∗log(n)) [Gr¨adel et al., 2002] whereas our decision procedure operates in 2O(n) w.r.t. formula size n. In addition, for translating the interleave operator, we use nominals, which are not supported in [Vardi, 1998]. We recall that the μ-calculus of [Vardi, 1998] extended with counting, backward modalities, and nominals is undecidable (see [Bonatti et al., 2008]). The reason why the combination of these features remains decidable in our case is that we restrict ourselves to finite trees.

7 Conclusion

We introduced a modal tree logic equipped with recursive and converse navigation, and counting operators on children nodes. We also presented a satisfiability-testing algorithm for the logic with exponential time complexity. The logic captures regular tree types and query languages with counting restrictions on children nodes. An extension of regular tree languages with the interleave operator whose operands are disjunction-free can also be described by the logic. The logic is closed under negation and can be used to decide typical reasoning problems on XML trees in exponential time: entailment, containment, and equivalence.