Gabriele Puppis
email: gabriele.puppis@cs.ox.ac.uk

Cristian Riveros
email: cristian.riveros@cs.ox.ac.uk

Staworko Sławek
email: slawomir.staworko@inria.fr

Mostrare

Bounded repairability for regular tree languages

Keywords: H.2.m [Information Systems]: Database Management-Repair XML, edit distance, repair, curry encoding

.

INTRODUCTION

When a database does not satisfy integrity constraints, a natural operation to perform is to repair it -modify it minimally so that the constraints are satisfied. This approach to data integrity has been investigated in the relational case for a variety of integrity constraints -beginning with classical functional and inclusion dependencies [START_REF] Arenas | Consistent query answers in inconsistent databases[END_REF], and continuing to wider classes such as tuple generating dependencies [START_REF] Foto | Repair checking in inconsistent databases: algorithms and complexity[END_REF]. A number of different modification operators have been considered in the relational case, including inserting, changing, and deleting tuples. In addition to finding repairs of documents, much of this line of research deals with querying inconsistent documents via their repairs.

For XML documents, repair has been studied less extensively. In [START_REF] Flesca | Querying and repairing inconsistent XML data[END_REF], repair is considered for an extension of classical relational constraints such as inclusion dependencies, while in [START_REF] Staworko | Validity-sensitive querying of XML databases[END_REF] repairs of a document with respect to an XML schema are studied, with an emphasis on consistent querying over such documents. The notion of modification of an XML document is based on standard edit operations on the underlying tree structure, e.g., relabeling a node, deleting a node, and inserting a new node. Quite a different line of work deals with editing of schemas, rather than documents. For example, [START_REF] Fan | Information preserving XML schema embedding[END_REF] deals with a similarity measure on schemas given by considering embeddings that preserve the DTD structure. The notion of similarity thus depends on the syntactic presentation of the schema, not the language of documents that it defines.

In this work we consider the question of the edit distance between XML schemas as well. Like [START_REF] Fan | Information preserving XML schema embedding[END_REF], we provide a method to notice similarity of schemas that may differ a bit, and like [START_REF] Staworko | Validity-sensitive querying of XML databases[END_REF] we will make use of edit distance on trees. Our results give a means of detecting whether schema R (for restriction) can be edited into schema T (for target). Unlike [START_REF] Fan | Information preserving XML schema embedding[END_REF] we do this on a purely semantic basis -R is repairable into T exactly when the documents satisfying R can be repaired into documents satisfying T . More formally, we consider a schema R to be "almost included" in schema T if every document t in R can be repaired to a document t ′ in T using a finite, uniformly bounded number of edits. In this case, we say that R is bounded repairable into T . The problem is motivated not only by schema matching, but also from data cleaning: we have some integrity property that we want to assure on documents (the target), and we have some property that we can assume the documents already have (the restriction). Bounded repairability states that we can clean the inputs to ensure conformance to our target constraint with a bounded amount of distortion of the input data.

The following examples show that it is not at all obvious whether one schema is bounded repairable into another. The left-hand side schema R defines the language of all trees of the form r(d(a, . . . , a, b, . . . , b), c, . . . , c), while the righthand side schema T defines the language of all trees of the form r(a, . . . , a, e(b, . . . , b, c, . . . , c)). We claim that R is repairable into T with a uniformly bounded number of edit operations. Indeed, given a tree r(d(a, . . . , a, b, . . . , b), c, . . . , c) satisfying R, one can first delete the node labeled by d, obtaining the tree r(a, . . . , a, b, . . . , b, c, . . . , c), and then insert a new e-labeled node under the root, which adopts as children all the nodes labeled by b or c; this results in a tree r(a, . . . , a, e(b, . . . , b, c, . . . , c)) that satisfies T .

Example 2. Consider the following DTDs:

R ′ : r → a a → b* b → EMPTY T ′ : r → a a → b*, c b → EMPTY c → EMPTY
It is easy to see that R ′ is bounded repairable into T ′ : any tree r(a(b, . . . , b)) in R ′ can be modified into a tree in T ′ by inserting a new c-labeled node as a right-sibling of the nodes labeled by b. However, if we replace in both DTDs R ′ and T ′ the rule r → a with the rule r → a * , we obtain a new pair of languages R ′′ and T ′′ such that R ′′ is not bounded repairable into T ′′ . This example suggests that bounded repairability depends on some interplay between the rules of DTDs and, more generally, between the specifications of the labellings of the nodes at different levels of the trees.

We will deal with the notion of bounded repairability for schemas that are more general than DTDs, e.g., schemas that are given by regular tree languages [START_REF] Schwentick | Automata for XML -a survey[END_REF], and which capture the structural part of the W3C's XML schema [START_REF] Fallside | XML Schema Part 0: Primer Second Edition[END_REF].

We will formalize the edit distance between regular tree languages, and from this define the bounded repair problem, that is, the problem of deciding bounded repairability between two given tree languages R and T . Our main result is that it is decidable whether or not R can be repaired into T with a uniformly bounded number of edits.

For regular languages of words, the bounded repair problem was resolved in [START_REF] Benedikt | Regular repair of specifications[END_REF]: there it was shown that the problem is coNP-complete when the languages are represented by deterministic finite state automata, and a characterization of bounded repairability was given using a coverability relation between chains of connected components of the automata.

In the case of tree languages, the problem turns out to be much more complex, both in terms of complexity and in terms of proof techniques that are needed to resolve it. We will provide a characterization of bounded repairability that exploits a suitable notion of component of a stepwise tree automaton [START_REF] Carme | Querying unranked trees with Stepwise Tree Automata[END_REF], i.e., a form of automaton that turns out to be particularly convenient for analyzing repairs. An additional complication for the tree case is that we need to consider structures of connected components of stepwise tree automata that take the form of trees, rather than chains.

Our characterization of the bounded repairability of R into T requires that every component structure of R can be "covered" by a component structure of T . The notion of covering is subtle, and the proof that it captures bounded repairability requires lifting the notion of edit from the level of the individual trees to the level of the component trees associated with the automata for R and T .

Once we have our characterization, we can apply it to get decidability of the bounded repair problem, and with some additional optimization we can give complexity bounds. We can also apply the characterization theorems to show that bounded repairability is much simpler to check for special classes of schemas. For example, we show that it is much less complex for deterministic DTDs when the alphabet is fixed, and much less complex when the restriction language R is trivial (i.e., the class of all trees).

Organization. In Section 2 we give some background on tree languages and edit operations. In Section 3 we give the formal statement of our main result, that is, a characterization of exactly which pairs of schemas are bounded repairable. The proof takes up Section 4. Section 5 uses the characterization theorem to get complexity bounds, while Section 6 gives a different characterization of bounded repairability for the case where the restriction language is trivial, and derives the corresponding complexity bounds. Section 7 gives conclusions and related work.

BACKGROUND

Curried trees and contexts

Throughout this paper we often use the curry encoding to represent unranked trees. The curry encoding [START_REF] Carme | Querying unranked trees with Stepwise Tree Automata[END_REF][START_REF] Martens | On the minimization of XML schemas and tree automata for unranked trees[END_REF], also known as the extension encoding, represents an unranked tree labeled with elements of Σ as a binary tree whose inner nodes are labeled with a distinguished symbol @ and leaves with elements of Σ. The encoding, denoted ext, is defined as follows (with a ∈ Σ):

ext(a) = a,
ext(a(t1, . . . , tn)) = @(ext(a(t1, . . . , tn-1), ext(tn))).

To simplify the notations, we write the symbol @ as an infix, left-associative operator. Figure 1 illustrates the encoding of an unranked tree. The inverse ext -1 of the encoding is defined by providing the symbol @ with the semantics of the extension operator on unranked tree and by evaluating the expression in a bottom-up fashion, i.e., ext -1 (a) = a and ext -1 (a@t1@ . . . @tn) = a(ext -1 (t1), . . . , ext -1 (tn)). For a finite set of labels Σ, we denote by T Σ the set of all curried trees over Σ.

We make an important observation that the root node of an unranked tree corresponds to the leftmost leaf in the corresponding curried tree. Other remarks follow [START_REF] Carme | Querying unranked trees with Stepwise Tree Automata[END_REF][START_REF] Martens | On the minimization of XML schemas and tree automata for unranked trees[END_REF]. We point out that ext is a one-to-one mapping between the set of unranked trees and the set of curried trees. We also note that there is a one-to-one correspondence between the nodes of an unranked tree and the leaves of the curried encoding. Moreover, the yield of a curried tree, i.e., the sequence of leaves taken from left to right, corresponds to the standard left-to-right pre-order traversal of the unranked tree. Another observation follows from the semantics of the extension operator: the inner nodes of a curried tree, labeled with @, correspond to the edges of the unranked tree. As usual, we use sequences of natural numbers to identify unambiguously the nodes in a tree: ε is the root node and x⋅i is the i-th child of node x. We denote by nodes(t) the set of all nodes in the tree t. For a tree t and a node x ∈ nodes(t), we denote by t(x) the label of the node x in t. We also introduce the partial orders ≼ post t and ≼ anc t on the nodes of a tree t; these two partial orders are induced by the standard post-order and ancestor relation of t, respectively.

@ @ r @ a a @ @ @ @ d @ b @ a @ a
We fix a special label • not in Σ to be used as a placeholder in contexts. Formally, a (curried ) context over Σ is an element of T Σ∪{•} with • occurring exactly once in a leaf. By C Σ we denote the set of all contexts over Σ. The empty context is the context • having exactly one node. For a context C and a tree t we denote by C ○ t the tree obtained from the substitution of • by t in C. Similarly, the composition C1 ○ C2 of two contexts C1 and C2 is obtained from the substitution of the placeholder in C1 by C2. (this results again in a context in C Σ ).

Stepwise tree automata

We use stepwise tree automata [START_REF] Carme | Querying unranked trees with Stepwise Tree Automata[END_REF][START_REF] Martens | On the minimization of XML schemas and tree automata for unranked trees[END_REF] to specify regular tree languages. These are essentially bottom-up tree automata running over the curry encodings of trees. Formally, a stepwise automaton is a tuple A = (Σ, Q, δ0, δ, F ), where: 1.

Σ is a finite set of labels, 2.

Q is a finite set of states, 3.

δ0 ∶ Σ → 2 Q is an assignment of initial states to labels, 4. δ ∶ Q × Q → 2 Q is a transition function, 5.
F ⊆ Q is a set of final states. We say that A is deterministic if δ0 (resp., δ) can be described as a partial function from Σ (resp., Q × Q) to Q. It is often convenient to represent δ0 and δ as a set of rules. For instance, we write a → q to indicate that q ∈ δ0(a) and q1@q2 → q to indicate that q ∈ δ(q1, q2).

A run of a stepwise automaton

A = (Σ, Q, δ0, δ, F ) on a tree t ∈ T Σ is a function ρ ∶ nodes(t) → Q such that ❼ for every leaf node x, ρ(x) ∈ δ0(t(x)), ❼
for every inner node x, ρ(x) ∈ δ(ρ(x ⋅ 1), ρ(n ⋅ 2)). A run ρ is accepting if ρ(ε) ∈ F . The language recognized by A, denoted L (A), is the set of all trees t ∈ T Σ on which A has an accepting run.

Example 3. As a running example, consider the two DTDs:

@ @ r @ a a @ @ @ @ d @ b @ a @
@ @ @ @ r @ @ d @ a @ a b @ a @ a @ a b c c c q r 1 q r 1 q r 1 q r 1 q r 0 q d 2 q d 1 q d 0 q a 1 q a 0 q a 1 q a 0 q b 0 q a 1 q a 0 q a 1 q a 0 q a 1 q a 0 q b 0 q c 0 q c 0 q c 0 Figure 2: Runs of two automata R and T . D: r → a, d a → a EMPTY d → b, c* b → a c → EMPTY D ′ : r → d, c* d → a, a a → a b b → EMPTY c → EMPTY
The following two stepwise automata capture (modulo the curry encoding) the languages defined by the previous DTDs (the underlined states are final and any rule using q a ? translates to two rules using q a 0 and q a 1 ):

R ∶ r → p r 0 a → p a 0 d → p d 0 b → p b 0 c → q c 0 p r 0 @p a ? → p r 1 p r 1 @p d 1 → p r 2 p a 0 @p a ? → p a 1 p d 0 @p b 1 → p d 1 p d 1 @p c 0 → p d 1 p b 0 @p a ? → p b 1 T ∶ r → q r 0 d → q d 0 a → q a 0 b → q b 0 c → q c 0 q r 0 @q d 2 → q r 1 q r 1 @q c 0 → q r 1 q d 0 @q a 1 → q d 1 q d 1 @q a 1 → q d 2 q a 0 @q a 1 → q a 1 q a 0 @q b 0 → q a 1
Figure 2 presents the (accepting) runs of the automata R and T on the curry encodings of some trees t and t ′ , respectively.

Stepwise automata capture exactly the class of regular (unranked) tree languages [START_REF] Carme | Querying unranked trees with Stepwise Tree Automata[END_REF] and they are more succinct than many other classes of tree automata [START_REF] Martens | On the minimization of XML schemas and tree automata for unranked trees[END_REF]. Other models that capture the same class of languages, such as unranked tree automata [START_REF] Schwentick | Automata for XML -a survey[END_REF] are more frequently used. Since unranked tree automata can be converted into stepwise tree automata in polynomial time, algorithms for analyzing stepwise automata provide the same complexity bounds for unranked tree automata -all of our theorems will apply to unranked tree automata as well as stepwise tree automata. The main advantage of using stepwise automata in our proofs is due to their ability of capturing the cyclic behavior of a regular tree language, defined via a suitable notion of strongly connected component (see Section 3 for more details).

In the sequel, we will work with trimmed automata only, namely, we assume that every state of an automaton appears in some accepting run (this implies that all states are both accessible and co-accessible). Every automaton can be made trimmed in linear time. As is usual for word automata, we extend the transition function δ of a stepwise automaton to trees in T Σ and to contexts in C Σ . Precisely, we define the function δ * ∶ T Σ → 2 Q such that q ∈ δ * (t) iff there exists a run ρ of A on t and ρ(ε) = q. Similarly, we define the function

δ * • ∶ Q × C Σ → 2 Q such that q ′ ∈ δ * • (q, C) iff there exists a run ρ of Aq = (Σ ∪ {•}, Q, δ0 ∪ {(•, q)}, δ, Q) on C and ρ(ε) = q ′ (
intuitively, we simulate some computation of A on C under the assumption that the placeholder is assigned state q). By an abuse of notation, we will denote δ * and δ *

• simply by δ.

Edit distance and bounded repairability

We briefly recall the definitions of some standard edit operations on unranked trees. The first operation, called deletion, consists of removing a distinguished (non-root) node x from a tree t and promoting its subtrees as children of its parent.

The second operation, called insertion, consists of adding a new node x in an unranked tree t, with a possible adoption of a list of subsequent children from the parent of x. Figure 3 gives an example of these two operations. These are the standard edit-operations that are used to define the edit-distance between trees [START_REF] Bille | A survey on tree edit distance and related problems[END_REF]. Note that the operation of relabeling a node in an unranked tree, which is sometimes used as a standard edit operation, is subsumed by the previous two operations.

We study the bounded repair problem for regular tree languages, which consists of deciding, given two regular tree languages R and T , whether one can transform any tree t ∈ R into a tree t ′ ∈ T using a finite, uniformly bounded number of edits. Formally, given two unranked trees t and t ′ , we denote by dist(t, t ′ ) the minimum number of edits that are needed for transforming t into t ′ . Given two regular tree languages R and T , we then define

dist(R, T ) = max t∈R min t ′ ∈T dist(t, t ′ )
to be the worst-case cost of repairing R into T . If the cost dist(R, T ) is finite, then we say that R is bounded repairable into T and we write R ↪ BR T for short.

Note that the bounded repairability relation ↪ BR satisfies some key properties, which will be used later on:

❼ Subset-subsumption, i.e., R ⊆ T implies R ↪ BR T . ❼ Transitivity, i.e., R ↪ BR T ↪ BR S implies R ↪ BR S. ❼ Union-compatibility, i.e., R ↪ BR T and R ′ ↪ BR T ′ imply R ∪ R ′ ↪ BR T ∪ T ′ .

MAIN CHARACTERIZATION

In this section we give an effective characterization of the bounded repairability relation between regular tree languages. Similarly to the string case [START_REF] Benedikt | Regular repair of specifications[END_REF], this characterization is based on the notion of strongly connected component of the transition graph of a stepwise automaton. In the string case, a suitable coverability relation between chains of components is used to characterize bounded repairability. Because here we work with trees, we need to generalize the notion of coverability to a relation over the so-called synopsis trees, i.e., full binary trees with nodes labeled by strongly connected components.

G R ∶ p r 0 p r 1 p r 2 p d 0 p d 1 p b 0 p b 1 p c 0 p a 0 p a 1 G T ∶ q r 0 q r 1 q d 0 q d 1 q d 2 q c 0 q a 0 q a 1 q b 0

Components of stepwise automata

Given a stepwise automaton

A = (Σ, Q, δ0, δ, F ), the transi- tion graph of A is the graph G A = (Q, E h ∪ Ev)
, where

E h = (q1, q) ∈ Q × Q ∃q2. q ∈ δ(q1, q2) , Ev = (q2, q) ∈ Q × Q ∃q1. q ∈ δ(q1, q2) .
We call the edges in Ev (resp., E h ) vertical (resp., horizontal ). Note that an edge may be both vertical and horizontal.

As an example, Figure 4 depicts the transition graphs of the automata R and T of Example 3 (dashed arrows represent horizontal edges, solid arrows represent vertical edges).

Recall that a set X of nodes of a graph G = (V, E) is a strongly connected component (or simply a component) iff X is maximal such that for every two x, y ∈ X, there is a path from x to y visiting nodes in X only. By SCC(A) we denote the set of all strongly connected components in the transition graph of A. We associate with each component X ∈ SCC(A) the language L (A X) of contexts that are realizable within X:

L (A X) = C ∈ C Σ ∃p, q ∈ X. q ∈ δ(p, C) .
Below, we identify particular types of components in the transition graph of an automaton. We say that a curried context C is horizontal if its placeholder • appears at the leftmost leaf (possibly at the root, if the context is a singleton). Essentially, a horizontal context C represents a hedge, i.e., a sequence of unranked trees that are encoded by the sub-trees below the leftmost branch of C. Concatenations of hedges thus correspond to compositions of horizontal contexts. For instance, given two horizontal contexts C and C ′ , C ○ C ′ is a horizontal context that represents the concatenation of the two hedges represented by C and C ′ , respectively. 1 } and {q r 1 } are non-trivial horizontal, since they both realize the contexts •, •@c, (•@c)@c, . . . The components {p a 1 } and {q a 1 } are non-horizontal, since they both realize the contexts •, a@•, a@(a@•), . . .

A component X ∈ SCC(A) is horizontal iff it realizes hori- zontal contexts only, namely, for every C ∈ L (A X), C is horizontal. Notice that an horizontal component of A can τ ∶ {p r 2 } {p r 1 } {p r 0 } {p a 1 } {p a 0 } {p a 0 } {p d 1 } {p d 0 } {p b 1 } {p b 0 } {p a 1 } {p a 0 } {p a 0 } σ ∶ {q r 1 } {q r 1 } {q r 0 } {q d 2 } {q d 1 } {q d 0 } {q a 1 } {q a 0 } {q b 0 } {q a 1 } {q a 0 } {q b 0 } {q c 0 }

Synopsis trees

We now introduce a suitable structure that eases the characterization of bounded repairability, namely, the synopsis tree. Formally, a synopsis tree of an automaton A is a full binary tree whose nodes are labeled with elements of SCC(A). The semantics ⟦τ ⟧ A of a synopsis tree τ of A is the language of curried trees recursively defined as follows: Next, we identify a family of synopsis trees that captures "closely enough" the language recognized by an automaton.

⟦X⟧ A = C ○ a C ∈ L (A X), a ∈ Σ ⟦X(τ1, τ2)⟧ A = C ○ (t1@t2) C ∈ L (A X), t1 ∈ ⟦τ1⟧ A , t2 ∈ ⟦τ2⟧ A with X ∈ SCC(A).
Definition 1. A primitive synopsis tree of an automaton R = (Σ, Q, δ0, δ, F ) is a synopsis tree τ of R such that: 1.
τ respects the transition function of R, i.e., for all nodes x, x ⋅ 1, and x ⋅ 2 in τ , there exist some states q ∈ τ (x), q1 ∈ τ (x ⋅ 1), and q2 ∈ τ (x ⋅ 2) such that q ∈ δ(q1, q2);

2. every internal node of τ has label different from the labels of its children, i.e., for all nodes x, x ⋅ 1, and

x ⋅ 2 in τ , τ (x ⋅ 1) ≠ τ (x) ≠ τ (x ⋅ 2).
PST(R) denotes the set of all primitive synopsis trees of A.

The tree τ depicted in Figure 5 is a primitive synopsis tree.

In particular, this tree respects the transitions of the run of the automaton R on the left-hand side of Figure 2. The idea underlying the notion of primitive synopsis tree is to capture the "cyclic behavior" of the components of the restriction automaton. This cyclic behavior has to be taken into account in the characterization of bounded repairability because it could generate arbitrary large fragments of trees that cannot be edited with uniformly bounded cost. Moreover, the use of primitive synopsis trees as a representation of the restriction language L (R) is sound because the set of primitively synopsis trees contains (via the previously defined semantics of synopsis tree) the language L (R):

@ @ r @ a a @ @ @ @ d @ b @ a @
Lemma 1. L (R) ⊆ ⋃ τ ∈PST(R) ⟦τ ⟧ R for any stepwise au- tomaton R.
We illustrate the proof of this lemma on the tree t from Figure 1 and the automaton R from Example 3. For this we consider the accepting run of R of Figure 2 and we use it to decompose t into a binary tree of contexts, where each context is realized by some SCC of R. We present this decomposition in Figure 6, where for better visualization we place the states of the run not on the nodes but on the edges above them and we add a virtual edge for the root.

The decomposition procedure works in a recursive manner and begins at the root node. When executed at a node x with a state q (which belongs to some component X ∈ SCC(R)), the procedure creates an empty context C = • which spans the edge above the node. If a child of x has a state that belongs to the same component X, then the procedure moves to this node and expands the context C to span the edge above the node child and the whole subtree rooted at the opposite child. This step is repeated iteratively until the procedure reaches a leaf node or a node whose both children have states not in X. In the latter case, the procedure is called recursively on both children nodes, creating two separate children context nodes.

Clearly, the contexts created during the decomposition are realized by some components of R and the structure of these components takes the form of a synopsis tree. For instance, for the decomposition of Figure 6 the resulting synopsis tree is τ in Figure 5. Naturally, this synopsis tree respects the transitions of the run of R on the input tree. Furthermore, since every context has been maximally expanded, every node of the synopsis tree does not share the same label with any of its children. This shows that the constructed synopsis tree is primitive.

We also remark that the height of a primitive synopsis tree of a stepwise automaton R is bounded by the number of different components in G R and hence by the number of states of R. Consequently, PST(R) is a finite language and, moreover, it can be represented with a simple deterministic binary bottom-up tree automaton whose size is polynomial in the size of R.

In order to represent the target language and the possible edited trees, one needs a relaxed version of primitive synopsis trees: Definition 2. A basic synopsis tree of an automaton T is a synopsis tree σ of T that respects the transition function of T (cf. Definition 1). We denote by BST(T ) the set of all basic synopsis trees of T .

For example, the tree σ in Figure 5 is a basic synopsis tree that respects the transitions of the run of the automaton T depicted on the right-hand side of Figure 2.

Notice that the set of basic synopsis trees of an automaton T can be represented by a deterministic binary bottom-up tree automaton of size polynomial in the size of T , even though this set is not necessarily finite.

The following lemma shows that the language given by the semantics of a basic synopsis tree of T is bounded repairable into the language L (T ).

Lemma 2. ⟦σ⟧ T ↪ BR L (T ) for any stepwise automaton T and any σ ∈ BST(T ).

The proof of this lemma is technical and is based on the following observations. Any tree t ∈ ⟦σ⟧ T can be seen as a composition of contexts, one for every node of σ and each belonging to the language of the corresponding component. Every such context can be decorated with states from a run of T that justifies that the context belongs to the language of its corresponding component. To make this decoration a proper run of T , one needs to insert additional contexts that allow the transition from one component to the other -this is possible because the basic synopsis tree σ respects

τ ∶ {p r 2 } {p r 1 } {p r 0 } {p a 1 } {p a 0 } {p a 0 } {p d 1 } {p d 0 } {p b 1 } {p b 0 } {p a 1 } {p a 0 } {p a 0 } σ ∶ {q r 1 } {q r 1 } {q r 0 } {q d 2 } {q d 1 } {q d 0 } {q a 1 } {q a 0 } {q b 0 } {q a 1 } {q a 0 } {q b 0 } {q c 0 } Figure 7: Covering of PST τ by BST σ.
the transition function of T and because σ is labeled with strongly connected components. Additionally, the symbols used for substitution in the semantics of the leaf nodes of σ may need to be replaced by appropriate tree fragments. Finally, we observe that the number of inserted contexts and tree fragments depends only on the size of σ and their sizes depend only on the size of T , which means that the number of edits that are required to repair t into L (T ) is independent of the size of t.

Coverings

The remaining part of the puzzle is to identify how to connect the primitive synopsis trees of the restriction automaton R to a finite subset of basic synopsis trees of the target automaton T . This is accomplished by the notion of coverability between synopsis trees.

Definition 3. Given two automata R and T and two synopsis trees τ of R and σ of T , we say that σ covers τ iff there exists an injective mapping λ of non-trivial nodes of τ to non-trivial nodes of σ such that: 1.

λ maps components in a compatible manner, i.e., L (R τ (x)) ⊆ L (T σ(λ(x))) for every non-trivial node x of τ ; 2.

λ preserves the post-order of non-trivial nodes, i.e., x ≼ post τ y iff λ(x) ≼ post σ λ(y) for any two non-trivial nodes x and y of τ ; 3.

λ preserves the ancestorship of non-horizontal nodes, i.e., x ≼ anc τ y iff λ(x) ≼ anc σ λ(y) for every non-horizontal node x of τ and every non-trivial node y of τ .

Figure 7 presents a covering of a primitive synopsis tree τ of R by a basic synopsis tree σ of T (square boxes represent non-trivial nodes, and they have double borders when the component is non-horizontal).

We are now able to state the main theorem of the paper: Theorem 1 (Characterization). Given two regular tree languages specified by stepwise automata R and T , L (R) is bounded repairable into L (T ) iff every primitive synopsis tree of R is covered by some basic synopsis tree of T .

Before turning to the proof of the above result, we explain the main ideas underlying the notion of covering. As a first remark, we observe that, given R and T such that L (R) ↪ BR L (T ), any reasonable strategy for repairing R into T with a uniformly bounded number cost will apply the edit operations only at the "junctions" of contexts realized by different components. Intuitively, this property holds because the non-trivial components of R can realize arbitrary large repetitions of the same context -these repetitions either do not need any editing at all, or they need an arbitrary large amount of editing. This gives an intuitive account for enforcing containments between languages recognized by components in the first condition of Definition 3 (not surprisingly, a similar condition was introduced in [START_REF] Benedikt | Regular repair of specifications[END_REF] for characterizing bounded repairability between regular languages of words).

As for the other two conditions, it is worth looking at the effect of an edit operation on the curry encoding of an unranked tree. Let us consider an unranked tree t with a distinguished node x that has to be deleted. There is a unique way to represent the curry encoding of t together with the node x as an expression of the form C ○ (t ′ @(C ′ ○ a)), where C ′ is a horizontal context that represents the hedge of subtrees under x and a is the label of x. The result of the deletion of x from t is encoded by the curried tree C ○ (C ′ ○ t ′ ) (see Figure 8 for an example). Note that this operation does not allow the deletion of the leftmost leaf node in the curried tree (this would correspond to deleting the root node in an unranked tree, an operation that is typically prohibited). The operation of inserting a new node y in an unranked tree t can be described in a similar way using curry encodings and horizontal contexts. Precisely, given an unranked tree t with curry encoding C ○(C ′ ○t ′ ), where C ′ is a horizontal context, the curried tree C ○ (t ′ @(C ′ ○ a)) represents the unranked tree that results from the insertion of a new a-labeled node y in t having as children the hedge represented by C ′ .

We now observe that the transformations on curried trees described above satisfy two crucial properties: (i) they preserve the post-order of the nodes and (ii) they preserve the ancestorship of non-horizontal contexts (e.g., C in Figure 8) with their descendants. These properties are precisely captured by the last two conditions of Definition 3.

PROOF OF THE MAIN RESULT

The following subsections are devoted to prove the two directions of the characterization given in Theorem 1.

From covering to repair

We begin with the proof of the "if" direction of Theorem 1, namely, we show how we can derive a strategy for repairing L (R) into L (T ) with a uniformly bounded number of edits, under the assumption that every primitive synopsis tree of R is covered by some basic synopsis tree of T .

In addition to Lemmas 1 and 2, we need the following crucial property:

Lemma 3. For any synopsis tree τ of R and any synopsis tree σ of T , if σ covers τ , then ⟦τ ⟧ R ↪ BR ⟦σ⟧ T .

Before sketching the proof of Lemma 3, we explain how the "if" direction of Theorem 1 follows from it. By Lemma 1, the restriction language is contained in the union of the languages induced by the semantics of the primitive synopsis trees of R. By hypothesis, each of these trees is covered by a basic synopsis tree of the target automaton T . Thus by Lemma 3 their languages can be transformed into the languages induced by the semantics of some basic synopsis trees, using a bounded number of edits. By Lemma 2 the languages of the basic synopsis trees can be in turn repaired into the target language. The result now follows from the fact that there are only finitely many primitive synopsis trees and the fact that bounded repairability is a transitive relation and is preserved under finite unions.

We now turn to the proof of Lemma 3. For a technical reason, we need to slightly extend the definition of synopsis tree by allowing the use of a special node labeled ǫ that represents a dummy trivial component. The semantics is extended in the natural way by letting L (A ǫ) = {•} (for any stepwise automaton A). Because all trivial components have the same semantics (i.e., they all recognize the language {•}), we shall often identify a trivial component of an automaton with the dummy component ǫ.

The first step consists of "interpolating" the two synopsis trees τ and σ by a synopsis tree θ of R such that: ❼ θ has the same labels (i.e., components) of τ on the non-trivial nodes and it covers τ via a bijection (between non-trivial nodes) that maps any non-trivial node of τ with label X ∈ SCC(R) to a non-trivial node of θ with the same label X (we say that τ strongly covered θ), ❼ θ has the same domain (i.e., set of nodes) of σ and it is covered by σ via the identity function between non-trivial nodes (we say that θ is embedded in σ). It is not difficult to show that such an interpolating synopsis tree θ exists and that the language ⟦θ⟧ R is contained in the language ⟦σ⟧ R : Lemma 4. If τ is covered by σ, then there is an synopsis tree θ of R such that τ is strongly covered by θ and θ is embedded in σ.

Lemma 5. For a synopsis tree θ of R and a synopsis tree

σ of T , if θ is embedded in σ, then ⟦θ⟧ R ⊆ ⟦σ⟧ T . X α H 1 β 1 H k β k ǫ . . . promotion X ǫ H 1 β 1 H k β k α . . . α demotion ǫ ǫ α ǫ α ǫ reduction α
Figure 9: Synopsis tree operations.

Recall that ⟦θ⟧ R ⊆ ⟦σ⟧ T implies ⟦θ⟧ R ↪ BR ⟦σ⟧ T and that the bounded repairability relation ↪ BR is transitive. We thus reduced the problem to showing that ⟦τ ⟧ R ↪ BR ⟦θ⟧ R .

Towards this goal, we can take advantage of the notion of strong coverability, and in particular of the fact that this is an equivalence relation, namely, it is reflexive, symmetric, and transitive (note that symmetry and transitivity follow from the fact that the mapping that witness strong coverability is a bijection between non-trivial nodes and preserves the labeling). In the sequel we only work with synopsis trees of the automaton R. This allows us to remove the automaton R from the notation that follows.

The next step is to associate with any synopsis tree ζ (of R) a suitable normal form ζ * that can be used as a canonical representative of the equivalence class of ζ induced by the strong coverability relation. In order to derive the normal form of a given synopsis tree, we will introduce generic editing operations on synopsis trees that preserve the strong coverability relation and entail bounded repairability. We will then prove that ⟦τ ⟧ can be repaired into ⟦θ⟧ with a uniformly bounded number of edits by first repairing ⟦τ ⟧ into ⟦τ * ⟧ and then repairing ⟦θ * ⟧ (= ⟦τ * ⟧) into ⟦θ⟧ (recall that τ and θ strongly cover each other and hence τ * = θ * by canonicity of the normal form). The repair strategy that witnesses bounded repairability between ⟦τ ⟧ and ⟦τ * ⟧ (resp., ⟦θ * ⟧ and ⟦θ⟧) can be read off the sequence of generic editing operations that takes τ to its normal form τ * (resp., θ to its normal form θ * ).

We describe below the structure of a synopsis tree in normal form.

Definition 4. A synopsis tree ζ is in normal form iff one of the following cases holds: 1.

ζ = ǫ, namely, ζ consists of a single node labeled with a trivial component,

2.

ζ = X(α, ǫ), where X is a non-trivial horizontal component and α is a synopsis tree in normal form,

3. ζ = ǫ(α, X(β, ǫ))
, where X is a non-horizontal component and α and β are synopsis trees in normal form.

We observe that the root of a synopsis tree in normal form is a horizontal (possibly trivial) node and that its left sub-tree is also in normal form. In particular, this means that all components along the leftmost branch of a synopsis tree in normal form are horizontal.

The following lemma shows that synopsis trees in normal form can be used as canonical representatives of the equivalence classes induced by the strong coverability relation. The proof of this lemma is by simple structural induction and case analysis.

Lemma 6. If τ and ζ are two synopsis trees in normal form that strongly cover each other, then τ and ζ are isomorphic.

Thanks to Lemma 6, we can define the normal form ζ * of a synopsis tree ζ as the unique synopsis tree that is in normal form and that strongly covers ζ, provided that this tree exists.

Our next goal is to prove that the normal form ζ * of ζ indeed exists, and that can be attained by a finite sequence of generic editing operations on synopsis trees. These operations are called promotion, demotion, and reduction, and are presented in Figure 9. There, ǫ represents a trivial component, X represents an arbitrary component, H1, . . . , H k represent horizontal (possibly trivial) components, and α, β1, . . . , β k represent arbitrary synopsis trees. Note that the figure describes the case where the promotion, demotion, and reduction operations are applied at the root of a synopsis tree -in general, these operations can be applied to any sub-tree of a synopsis tree. We write ζ → * op ζ ′ whenever ζ ′ can be obtained from ζ by applying a finite sequence of promotion, demotion, and reduction operations. In order to give further intuition about these operations, we remark an analogy between the operations of promotion, depicted in Figure 9, and deletion, depicted in Figure 8 (a similar correspondence holds between the operations of demotion and insertion of a new root). In this case, the root X of the synopsis tree is acting as the the context C of the curried tree, the sub-tree α is acting as the curried sub-tree t ′ , and the sub-tree rooted at H1 is acting as the horizontal context C ′ .

It is important to point out that the editing operations on synopsis trees described above preserve the post-order of non-trivial nodes and the ancestorship of non-horizontal nodes. From this it follows that they also preserve the strong coverability relation. Furthermore, the following lemma shows that the normal form of a synopsis tree exists and can be obtained via a sequence of promotion, demotion, and reduction operations: The proof goes by a structural induction on the synopsis tree ζ that has to be normalized. Specifically, one first normalizes the left and right sub-trees of ζ separately using induction. One then completes the normalization procedure by applying suitable operations on the basis of the component at the root of ζ: if this component is non-horizontal, then one applies a promotion operation followed by a demotion operation; if it is horizontal and non-trivial, then one only applies a promotion operation; if it is trivial, then one applies a promotion followed by a reduction operation.

The next lemma shows that if ζ → * op ζ ′ , then the two languages ⟦ζ⟧ and ⟦ζ ′ ⟧ are repairable one into each other with a uniformly bounded number of edits. In other words, the application of a promotion, demotion, or reduction operation to a synopsis tree ζ corresponds to a small amount of edits over ⟦ζ⟧. The proof of this result is via a simple analysis of the transformations on languages of unranked trees that are induced by the operations of promotion, demotion, and reduction.

Lemma 8. For any pair of synopsis trees ζ and ζ

′ , if ζ → * op ζ ′ , then ⟦ζ⟧ ↪ BR ⟦ζ ′ ⟧ and ⟦ζ ′ ⟧ ↪ BR ⟦ζ⟧.
We have now all the ingredients to prove Lemma 3. Remember that by Lemmas 4 and 5 it only remains to show that ⟦τ ⟧ R ↪ BR ⟦θ⟧ R . The latter claim can be proved by combining Lemmas 6, 7, and 8. Indeed, we know from Lemma 7 that τ and θ can be converted into the normal forms τ * and θ * , respectively, by applying sequences of promotions, demotions, and reductions. Lemma 8 implies that ⟦τ ⟧ R ↪ BR ⟦τ * ⟧ R and, symmetrically, ⟦θ * ⟧ R ↪ BR ⟦θ⟧ R .

Since τ strongly covers θ, Lemma 6 implies τ * = θ * . We thus conclude that ⟦τ ⟧ R ↪ BR ⟦θ⟧ R from the transitivity of the bounded repairability relation.

From repair to covering

We now sketch the proof of the "only if" direction of Theorem 1.

We fix for the rest of the section two stepwise hedge automata R = (Σ, Q, δ0, δ, F ) and T = (∆, Q ′ , δ ′ 0 , δ ′ , F ′ ) recognizing the restriction and the target languages, respectively. We assume that L (R) is bounded repairable into L (T ) and we prove that every primitive synopsis tree of R is covered by some basic synopsis tree of T .

The general idea of the proof is to associate with any primitive synopsis tree τ of R a suitable tree tτ ∈ L (R), called witness tree of τ , such that from any optimal repair of tτ into L (T ) one can extract a basic synopsis tree σ of T that covers τ . Intuitively, the witness tree tτ is obtained from the primitive synopsis tree τ by replacing every non-trivial node x with a sufficiently large number of repetitions of a special context in L (R τ (x)), called fingerprint context. The number of repetitions of each fingerprint context will depend on the worst-case repair cost N = dist(L (R), L (T )). Using the definition of the witness tree tτ and the assumption that tτ can be repaired into some tree sτ ∈ L (T ) with at most N edits, one can then argue that sτ contains at least one copy of the fingerprint context associated with each nontrivial node x of τ and, furthermore, the arrangements of the occurrences of these fingerprints inside tτ and inside sτ coincide both with respect to the post-order relation and with respect to the ancestorship of the non-horizontal components. One finally looks at some run of T that accepts the tree sτ : this run, together with the structure of the fingerprints inside sτ , induces a basic synopsis tree σ of T and a coverability relation from τ to σ.

Below, we illustrate in more details the above arguments. We divide up the proof into defining the witness tree tτ and building the cover from its repair.

Constructing the witness tree. Before constructing the witness tree, we give the following lemma, which defines what we call a fingerprint context of a component of R.

Basically, the lemma shows that given a component X ∈ SCC(R), one can find a context C X that can be "pumped" inside the language L (R X)

(i.e., C X ○. . .○C X ∈ L (R X)) and such that L (R X) ⊆ L (T Y ) iff C X ∈ L (T Y ),
for any component Y ∈ SCC(T ). We say that a context C is cyclic for a component X if there is a state q ∈ X such that q ∈ δ(q, C). Lemma 9. For every X ∈ SCC(R), there exists a cyclic context C X ∈ L (R X) such that, for every Y ∈ SCC(T ),

L (R X) ⊆ L (T Y ) iff C X ∈ L (T Y ).
We associate with each component X a context C X that satisfies Lemma 9, and call it a fingerprint context of X.

We now fix a primitive synopsis tree τ of R and we define the corresponding witness tree tτ by using an induction on τ . In doing so, we will guarantee that δ(tτ ) ∩ τ (ε) ≠ ∅, namely, that there is a run of R on the witness tree tτ that reaches a state of the component at the root of τ . We omit the construction for the base case, where τ is a singleton, since it can be easily derived from what follows. Thus, we assume that X is the component at the root of τ and that τ1 and τ2 are the non-empty left and right sub-trees of τ . By induction hypothesis, we can denote by tτ 1 and tτ 2 the witness trees of τ1 and τ2, respectively. Moreover, we can fix a state q1 (resp., q2) in the non-empty set δ(tτ 1 ) ∩ τ1(ε) (resp., δ(tτ 2 )∩τ2(ε)). The construction of the witness tree tτ is done in a bottom-up way using the three steps described below (the reader can also refer to Figure 10).

The first step consists of merging the two trees tτ 1 and tτ 2 into a single tree that can be parsed by the automaton R ending up in the component X. We know from the definition of primitive synopsis tree that τ respects the transition function of R. In particular, this means that there exist some states q ′ ∈ X, q ′ 1 ∈ τ1(ε), and q ′ 2 ∈ τ2(ε) such that q ′ ∈ δ(q ′ 1 , q ′ 2 ). Moreover, since q1 and q ′ 1 (resp., q2 and q ′

2 ) belong to the same component at the root of τ1 (resp., τ2), there exist some contexts C1 ∈ L (R τ1(ε)) and C2 ∈ L (R τ2(ε)) such that q ′ 1 ∈ δ(q1, C1) and q ′ 2 ∈ δ(q2, C2).

tτ 1 tτ 2 C 1 C 2 q 1 q 2 @ q ′ 1 q ′ 2 C C k X q ′ q q ⎫ ⎪ ⎪ ⎬ ⎪ ⎪ ⎭ = C ′ C N n.h.
when X is non-horizontal This allows us to construct the tree

(C1 ○ tτ 1 ) @ (C2 ○ tτ 2 )
and claim that R can parse it and end up in state q ′ of component X.

The next step consists of prolonging the above tree in such a way that one can later attach repetitions of the fingerprint context C X . This is done by identifying a "recurrent" state q such that q ∈ δ(q, C X ) (this state exists since C X is cyclic) and then connecting it to the state q ′ using a suitable context C ∈ L (R X) such that q ∈ δ(q ′ , C) (note that q and q ′ belong to the same component X). The resulting tree is of the form C ○ (C1 ○ tτ 1 ) @ (C2 ○ tτ 2 ) .

In order to avoid that an editing of the witness tree tτ could modify the ancestorship of C X with the nodes of the two sub-trees tτ 1 and tτ 2 , we further assume that, if X is a non-horizontal component, then the context C that is used for connecting q to q ′ is of the form C N n.h. ○ C ′ , where N = dist(L (R), L (T )), C ′ , Cv ∈ L (R X), and C n.h. is a cyclic non-horizontal context. Recall that the ancestorship of non-horizontal contexts is preserved by the editing operations.

The last step consists of plugging in a sufficiently long repetition of the fingerprint context C X . For this, we define k = m ⋅ (2N + 1), where N = dist(L (R), L (T )) and m is the number of SCCs of T . We then attach the k-fold repetition C k X of the fingerprint context C X to the tree so far constructed, thus obtaining the witness tree

tτ = C k X ○ C ○ (C1 ○ tτ 1 ) @ (C2 ○ tτ 2 )
. Note that R can parse tτ and end up in state q ∈ X. This shows that the invariant δ(tτ ) ∩ X ≠ ∅ is satisfied.

We remark that it may happen that δ(tτ ) ∩ F = ∅ and hence tτ ∉ L (R). Strictly speaking, this could violate the claim that one can repair tτ into L (T ) with at most N edits. However, from the assumption that R is trimmed it follows that there is a context C F such that δ(q, C F ) ∩ F ≠ ∅. This means that one can always prolong tτ to obtain a tree inside the language L (R). From now on, we assume for the sake of simplicity that tτ ∈ L (R).

Building the covering from a repaired witness tree. We now turn to deriving a covering of τ by looking into the repair of tτ . We fix, once and for all, some tree sτ in the target language L (T ) that is obtained by repairing tτ with at most N edits.

Remember that the witness tree tτ contains k = m ⋅ (2N + 1) copies of each fingerprint context C X , where X = τ (x) for any non-trivial node x of τ . As a consequence, the repaired tree sτ must contain an m-fold repetition C m X of each finger context C X . In the following, we will look at the occurrences of these repeated fingerprint contexts inside sτ and compare their post-order and ancestor relationships with those induced by tτ . For this we need some definitions.

Given a context C and a node x of a tree t, we say that C occurs at node x if there exist a context C ′ and a tree t ′ such that (i) t can be written as C ′ ○ C ○ t ′ and (ii) x is the node where the sub-tree C ○ t ′ of t hangs from. We denote an occurrence of a context C at a node x of a tree t by the pair (C, x). Furthermore, we say that two occurrences (C, x) and (C ′ , x ′ ) of two contexts inside the same tree t are non-overlapping (resp., in post-order relation, ancestor relation)

if {x} ⋅ nodes(C) ∩ {y} ⋅ nodes(C ′ ) = ∅ (resp., x ≼ post t y, x ≼ anc t y).
The following lemma shows that the occurrences of the contexts C m X inside tτ are in the same post-order relation as the corresponding occurrences inside sτ , and similarly for the ancestor relation when X is a non-horizontal component.

Lemma 10. One can find a mapping f from the nontrivial nodes x of the primitive synopsis tree τ to the nodes f (x) of the repaired witness tree sτ such that: ❼ the context C m X , where X = τ (x), occurs at node f (x) in sτ , for all non-trivial nodes x of τ ,

❼

all occurrences (C m X , f (x)), with X = τ (x) and x nontrivial node of τ , are pairwise non-overlapping,

❼

x ≼ post τ y iff f (x) ≼ post sτ f (y), for all pairs of non-trivial nodes x, y of τ ,

❼

x ≼ anc τ y iff f (x) ≼ anc sτ f (y), for all pairs of non-trivial nodes x, y of τ , with τ (x) non-horizontal component.

It only remains to show how to extract a basic synopsis tree σ that covers τ from an accepting run of T on sτ .

Let ρ be a run of T that accepts sτ , let x be a non-trivial node of τ with label X, and let f (x) be the corresponding node in sτ induced by the mapping f , as defined in Lemma 10. By the previous arguments, the context C m X occurs at node f (x) in sτ . Let y be the position of the placeholder • in the fingerprint context C X and observe that C X occurs m times at nodes ε, y, y ⋅ y, . . ., y m-1 of C m X . Let yx,0 = f (x), yx,1 = f (x) ⋅ y, . . ., yx,m-1 = f (x) ⋅ y m-1 , and yx,m = f (x) ⋅ y m . Clearly, (C X , yx,0), . . ., (C X , yx,m-1) are non-overlapping occurrences of the context C X inside sτ .

Consider now the states that occur at the m + 1 nodes yx,0, yx,1, . . . , yx,m of the run ρ. From the Pigeonhole Principle, we know that there exist two nodes yx,i and yx,j, with 0 ≤ i < j ≤ m, and a component Y of T such that both states ρ(yx,i) and ρ(yx,j) belong to Y . In fact, by the definition of strongly connected component, we can assume j = i + 1 and hence C X ∈ L (T Y ). Notice that, until this point, we have not used the property of fingerprint contexts (Lemma 9). In particular, the fact that C X is a fingerprint context of X and

C X ∈ L (T Y ) implies that L (R X) ⊆ L (T Y ).
What we have just showed is that it is possible to find a mapping from any non-trivial node x of τ to a node yx = yx,i of sτ such that L (R X) ⊆ L (T Y ), where X = τ (x) and Y is the component of the state ρ(yx). Thanks to Lemma 10, we can also claim that, for all non-trivial nodes x, x ′ in τ ,

❼ x ≠ x ′ implies yx ≠ y x ′ , ❼ x ≼ post τ x ′ iff yx ≼ post sτ y x ′ , ❼ x ≼ anc τ x ′ iff yx ≼ anc sτ y x ′ , provided that the component τ (x) is non-horizontal.
We are now ready to define the basic synopsis tree σ that covers τ . The domain of σ coincides with the domain of sτ , i.e., nodes(σ) = nodes(sτ ). The labeling σ(x) of a node x of σ is given by the component X that contains the corresponding state ρ(x), where ρ is a run of T that accepts sτ . Notice that σ trivially satisfies the properties of a basic synopsis tree, as its labellings respects the transitions of T given by the run ρ. In a similar way, we can define the mapping λ that witnesses the coverability of τ by σ: for this we simply let λ map any non-trivial node x of τ to the node yx of σ. The fact that λ satisfies Definition follows easily from the properties described by the three items above (for instance, the fact that λ is injective follows from the first item). This completes the proof that τ is covered by a basic synopsis tree of T .

COMPLEXITY RESULTS

In this section we will exploit the characterization given in Theorem 1 to obtain some complexity bounds for the bounded repair problem. We will first consider the case where the regular tree languages are represented by nondeterministic stepwise automata. Then, we will concentrate on less succinct and less expressive representations, such as deterministic stepwise automata and DTDs.

Languages defined by automata

Below, we show that the bounded repair problem between restriction and target languages represented by two nondeterministic stepwise automata R and T is in Π EXP 2 (i.e., coNEXPTIME NEXPTIME ). To achieve this bound we analyze the size of a primitive synopsis tree τ of R and the minimal size of some basic synopsis tree of T that covers τ . It follows easily from Definition 1 that any primitive synopsis tree of R has height less than the number of components of R, and hence size at most 2 SCC(R) . As for the minimal size of the basic synopsis trees of T that cover a given primitive synopsis tree of R, we can prove the following: Lemma 11. Given two stepwise automata R and T and two synopsis trees τ ∈ PST(R) and σ ∈ BST(T ), if σ covers τ , then there is σ ′ ∈ BST(T ) that covers τ and has size at most 2 ⋅ τ ⋅ SCC(T ) , where τ is the number of nodes of τ and SCC(T ) is the number of components of T .

The above lemma, together with Theorem 1, gives a Π EXP 2 algorithm that receives two non-deterministic stepwise automata R and T and decides whether L (R) is bounded repairable into L (T ). The algorithm universally guesses a primitive synopsis tree τ of R of size at most 2 SCC(R) , then it existentially guesses a basic synopsis tree σ of T of size at most 2 SCC(R) +1 ⋅ SCC(T ) and a function λ from non-trivial nodes of τ to non-trivial nodes of σ, and finally it checks that λ is a covering of τ by σ (this amounts at deciding language inclusions, which can be done in exponential time [START_REF] Seidl | Deciding equivalence of finite tree automata[END_REF]).

Proposition 1. The bounded repair problem between languages represented by non-deterministic stepwise automata is in Π EXP 2 .

As for the complexity lower bound, we are only able to prove that the considered problem is EXPTIME-hard by using a straightforward reduction from the containment problem for non-deterministic stepwise automata [START_REF] Seidl | Deciding equivalence of finite tree automata[END_REF]. Precisely, given two non-deterministic stepwise automata R and T , one can decide whether L (R) ⊆ L (T ) by first constructing two automata R * and T * that recognize the languages

L (R * ) = {#(t1, ..., tn) n ∈ N, ∀1 ≤ i ≤ n. ti ∈ L (R)} and L (T * ) = {#(t1, ..., tn) n ∈ N, ∀1 ≤ i ≤ n. ti ∈ L (T )},
respectively, where # is a fresh symbol not belonging to the alphabets of R and T , and then checking whether L (R * ) is bounded repairable into L (T * ). Note that the latter condition holds iff L (R) ⊆ L (T ).

Proposition 2. The bounded repair problem between languages represented by non-deterministic stepwise automata is EXPTIME-hard.

Languages defined by DTDs

We now analyze the complexity of the bounded repair problem when the languages are represented by DTDs.

Recall that a DTD is a function mapping any letter a in the underlying alphabet to a regular expression D(a) over the same alphabet. The language defined by a DTD D is the set of all unranked trees t such that (i) the root of t is labeled with some letter from a distinguished set of initial symbols and (ii) for every node x ∈ nodes(t), the sequence of labels of the children of x is a word inside the language D(t(x)). A DTD D is non-recursive if its dependency graph (i.e., the graph that connects a letter a to a letter b whenever b occurs in the language D(a)) is acyclic. A DTD D is deterministic if all its regular expressions D(a) are 1unambiguous [START_REF] Brüggemann-Klein | One-unambiguous regular languages[END_REF]. This is also equivalent to saying that the Glushkov automata [START_REF] Brüggemann-Klein | One-unambiguous regular languages[END_REF] that correspond to the regular expressions of the DTD are deterministic. From results in [START_REF] Champavère | Efficient inclusion checking for deterministic tree automata and XML schemas[END_REF] (in particular, from Proposition 4 and Theorem 5) it follows that any deterministic DTD can be turned in polynomial time into an equivalent deterministic stepwise automaton.

As a first remark, we recall that the containment problem for non-deterministic DTDs is PSPACE-complete. The lower bound follows easily from the PSPACE-hardness of containment of regular expressions [START_REF] Stockmeyer | Word problems requiring exponential time[END_REF]. The upper bound is a folklore result: given two DTDs D and D ′ , one can decide whether the language defined by D is contained in the language defined by D ′ by first removing useless rules and then checking that, for every letter a in the alphabet of D, the language D(a) is contained in the language D(a ′ ).

Following the same idea in the proof of Proposition 2, one can reduce the containment problem for regular expressions to the bounded repairability problem for languages defined by non-recursive non-deterministic DTDs, thus showing that the latter problem is at least PSPACE-hard. Proposition 3 below gives a stronger result by showing that PSPACEhardness holds also in the presence of non-recursive deterministic DTDs. The proof of this result is technical and uses a reduction from the corridor tiling problem [START_REF] Van | The convenience of tilings[END_REF].

Proposition 3. The bounded repair problem between languages represented by deterministic DTDs is PSPACEhard, even for non-recursive DTDs.

For DTDs, even deterministic ones, we do not have a better upper bound than in the general case. Recall that containment of deterministic stepwise automata (and hence deterministic DTDs as well) is in PTIME. It is thus conceivable that a PSPACE upper bound for the bounded repair problem exists for deterministic DTDs. As we are not able to provide such a tight complexity bound, we can only reuse Proposition 1 to claim that the complexity of the bounded repair problem for deterministic DTDs is between PSPACE and Π EXP 2 .

For non-recursive DTDs we can do better, since they define languages of trees of bounded height, and can be coded by regular word languages (see, for instance, [START_REF] Segoufin | Validating streaming XML documents[END_REF]). The edit operations on trees translate to edit operations on the word encodings, and hence we can apply the fact that bounded repairability for word languages recognized by deterministic finite automata is in coNP [START_REF] Benedikt | Regular repair of specifications[END_REF]. Because there is an exponential blow-up in the encoding, this gives us a coNEXPTIME upper bound for non-recursive DTDs. Again, the best lower bound we have for non-recursive DTDs is PSPACE.

We now consider a specialization of the problem where the alphabet Σ of the restriction language is fixed. We show that, in this case, the problem is between PSPACE and EXPTIME for languages represented by non-deterministic DTDs, and between coNP and Π P 2 (i.e., coNP NP ) for languages represented by deterministic DTDs.

Let us first discuss the complexity upper bounds. Suppose that D is a DTD defining a restriction language over the fixed alphabet Σ. A close inspection to the translation from DTDs to stepwise automata [START_REF] Champavère | Efficient inclusion checking for deterministic tree automata and XML schemas[END_REF] discloses the following crucial property: Lemma 12. Given a non-deterministic (resp., deterministic) DTD D that defines a restriction language R over an alphabet Σ, one can compute in polynomial time a nondeterministic (resp., a deterministic) stepwise automaton R = (Σ, Q, δ0, δ, F ) that recognizes R and whose state space can be partitioned into k ≤ 2 Σ subsets Q1, . . . , Q k such that ❼ every component of R is contained in some set Qi, ❼ for all states q1, q2, q ∈ Q, if q ∈ δ(q1, q2) and q2 and q are in different components, then q2 ∈ Qi and q ∈ Qj for some 1 ≤ i < j ≤ k.

As an example, the automaton R described in Example 3 is a deterministic stepwise automaton whose state space can be partitioned into 9 sets that satisfy the first part of the claim:

Q1 = {p a 0 }, Q2 = {p a 1 }, Q3 = {p b 0 }, Q4 = {p b 1 }, Q5 = {p c 0 }, Q6 = {p d 0 }, Q7 = {p d 1 }, Q8 = {p r 0 , p r 1 }, Q9 = {p r 2 }.
Lemma 12 above implies that any path in the transition graph of R (see, for instance, the left-hand side graph of Figure 4) traverses at most 2 Σ -1 vertical edges that connect pairs of states in different components. As a consequence, any primitive synopsis tree of R has size at most Q 2 Σ , i.e., polynomial in the size of R when Σ is fixed.

Putting together Lemma 12, Lemma 11, and Theorem 1 one obtains an EXPTIME (resp., a Π P 2 ) algorithm that decides whether R ↪ BR T , where R and T are languages defined by non-deterministic (resp., deterministic) DTDs and R is over a fixed alphabet Σ. The algorithm has the same structure of the one presented in the previous sub-section. Namely, it translates the input DTDs into equivalent stepwise automata R and T , then it guesses universally a primitive synopsis tree τ of R of polynomial size and existentially a basic synopsis tree σ of T of polynomial size, together with a function λ from non-trivial nodes in τ to non-trivial nodes in σ, and finally it checks that λ is a covering of τ by σ. As previously mentioned, the last step of the algorithm can be performed in either exponential time or polynomial time, depending on whether the input DTDs are non-deterministic or deterministic. Note that the complexity upper bounds do not increase if the target languages are given directly by non-deterministic/deterministic stepwise automata. Proposition 4. The bounded repair problem between a restriction language represented by a non-deterministic (resp., deterministic) DTD over a fixed alphabet and a target language represented by a non-deterministic (resp., deterministic) stepwise automaton over an arbitrary alphabet is in EXPTIME (resp., in Π P 2 ).

Finally, we show that even strong restrictions, including fixing both alphabets, cannot get us below PSPACE in the non-deterministic case. We have already discussed how the containment problem for regular expressions can be reduced to the bounded repair problem for languages defined by non-recursive non-deterministic DTDs. The same reduction holds when we fix the alphabets, thus showing that the bounded repair problem between non-recursive nondeterministic DTDs over fixed alphabets is still PSPACEhard. We also provide a coNP lower bound for the analogous problem when the languages are represented by nonrecursive deterministic DTDs over fixed alphabets. This lower bound follows quite easily from a reduction from the validity problem for propositional formulas in disjunctive form (i.e., the dual of the SAT problem). The idea is to encode in the restriction language all the possible valuations for the propositional variables and then restrict the target language to consist only of encodings of valuations that satisfy at least one clause of the propositional formula.

A similar reduction was given in [START_REF] Benedikt | Regular repair of specifications[END_REF] for languages of words recognized by deterministic finite automata. The additional complication here is that we have to fix the restriction and the target alphabets; however, the reduction is still possible by encoding the valuation of each variable with a block of nodes labeled over a binary alphabet.

Proposition 5. The bounded repair problem between languages represented by non-recursive non-deterministic (resp., deterministic) DTDs with both restriction and target alphabets fixed is PSPACE-hard (resp., coNP-hard).

THE UNRESTRICTED CASE

In this section we consider the so-called unrestricted case of the bounded repairability problem, namely, a variant of the problem where the restriction language is assumed universal (i.e., equal to T Σ ) and the target language is represented by a stepwise automaton T .

We recall the assumption that any stepwise automaton T is trimmed (i.e., every state of T appears in some accepting run of A on some input tree). Under this assumption, we say that an automaton T is complete over Σ if for every tree t ∈ T Σ there is a (possibly non-accepting) run of T on t.

In this section we also make use of deterministic visibly pushdown transducers [START_REF] Raskin | Visibly pushdown transducers[END_REF][START_REF] Alur | Adding nesting structure to words[END_REF] as suitable devices that transform unranked trees in a streaming fashion, namely, that receive the serialized version of an unranked tree (i.e., a well-formed sequence of opening and closing tags corresponding to the pre-order traversal of a tree) and output the serialized version of another unranked tree. By a slight abuse of notation we identify unranked trees with their serializations. The following result gives equivalent conditions for bounded repairability in the unrestricted case. Proposition 6. Given an alphabet Σ and an automaton T = (∆, Q, δ0, δ, F ), the following conditions are equivalent:

❼ T Σ is bounded repairable into L (T ),

❼

T is complete over Σ, ❼ there exist k ∈ N and a deterministic visibly pushdown transducer that receives any unranked tree t over Σ and outputs an unranked tree t ′ such that dist(t, t ′ ) ≤ k and ext(t ′ ) ∈ L (T ).

From the above characterization one can derive a polynomial-time algorithm that decides whether T Σ is bounded repairable into L (T ), when T is given by a deterministic stepwise automaton. For this it is sufficient to turn T into a trimmed deterministic automaton T ′ = (Σ, Q ′ , δ ′ 0 , δ ′ , F ′ ) over Σ and then check that (i) for every symbol a ∈ Σ, δ ′ 0 (a) ≠ ∅ and (ii) for every pair of states q1, q2 ∈ Q ′ , δ ′ (q1, q2) ≠ ∅. When the target language is represented by a non-deterministic stepwise automaton T , the complexity increases to EXPTIME: one can simply determinize T and then use the decision procedure for the deterministic case.

As one could expect, the above complexity bounds (i.e., PTIME for deterministic stepwise automata and EXPTIME for non-deterministic stepwise automata) are tight -hardness proofs can be derived from reductions of the emptiness and universality problems, respectively, on the corresponding classes of automata.

Proposition 7. The bounded repair problem in the unrestricted case when the target language is represented by a non-deterministic (resp., deterministic) stepwise automaton is EXPTIME-complete (resp., PTIME-complete).

It is worth remarking some similarities and differences between the considered problem and the analogous unrestricted bounded repair problem for regular languages of words [START_REF] Benedikt | Regular repair of specifications[END_REF]. First of all, the characterization given in Proposition 6 implies that, in the unrestricted case only, if the universal tree language T Σ is bounded repairable into a regular tree language T , then the repair strategy can be implemented by a deterministic visibly pushdown transducer that works directly on serializations of unranked trees. This is reminiscent of the equivalence between the unrestricted repair problems for regular word languages in the nonstreaming and in the streaming settings. We also remark that bounded repairability for tree languages is a much stronger property than that for word languages. In [START_REF] Benedikt | Regular repair of specifications[END_REF] (Corollary 20), it is shown that for every alphabet Σ and every regular word language T , Σ * is bounded repairable into T or into its complement T ∁ . When considering languages of trees the situation is quite different: for every alphabet Σ, there are regular tree languages T such that T Σ is bounded repairable neither into T nor into its complement T ∁ .

CONCLUSIONS AND RELATED WORK

In this paper we present the first algorithm for determining whether one regular tree language can be edited to another regular tree language with a finite number of edits.

Edit distance between trees has been extensively studied [START_REF] Bille | A survey on tree edit distance and related problems[END_REF], and several polynomial-time algorithms exist based on dynamic-programming. The problem of computing the distance between a tree and a schema has also been studied [START_REF] Boobna | Correctors for XML data[END_REF]. Regarding similarity between schemas, syntactic similarity between schemas were studied in [START_REF] Fan | Information preserving XML schema embedding[END_REF] and a similarity setbased measure was proposed in [START_REF] Antonopoulos | Generating, sampling and counting subclasses of regular tree languages[END_REF], but both works did not consider edit operations between trees. Approximation of regular tree languages by single-type regular tree languages has been studied in [START_REF] Gelade | Simplifying XML schema: single-type approximations of regular tree languages[END_REF] were the setting is restricted to a particular class of tree languages (single-type) and the approximation is modeled by language containment. To the best of our knowledge, the problem of editing all trees in a schema to trees in another schema has not been studied explicitly. In the word case, the analogous notion has been studied only recently [START_REF] Benedikt | Regular repair of specifications[END_REF].

We leave several problems open; most importantly, we have a gap in the complexity for the repair problem. We hope to close this by lowering the complexity to EXPTIME.

Bounded repairability is a strong notion of inclusion between schemas: there may be two schemas where the number of edits is unbounded, but is small as a percentage of the tree size. In [START_REF] Benedikt | The cost of traveling between languages[END_REF] we showed a way to compute this "percentage of edits" in the word case. We would like to generalize this to the setting of trees. It would also be interesting to consider restricted processors that work in an online fashion -in the word case, the requirement for a repair to be "streaming" has been studied [START_REF] Benedikt | Regular repair of specifications[END_REF], where the streaming notion is captured by property that the repairs can be generated by a finite state transducer without lookahead. For trees, it is not clear what model should be used as a "streaming repair processor". Theorem 6 shows that in the unrestricted case it always suffices to repair with a visibly pushdown transducer, but in the general case VPTs maybe too restrictive.

Example 1 .

 1 Consider the following DTDs: R: r → d, c* d → a*, b* a → EMPTY b → EMPTY c → EMPTY T : r → a*, e e → b*, c* a → EMPTY b → EMPTY c → EMPTY

Figure 1 :

 1 Figure 1: Curry encoding of an unranked tree.

Figure 3 :

 3 Figure 3: Edit operations on unranked trees.

Figure 4 :

 4 Figure 4: Transitions graphs of automata R and T .

Figure 5 :

 5 Figure 5: Synopsis trees τ and σ of automata R and T . also be seen as a sub-automaton of A that contains horizontal transitions only. Similarly, we say that X is trivial iff it realizes the empty context only, i.e., L (A X) = {•}. Note that trivial components are horizontal. As an example, consider again the transition graphs of Figure 4. All components except {p d 1 }, {p a 1 }, {q r 1 }, and {q a 1 } are trivial. The components {p d1 } and {q r 1 } are non-trivial horizontal, since they both realize the contexts •, •@c, (•@c)@c, . . . The components {p a 1 } and {q a 1 } are non-horizontal, since they both realize the contexts •, a@•, a@(a@•), . . .

Figure 5

 5 contains two synopsis trees τ and σ, respectively for the automata R and T of Example 3.

Figure 6 :

 6 Figure 6: Decomposition of a tree.

Figure 8 :

 8 Figure 8: Deleting a node in the curry encoding.

Lemma 7 .

 7 For any synopsis tree ζ, we have ζ → * op ζ * .

Figure 10 :

 10 Figure 10: Construction of the witness tree tτ .

Acknowledgments. We would like to thank Michael Benedikt for the many helpful remarks on the paper. The first two authors were supported by the EPSRC (UK) grant EP/G004021/1 and by the EU project FOX (FP7-ICT-233599). The third author has been partially supported by Ministry of Higher Education and Research, Nord-Pas de Calais Regional Council and FEDER through the Contrat de Projets Etat Region (CPER) 2007-2013, and Codex project ANR-08-DEFIS-004.


Michal Valko

Milos Hauskrecht

Feature importance analysis for patient management decisions

Keywords: Data Interpretation, Statistical [E05, 318, 740, 300] Decision

The objective of this paper is to understand what characteristics and features of clinical data influence physician's decision about ordering laboratory tests or prescribing medications the most. We conduct our analysis on data and decisions extracted from electronic health records of 4486 post-surgical cardiac patients. The summary statistics for 335 different lab order decisions and 407 medication decisions are reported. We show that in many cases, physician's lab-order and medication decisions are predicted well by simple patterns such as last value of a single test result, time since a certain lab test was ordered or time since certain procedure was executed.

Introduction

Advances in data collection and electronic health record technologies have led to the emergence of clinical datasets, where data instances consist of sequences of clinical findings, lab values, measurements, and medication actions [START_REF] Morik | Combining Statistical Learning with a Knowledge-Based Approach -A Case Study in Intensive Care Monitoring[END_REF]. Such multivariate time series data provide us with a complex temporal characterization of the patient case. Analyses of these clinical datasets can be extremely useful for building models supporting patient outcome prediction, early detection of adverse events, or clinical decision making [START_REF] Balas | Information systems can prevent errors and improve quality[END_REF].

The key challenge when analyzing the clinical datasets is the complexity of the multivariate time series and the number of possible temporal features (patterns) one may generate to characterize such data. Inevitably we ask what types of features are the most important to represent the patient case. Are patterns related to most recent patient history more important than the distant past? What features do the physicians base their decisions upon? Are values or trends more important? Do physicians tend to look into simple trends and simple time constrains or into more complex temporal characteristics between several clinical variables?

We study this problem by analyzing the importance of various temporal features for lab and medication order decisions.

More specifically, we investigate what temporal characteristics of the patient state influence the physician's decision the most.

Our analyzes on a collection of 4486 post-surgical cardiac patient records show that a relatively simple temporal characterization of the patient state is often sufficient to predict well many lab order and medication decisions. Moreover, we identify which of those simple characteristics are the most valuable sources of information for such a prediction.

The paper is structured as follows. First, we introduce the post-surgical cardiac dataset and temporal features used in our analysis. After that, we analyze the data and present statistics reflecting how different features predict the lab order and medication decisions. Finally, we discuss the results and conclude.

PCP Dataset

Post-surgical cardiac patient (PCP) database is a database of de-identified records for 4486 post-surgical cardiac patients treated at one of the University of Pittsburgh Medical Center (UPMC) teaching hospitals. The entries in the database were populated from data from the MARS system, which serves as an archive for much of the data collected at UPMC. The records for individual patients included discharge records, demographics, progress notes, all labs and tests (including standard and all special tests), two medication databases, micro-biology labs, EKG, radiology and special procedures reports, and a financial charges database. The data in PCP database were cleaned, cross-mapped, and are currently stored in a local MySQL database with protected access.

Dataset used in the analysis. To conduct our analysis, we used time-stamped data stored in the PCP database and converted them into a vector space representation of a patient state at discrete time points to get a collection of patient state examples. More specifically, each patient record in the PCP was used to build a sequence of patient state examples reflecting scenarios the physicians faced at 8:00am every 24 hours when managing the patient (Figure 1). Only the information available up to the segmentation points was considered in the vector space representation. Our 24-hour segmentation led to the total of 30,828 patient state examples. Patient-management decisions. In addition, every patient state example in the dataset that was generated by the above segmentation process was linked to lab order and medication decisions that were made for that patient within next 24 hours. Patient management decisions considered were:

• Lab order decisions with (true/false) values reflecting whether the lab was ordered within the next 24 hours or not • Medication decisions with (true/false) values reflecting if the patient was given a medication within the next 24 hours or not.

A total of 335 lab order and 407 medication decision values were recorded and linked to every patient state example in the dataset.

Features

To represent a patient state we have adopted a vector space representation that is convenient for machine learning approaches. In this representation a patient state is represented by a set of features characterizing the patient at a specific point in time and their corresponding feature values. Features represent and summarize the information in the medical record such as last blood glucose measurement, last glucose trend, or the time the patient is on heparin. These representations were also used in our experimental studies published in [START_REF] Valko | Conditional anomaly detection methods for patient-management alert systems[END_REF][START_REF] Valko | Distance metric learning for conditional anomaly detection[END_REF][START_REF] Hauskrecht | Evidence-based Anomaly Detection in Clinical Domains[END_REF].

The features used in our experiment were generated from time series associated with different clinical variables, such as blood glucose measurement, platelet measurement, Amiodarone medication. The clinical variables used in this study were grouped into five categories:

1. Laboratory tests (LABs)

Medications (MEDs)

3. Visit features/demographics 4. Procedures

Heart support devices

We now briefly describe the features generated for clinical variables in each of these categories.

Lab Features

For the categorical labs, for example the ones with POS/NEG results we used the following features: Last value; second last value; first value; time since last order; whether the order pending; whether the value is known; and, whether the trend known. For the labs with continuous or ordinal values we used a richer set of features including features as difference between the last two values, slope of the last 2 values, and their percentage drop/increase. We used the same kind of features for the following pairs of lab values (last value, first value), (last value, nadir value), (last value, horizon value). Nadir and horizon value are the lab values with the smallest and the greatest value recorded up to that point. Figure 2 illustrates a subset of features generated for the labs with continuous values. The total number of features generated for such a lab is 40.

Medication Features

For each medication we used four features: 1) indicator if the patient is currently on the medication 2) time since the patient was on that medication 3) time since the patient was put on that medication for the first time and, 4) time since last change in the status of patient taking the medication.

Visit/Demographic Features

We only have 3 features in this category: age, sex, and race. These are static and same for every time point we generate.

Procedure Features

Procedure features capture the information about procedures such as Heart valve repair that were performed either in OR or at the bedside. In our data we distinguish 36 different procedures that are performed on cardiac patients. We record four features per procedure: 1) time since the procedure was done last time 2) time since the procedure was done first time 3) whether the procedure was done in last 24 hours, and 4) whether the procedure was ever done to this patient.

Methods

Univariate AUC analysis

Our objective is to evaluate the significance of a feature for predicting either the lab order or medication order decision.

Feature categories While one can always analyze predictive relations in between features and individual decisions, the aim of this paper is to

understand what kinds of features influence lab and medication orders the most. Hence our analysis focuses on summary statistics across multiple labs and medication decisions, and across multiple feature categories. To conduct these analyses we grouped 9,223 different features into:

(1) Five categories corresponding to lab, medication, demographics, procedures, and heart support device features.

(2) Forty temporal feature categories, each representing the same temporal characteristic of the time series. For example the category 'Time since last LAB' subsumes 'Time since last Platelet count' and 'Time since last Glucose lab' features.

Assessment metric

We used the AUC score to assess the feature significance. AUC score is an area under the Receiver operating characteristic [START_REF] Green | Signal detection theory and psychophysics[END_REF] which is used to measure the predictive strength of a feature. To assess the importance of each feature category we computed the number of times the feature in the category is the best AUC feature for predicting the decisions.

Multivariate analysis

The limitation of the univariate analysis is the focus on an individual feature and it ability to predict the order decisions. In general, a better result may be often obtained by combining multiple features into a predictive model. To assess how helpful it is to use information from multiple features as opposed to just a single feature we have conducted a limited multivariate predictive analysis. Due the large amount of data, we used linear SVM classifier [START_REF] Vn | The Nature of Statistical Learning Theory[END_REF][START_REF] Burges | A tutorial on support vector machines for pattern recognition[END_REF]. In particular, for each order decision we trained such a classifier using 1) top 1; 2) top 3; and 3) top 30 features according to their AUC score computed on a subset of 2900 patients. After training the performance of the multivariate models was assessed by calculating their AUC on the remaining patient cases. The next histogram (Figure 4) shows the top 10 most important temporal lab features for predicting the orders of the same lab. The best feature categories were the times since the last lab order and lab results, in particular last value, nadir, and horizon values. The fact that the time since last measurement is the dominant feature is somewhat surprising but can be explained by the fact that many labs for our cohort of patients are done regularly and routinely, and the time since the last test was done is a good indicator of the upcoming lab order. Also surprising is a relatively low importance of trend features, in general absolute values of labs appear to be more significant for predicting the lab orders. This suggests value based prediction patterns are dominant for lab order decisions and trend information (if used at all) typically refines the pattern.

Results

Prediction of LAB orders

Figure 5 illustrates which temporal lab features predict the order of a different lab (i.e. not itself) the best. In this case, we observe that the last lab value is the most significant predictor of the order decision. This can be explained by the fact that an abnormal value of one test prompts the order of the other test. Also some lab tests are organized in panels and panels are typically ordered together creating this dependency.

Prediction of Medication orders

Figure 6 shows the influence of labs, medication, demographics, procedures, and support device features for predicting medication orders. In particular, we are showing the prediction of a medication commission, provided that a patient was not on that medication before. We see that the list is dominated by procedure features as some medications tend to follow certain procedures. Figure 8 shows the importance of medication features from different medications on the decision. One possible explanation for this dependency is that many medications are complementary and administered together, while other combinations are not used because of possible drug interaction. There-fore, a presence of one medication can often explain (predict) the presence or absence of another one.

Multivariate prediction

The goal of this experiment is to explore the benefit of combining information from multiple sources or features. Tables 1 and2 show AUC scores for prediction of top 10 highly predictive labs and medications from the linear SVM classifier. The classifier was trained on a subset of all features, in particular top 1, top 3 and top 30 best performing features in the training data. All results are reported on the independent test set.

We note that the feature selection for models with over 9000 feature candidates is an important and challenging problem and that the greedy selection applied in the experiment may not be the best one. However, this (somewhat limited) experiment indicates that a single feature is often a good predictor of the decision, suggesting simple patterns and their refinements may be able to capture well the prevalent lab order and medication order patterns.

Conclusions

Our univariate analyses of relations in between patient states and patient-management decisions revealed that the lab and medication order decisions are often driven by simple predictive patterns that involve more recent set of values, or times since the occurrence of some event (e.g. procedures, or previous lab/medication orders). Our (limited) analyses of more complex multivariate models suggest that lab and medication order decisions are likely based on only few clinical variables and their characteristics (features). In the future, we plan to further expand this study by analyzing feature dependencies and by developing more advanced feature selection for building multivariate predictive models.

Figure 1 .

 1 Figure 1.A segmentation of a patient case (Case A) to multiple patient state instances (A-1 to A-4) at 8:00am. Lab and medication orders for the following 24 hours are associated with each instance.

Figure 2 .

 2 Figure 2. A subset of temporal features generated for continuous valued lab tests.

  Last value: A Last value difference = B-A Last percentage change = (B-A)/B Last slope = (B-A) / (t B -t A ) Nadir = D Nadir difference = A-D Nadir percentage difference = (A-D)/D Baseline = F Drop from baseline = F-A Percentage drop from baseline = (F-A)/F 24 hour average = (A+B)/2 …

Figure 3

 3 Figure3summarizes the most influential category for lab order decisions. The categories considered are labs, medication, procedure, demographics, and support devices features. Clearly, the most influential predictors for lab orders are features derived from lab and procedures data. Briefly, the best predictors for the next lab order are past labs. Intuitively, the lab order decision is typically driven by the existence of previous abnormal value of the same or other lab, and time since this lab has been measured. Procedure features are important as the type of surgical procedure and the time elapsed since the procedure may prompt close monitoring of certain organ functions and hence corresponding lab orders.

Figure 3 .

 3 Figure 3. The importance of labs, meds, procedures, demographics and support device information for lab order decisions.

Figure 4 .

 4 Figure 4. The most influential temporal lab feature categories for predicting lab order decisions with the same lab features.

Figure 5 .

 5 Figure 5. The most influential temporal feature categories for predicting lab order decisions with other lab features.

Figure 6 .

 6 Figure 6. The importance of labs, meds, procedures, demographics, and support device information for medication commissions.

Figure 7

 7 Figure 7 breaks down the categories shown in Figure 6 and shows the top 10 most predictive features. For many medications the time since last procedure was the most predictive feature. For examples commissions of Papaverine could be most predicted (AUC= 95%) with the time that passed since the last Coronary Artery Bypass for that patient.

Figure 7 .

 7 Figure 7. The most important temporal lab features for predicting medication commissions.

Figure 8 .

 8 Figure 8. The importance of temporal features for predicting medication order decisions with other medication features.

  Finally, we describe the status of 4 different heart support devices: Extracorporeal Membrane Oxygenation (ECMO), Balloon counter pulsation, Pacemaker, and other Heart Assist Device. For each of them, we record a single feature which describes whether the device is currently used to support patient's heart function.Altogether, our dataset consists of 9,223 different features describing 30,828 patient states. As noted earlier, we use the patient state to evaluate our ability to predict 742 lab and medication order decisions.

	8:00	8:00	8:00	8:00
	Case A Heart Support Device Features
	orders
	Case A-1	order
	Case A-2		orders
	Case A-3			orders
	Case A-4

Table 1

 1

	AUC for linear SVM trained on top 1, 3 and 30 most
	predictive features, showing 10 highly predictive labs
		top 1	top 3	top 30
	GLU	87.46% 85.97% 87.73%
	TCPK	79.56% 81.38% 82.68%
	PPO2V	79.71% 79.70% 85.00%
	VANMCR	74.15% 79.60% 82.13%
	LD	79.22% 79.14% 82.69%
	HPA	83.54% 83.03% 84.97%
	RETAB2	75.83% 75.67% 81.89%
	TEGMA	75.91% 85.36% 84.76%
	TEGR	75.91% 85.35% 85.30%
	TEGALP	75.91% 85.38% 85.09%
	Table 2 AUC for linear SVM trained on top 1, 3 and 30 most
	predictive features, showing 10 highly predictive medications
		top 1	top 3	top 30
	Nitroglycerin	71.48% 79.50% 80.53%
	Papaverine	82.34% 83.83% 89.19%
	Ioversol	87.65% 88.58% 89.50%
	Aminocaproic	79.49% 79.39% 86.83%
	Aprotinin	80.67% 78.65% 85.99%
	Thiopental	76.40% 75.62% 85.30%
	Eptifibatide	87.22% 89.13% 89.75%
	Darbepoetin	86.22% 90.33% 88.85%
	Iodixanol	69.62% 87.99% 87.26%
	Vitamin K	85.87% 86.08% 86.61%

Acknowledgments

The research presented in this paper was funded by grants R21-LM009102-01A1 and 1R01LM010019-01A1. Its content is solely the responsibility of the authors and do not necessarily represent the official views of the NIH.