Julien Carme

Rémi Gilleron

Aurélien Lemay

Joachim Niehren

Interactive Learning of Node Selecting Tree Transducers ⋆

Keywords: Web information extraction, wrapper induction, grammatical inference, tree automata, monadic queries : Nstts and pNstts . . . . . . . . . Time . . . . . .

We develop new algorithms for learning monadic node selection queries in unranked trees from annotated examples, and apply them to visually interactive Web information extraction.

We propose to represent monadic queries by bottom-up deterministic Node Selecting Tree Transducers (Nstts), a particular class of tree automata that we introduce. We prove that deterministic Nstts capture the class of queries definable in monadic second order logic (Mso) in trees, which Gottlob and Koch (2002) argue to have the right expressiveness for Web information extraction, and prove that monadic queries defined by Nstts can be answered efficiently. We present a new polynomial time algorithm in Rpni-style that learns monadic queries defined by deterministic Nstts from completely annotated examples, where all selected nodes are distinguished.

.

We have implemented our interactive learning algorithm and integrated it into a visually interactive Web information extraction system -called Squirrel-by plugging it into the Mozilla Web browser. Experiments on

Search Results for: Bruss

Found 26 Total matches in 1.32067 seconds Score: 1 Name: Ingo Bruss First Entered: 03/07/96 Email: bruss@mach.uni/karsruhe.de Score: 1 Name: Trevor Bruss First Entered: 20/05/97 Email: bruss@pz621.inland.com Score: 1 Name: Trevor Bruss First Entered: 04/08/98 Email: bruss@virgo.valpo.edu machine learning techniques by tree views. Another is based on finite-state techniques [START_REF] Kosala | Information extraction from web documents based on local unranked tree automaton inference[END_REF][START_REF] Raeymaekers | Learning (k,l)-contextual tree languages for information extraction[END_REF]. This approach differs from ours in that it represents monadic queries by a local tree languages. Induction starts from learning algorithms from positive examples. For a more detailed comparison see Section 6.

In the present article -extending on Carme, Lemay, and Niehren (2004a) and [START_REF] Carme | Interactive learning of node selecting tree transducer[END_REF] -we combine features of both, machine learning techniques and visual specification. We define an interactive setting for inducing tree based wrappers. We are interested in machine learning techniques that can infer node selection queries in trees. We consider an Html document as a tree structure obtained by parsing the document. An example for a rendered Html document is given in Figure 1, and its parse tree in Figure 2. The Html document contains the email addresses of three persons, called Ingo Bruss, Trevor Bruss, and Trevor Bruss again, each of which is described in its own Html table. The names of these persons as well as their email addresses are contained in hyperlinks, which correspond to nodes of the parse tree that are labeled by tag A.

Suppose that we want to extract all email addresses in this Html document. With respect to the parse tree, this wish can be expressed by the monadic node selection query that selects all hyperlinks in the last row of a table. In XPath like notation (but with additional axes), this query can be defined as follows:

/descendant-or-self::TABLE/lastchild::*/descendant::A/child::* Start at the root, go downwards to a node labeled by TABLE, move to its last child, then move to some A-labeled offspring and finally select one of its children. The same query can be expressed by a conjunctive formula of first-order logic with one free node variable x:

{x | ∃x 1 ∃x 2 ∃x 3 . label TABLE (x 1 ) ∧ lastchild (x 1 , x 2 ) ∧descendant(x 2 , x 3 ) ∧ label A (x 3 ) ∧ child (x 3 , x)}
One might opt for a more precise query that further constrains the path from the TABLE to the A labeled node. For tree structures generated by the same search machine, however, such a refinements seem unnecessary to correctly select the informative nodes.

Another task of interest might be to extract all pairs of names and email addresses. This binary query can be expressed by a conjunctive firstorder formula with two free variables. In what follows, however, we will restrict ourselves to monadic queries. This is because most existing systems rely on monadic queries for treating more complex binary or n-ary cases [START_REF] Baumgartner | Visual web information extraction with lixto[END_REF][START_REF] Muslea | Hierarchical wrapper induction for semistructured information sources[END_REF][START_REF] Kosala | Information extraction from web documents based on local unranked tree automaton inference[END_REF].

We thus consider the problem of extracting sets of informative nodes in trees, that are generated homogeneously by some back-end database or search machine. We fix a formal query representation language and split the selection task into two subproblems:

1. find a representation of an appropriate monadic query for informative nodes in trees; here we want to use machine learning techniques, rather than manual query specification or programming. 2. answer the query in a tree: given a tree and a query definition, compute the set of nodes that the query selects in the tree.

Suitable query representation languages thus need to satisfy a number of constraints.

Expressiveness: All useful monadic queries should be definable in the chosen query representation language. Monadic second-order logic (MSO) is the yardstick for measuring the expressiveness of query languages for trees and thus wrapper language in information extraction from tree structured documents (Gottlob & Koch, 2002). It allows to define all regular node selection queries in trees, which is adequate for many information extraction tasks. Efficiency: We need efficient algorithms for answering monadic queries given a tree a representation of the query in our language. Learnability: The objective is to induce monadic queries from trees in some of the nodes are annotated that are to be extracted. In the simpler case, we consider completely annotated Web pages in which all nodes are annotated that are subject to extraction. Because complete annotation may be unfeasible, we also consider partial annotations. Therefore we need to consider the problem of learning monadic queries from completely or partially annotated trees.

In this article, we propose two new query representation formalisms for monadic queries that are based on tree automata, Node Selecting Tree Transducers ( Nstts) and Pruning Node Selecting Tree Transducers (pNstts).

We introduce Nstts and pNstts in Section 2, with the objective to illustrate the basic ideas and concepts related to tree automata for unranked trees and monadic queries by examples.

In Section 3, we show that these query representation languages satisfy some of the algorithmic learnability requirements. What we need is an efficient test to determine whether a tree automaton is functional and thus an Nstt, or cut-functional and thus a pNstt. The algorithm for cutfunctionality is elaborated in the appendix (Section A).

Our results on efficiency and expressiveness of Nstts and pNstts are postponed to the appendix as well (Sections B and C). There, we show that monadic queries defined by deterministic Nstts or pNstts can be answered efficiently with linear time combined complexity. We then show that this holds even though deterministic Nstts and pNstts capture the class of monadic queries definable in MSO. Both query languages Nstts and pNstts are thus unrestricted from the view point of expressiveness1 .

The subsequent sections are devoted to learning algorithms for node selection queries, that are represented by Nstts or pNstts. In Section 4, we present a new polynomial time algorithm in Rpni-style that we call tRpni which learns monadic queries defined by deterministic Nstts from completely annotated examples (for the target query). It relies on a subprocedure for testing membership to the class of Nstts, i.e. for testing functionality.

In Section 5, we model the interactive process of learning monadic queries as active learning in the style of [START_REF] Angluin | Learning regular sets from queries and counterexamples[END_REF], in order to measure the user's effort during the interaction. Only partially annotated trees are available in interactive Web information extraction. We solve this problem by using intelligent tree pruning heuristics and we present a practically feasible interactive learning algorithm for monadic queries defined by pNstts.

It relies on a sub-procedure for testing membership to the class of pNstts, i.e. cut-functionality.

Finally, Section 6 discusses the integration of our learning algorithms into visually interactive Web information extraction. We have implemented our core learning algorithm in OCaml and have turned it into a visually interactive Web information extraction system -called Squirrel-by integration into the Mozilla Web browser. Experiments on realistic Web documents confirm excellent quality with very few user interactions -annotations and corrections -during wrapper induction.

2 Node Selecting Tree Transducers: Nstts and pNstts Parse trees of Html or Xml documents are sibling ordered unranked trees whose nodes may have an unbounded list of children. In this section, we develop query representation languages for monadic node selection queries in unranked trees, that we will use for query induction by methods of grammatical inference. We rely on tree automata for unranked trees. We propose two kinds of tree automata, that we call node selecting tree transducers ( Nstts) and pruning node selecting tree transducers (pNstts).

We start with a gentle introduction to Nstts and pNstts, whose objective is to illustrate the basic ideas and concepts related to tree automata for unranked trees and monadic queries by examples. Algorithmic learnability aspects will be discussed in Section 3. Questions on efficiency and expressiveness for Nstts and pNstts are answered in the appendix (Sections B and C).

Monadic queries in unranked trees

Let N = {1, 2, . . .} be the set of natural numbers without 0 and B = {0, 1} be the set of Booleans. Let Σ be a finite set, the set of node labels, also called the signature.

An unranked tree over Σ is a finite tree with Σ-labeled nodes whose edges are totally ordered from the left to the right. An unranked tree t over Σ is a pair consisting of a label a ∈ Σ and a possibly empty list of unranked trees t 1 , . . . , t n : the following abstract syntax:

t ::= a(t 1 , . . . , t n )
where n ∈ N ∪ {0} and a ∈ Σ As a running example, we consider the following unranked tree with labels in Σ = {L, F , A, H , W }:

films = L(F (A, H ), F (A, W ), F (A, H ))
This tree represents a list (L) of three films (F), two of which are directed by Hitchcock (H) and one by Wenders (W). The letter (A) represents the

L F A H F A W F A H Figure 3
The unranked tree films = L(F (A, H ), F (A, W ), F (A, H )). We want to query for the actor lists (A) in the films by Hitchcock (H).

actor lists of these films (which would rather expand to a larger subtree in realistic examples). We draw trees as graphs, as for instance in Figure 3.

As in this example, we will systematically ignore textual contents of Html or Xml documents in this article. This design decision clearly simplifies our tasks, which nevertheless remains useful for practical applications to Web information extraction, as we will see.

We write nodes(t) for the set of nodes of a tree t. We identify a node with its relative address, so that nodes(t) ⊆ N * . The node 21, for instance, is the first child of the second child of the root. In our example tree films, this node is labeled by A. We write t(v) for the the label of some v ∈ nodes(t), for instance:

films(21) = A
We say that two trees have the same shape if they have the same set of nodes. This definition works, since we identify nodes with their relative address from the root.

Definition 1 A monadic query in unranked Σ-trees is a function q that maps unranked trees t over Σ to subsets of their nodes:

q(t) ⊆ nodes(t)
The function nodes itself, for instance, is a monadic query that maps a tree t to the set of all its nodes. A less trivial example is the query actors_hitchcock which asks for the set of all actor lists in films by Hitchcock. Applied to the example tree films, this query yields the following set of nodes:

actors_hitchcock (films) = {11, 31}
Each actor list of a Hitchcock film corresponds to some node labeled by A, that has a parent labeled by F , and a next sibling to the right that is labeled by H. Furthermore, the F -parent should belong to a list of films, so that its own parent is labeled by L and all its siblings by F .

Tree automata for unranked trees

Tree automata are machines that recognize sets of trees. Tree automata are traditionally developed for binary or ranked trees (Comon, Dauchet, Gilleron, Jacquemard, Lugiez, Tison, & Tommasi, 1997), and indeed, the situation gets different for unranked trees.

A large number of different automata notions for unranked trees and querying have been proposed recently. Besides so called unranked tree automata (UTAs) by [START_REF] Brüggemann-Klein | Regular tree and regular hedge languages over unranked alphabets: Version 1[END_REF] that are most popular in the database community [START_REF] Libkin | Logics over unranked trees: an overview[END_REF] and identical with the much earlier pseudo-automata by [START_REF] Thatcher | Characterizing derivation trees of grammars through a generalization of automata theory[END_REF], there are so called query automata [START_REF] Neven | Query automata over finite trees[END_REF], forest grammars of [START_REF] Neumann | Locating matches of tree patterns in forests[END_REF], automata on binary encodings of unranked trees (Frick, Grohe, & Koch, 2003) and the algebraic recognizably notion of stepwise tree automata by Carme, Niehren, and Tommasi (2004b).

With respect to query induction as proposed in this article, we need an automata notion for unranked trees that comes with a good notion of bottom-up determinism, so that the Myhill-Nerode theorem on minimization holds. [START_REF] Martens | On the minimization of XML schemas and tree automata for unranked trees[END_REF] discuss the available alternatives. They show that unique minimization fails for deterministic UTAs, and argue that stepwise tree automata yield smaller minimal automata than the inverted standard binary encoding (up to a linear factor depending on the size of the alphabet) and parallel UTAs [START_REF] Raeymaekers | Minimization of finite unranked tree automata[END_REF]Cristau, Löding, & Thomas, 2005). We thus choose to work with stepwise tree automata.

Stepwise tree automata can be understood as standard tree automata that operate on binary encodings of unranked trees (not the standard encoding however). This fact will come in handy for our more formal results on Nstts and pNstts in Section 3. In this section, however, we will use finite word automata syntax to present stepwise tree automata. Semantically, however, they behave such as tree automata. The relationship to standard tree automata will be clarified on need (in Section 3.2).

Definition 2 A stepwise tree automaton for unranked trees over Σ is a finite word automaton A with alphabet(A) = states(A) ⊎ Σ such that there is a unique initial state: initial (A) = {q I }.

if q 0 a → q ′ in rules(A) for some a ∈ Σ then q 0 = q I , and no transition q 1 q2 → q in rules(A) satisfies q = q I nor q 2 = q I . A run r of a stepwise tree automaton A on an unranked tree t labels the nodes of t by states of A. It is a function of type r : nodes(t) → states(A) that can be understood as a tree over states(A) having the same shape as t. Value r(v) is the state that run r assigns to node v ∈ nodes(t). If v has n children v1, . . . , vn then r(v) is a state obtained by running A on the following word:

t(v) r(v1) . . .

r(vn)

This word starts with the label of v in t and continues by the sequence of states that r assigns to the children of v. A run is successful if it maps the root of t to a final state of A. A stepwise tree automaton A accepts an unranked tree t if there exists a successful run of A on t. The language

6 4 5 3 1 2 F L 4,5 H W A 1 2 3 L 6 F 4 A 1 H 2 F 5 A 1 W 3 F 4 A 1 H 2
Figure 4 A stepwise tree automaton that accepts film lists, and the films tree annotated by a successful run of this automaton. State 6 of the root is obtained by evaluating the word L454 by the automaton.

L(A) of a stepwise tree automaton A is the set of all unranked trees that A accepts. An example for a stepwise tree automaton is given in Figure 4. This automaton accepts all lists containing films by Hitchcock and Wenders. The films tree annotated by a run of this automaton is drawn in Figure 4.

Definition 3 A stepwise tree automaton A is (bottom-up) deterministic, if it is a left-to-right deterministic finite automaton, i.e., for ever every q ∈ states(A) and a ∈ alphabet(A) there exists at most one q ′ in states(A) such that q a → q ′ belongs to rules(A).

What might be less clear at the time being is that every stepwise tree automaton can be determinized without altering its tree language, and that all regular languages of unranked trees are recognized by a unique minimal deterministic stepwise tree automaton (up to isomorphism). This will become obvious from the tree automata perspective adopted in Section 3.

Nstts for unranked trees

The next goal is to use stepwise tree automata in order to define monadic queries in unranked trees. There are many possibilities to do so, Nstts provide one of them, pNstts another. Two further methods will be discussed and used in Section B. An annotated tree over Σ is a tree over Σ × B. Every annotated tree can be decomposed into a product t × β between a Σ-tree t and a B-tree β of the same shape. For convenience, we will often write a b for pairs (a, b). For instance:

L(F (A, H )) × 0(0(1, 0)) = L 0 (F 0 (A 1 , H 0 ))
A completely annotated tree for a query q in Σ-trees is an annotated tree of the form:

t × q(t)
L0 6 F0 4 A1 1 H0 2 F0 5 A0 0 W0 3 F0 4 A1 1 H0 2
Figure 6 A deterministic Nstt defining the query actors_hitchcock and one of its successful runs.

for some Σ-tree t. Here, we freely consider the set q(t) as a B-tree of the shape of t, which relabels selected nodes of t to 1 and all others to 0. Examples for three completely annotated trees for the query actors_hitchcock are given in Figure 5.

The idea of Nstts is to represent a monadic query q by a tree automaton that recognizes the set of completely annotated trees for q except for some t × q(t) where q(t) = ∅. Such languages L of annotated trees are functional in that for every Σ-tree t there exists at most one Boolean tree β such that t × β ∈ L(A) (namely β = q(t)).

Definition 4 An Nstt over Σ is a stepwise tree automaton A over Σ × B that recognizes a functional language of annotated trees. Every Nstt A defines a monadic query q A such that for all unranked Σ-trees t:

q A (t) = {v | ∃B-tree β s.t. t × β ∈ L(A), β(v) = 1}
As example, we present in Figure 6 a deterministic Nstt that defines the query actors_hitchcock . Let us recall that we freely write a b instead of (a, b).

A query q is represented by an Nstt A if A defines the query q, i.e. q A = q. As we do not care about trees t such that q(t) = ∅, a query q may be represented by several Nstts. Two Nstts A and A ′ are said to be equivalent if q A = q A ′ .

Pruning Nstts for unranked trees

One of the disadvantages of Nstts is that they need to model all subtrees, even those that are irrelevant for node selection. The Nstt in Figure 4, for instance, has rules to recognize films that are not directed by Hitchcock (but by Wenders). In Web information extraction, such information is typically not available or difficult to learn from the very few given examples.

We propose pNstts to solve this problem. These are machines that operate like Nstts except they first prune trees non-deterministically and then select nodes from the pruned tree. This way, they are able to ignore all pruned subtrees.

Let T be a special constant, that we use to mark leaves in pruned trees where complete subtrees have been cut off. A pruned tree over a signature Σ is an unranked tree over the signature

Σ T = Σ ∪ {T}
whose inner nodes are labeled in Σ. Only leaves of pruned trees may be labeled by T. For every Σ-tree t, let cuts(t) be the set of Σ T -trees obtained by pruning some subtrees of t, i.e., by substituting some complete subtrees of t by T. Two pruned trees t 1 and t 2 are said to be compatible if they can be obtained by pruning from some common third tree, i.e., if there is a tree t such that t 1 , t 2 ∈ cuts(t).

See Figure 7 for some examples of pruned annotated trees, which have the signature (Σ × B) T . It will be convenient to identify pruned annotated trees over (Σ ×B) T with trees over (Σ ×B)⊎{T T }, i.e., we implicitly identify T with the pair (T, T) which is T = T T . This permits us to decompose all trees over (Σ × B) T into products t × β of trees t over Σ T and trees β over B T . Intuitively, the annotation of T by T means that we don't know whether nodes in pruned subtrees will be selected or not.

We call a language L of (Σ × B) T -trees cut-functional if for all t 1 × β 1 , t 2 × β 2 ∈ L such that t 1 and t 2 are compatible, it holds that β 1 and β 2 are compatible. This means that different prunings t 1 and t 2 of the same third tree t will never carry contradictory information. A Σ T -tree t is called unpruned if T does not occur in the set of node labels used by t. Note that cut-functional languages of unpruned trees (and thus with signature Σ ⊎ B) are functional.

Consider for instance the two annotated prunings of films in Figure 7. Their Boolean annotations are compatible in that both of them require the root to be unselected. For all other nodes, there exist no overlapping annotations. The fact that the left-most (resp. right-most) A-node is to be selected is available on the left-most (resp. right-most) pruning only.

L0 6 F0 4 A1 1 H0 2 T 7 T 7 L0 6 T 7 T 7 F0 4 A1 1 H0 2 Figure 9
Two runs of different prunings of films by the pNstt in Figure 8. Each of them selects one of the A-nodes in Hitchcock's films.

Definition 5 A pNstt over Σ is a tree automaton over (Σ × B) T whose language is cut-functional. Every pNstt A defines the query q A such that for all Σ-trees t:

q A (t) = {v ∈ nodes(t) | ∃ t ′ ∈ cuts(t), ∃β ′ : t ′ × β ′ ∈ L(A), β ′ (v) = 1}
The nodes of q A (t) can thus be computed non-deterministically, by guessing a pruning of t ′ of t and inspecting the Boolean annotation β ′ such that t ′ × β ′ ∈ L(A), which is unique by cut-functionality if it exists.

A deterministic pNstt that recognizes the actors lists of Hitchcock's films is given in Figure 8. Indeed, it leaves the structure of all films by other directors than Hitchcock undefined, since these can be pruned to T.

A query q is represented by a pNstt A if A defines the query q, i.e. q A = q. A query q may be represented by several pNstts.

Testing Functionality in Polynomial Time

Queries defined by Nstts and pNstts have three important algorithmic or descriptive properties that render them suitable for interactive query induction.

Membership: whether a deterministic tree automaton over Σ × B is functional, and hence an Nstt can be decided in polynomial time. Whether a tree automaton over (Σ × B) T is cut-functional and thus a pNstt can be decided in polynomial time. Efficiency: monadic queries defined by Nstts or pNstts can be answered in polynomial time Expressiveness: deterministic Nstts can express all monadic second order definable monadic queries, as well as deterministic pNstts.

In this section, we prove the first property, by presenting efficient algorithms for membership testing, on which our learning algorithms will rely. Efficiency will be treated in Section B. It is fundamental because correctness of the hypothesis Nstt or pNstt must be checked frequently in the interactive setting. Also, an information extraction program must be efficient. Expressiveness will be treated in Section C. We show that deterministic Nstts and pNstts can express all MSO-definable queries. The learning algorithm for Nstts will be able to infer all MSO-definable queries, when given enough examples (which is unrealistic in practice). The choice of a practical pruning function will restrict the class of learnable queries by the learning algorithm of pNstts.

Tree automata for binary trees

Properties depending on determinism and functionality are easier to establish for standard tree automata on binary trees. As we will show, they can be lifted to stepwise tree automata by exploiting a particular binary encoding of unranked trees, called Currying in (Carme et al., 2004b). Note that the notion of determinism for tree automata on unranked trees works out smoothly for stepwise tree automata in contrast to more standard notions of tree automata for unranked trees [START_REF] Martens | On the minimization of XML schemas and tree automata for unranked trees[END_REF].

Standard tree automata (Comon et al., 1997) are traditionally defined for binary trees, i.e., unranked trees where every node has either no or exactly 2 children. For sake of simplicity, we will develop our algorithms for binary trees, and then lift them to unranked trees via binary encoding.

A tree automaton A for binary trees over some signature Σ consists of a finite set states(A), a subset final (A) ⊆ states(A), and a set of rules of two kinds where a ∈ Σ and p, p 1 , p 2 ∈ states(A).

a → p instead of p a(p 1 , p 2 ) → p instead of p a a p 1 p 2
Standard tree automata can be seen as particular stepwise tree automata, except that they decompose binary rules into three steps. As a consequence, the notions of runs, successful runs, and accepted tree languages carry over immediately. We write runs A (t) for the set of runs of automaton A on tree t and succ_runs A (t) for the subset of successful runs. The notion of bottom-up determinism carries over from stepwise to standard tree automata, too. A tree automaton is bottom-up deterministic if none of its rules have the same left hand side. It is well known that every standard tree automaton can be determinized without affecting its tree language. Further notions that carry over to binary trees without any changes are functionality, cut-functionality, Nstts, and pNstts.

L F A H F A W F A H curry =⇒ @ @ @ L @ @ @ H W H @ @ @ F A F A F A Figure 10
Curried binary encoding: curry(L (F (A,H ),F (A,W ),F (A,H ))) = L @(F @A @H )@(F @A @W )@(F @A @H ).

Binary encoding of unranked trees

We next relate deterministic stepwise tree automata for unranked trees to deterministic standard tree automata over binary trees. This shows that subsequent learnability results for deterministic standard tree automata can be lifted to deterministic stepwise tree automata. The base idea is to encode unranked trees into binary trees by using Currying. The better known first-child next-sibling encoding fails to do this job; it does not preserve determinism. Some more care is needed when determinizing stepwise tree automata. The usual determinization algorithm for finite automata fails since it alters the tree language of a stepwise tree automaton. Instead, a stepwise tree automaton needs to be understood as a standard tree automata operating on Curryied encodings. Determinisation for standard tree automata is then doing the job.

For applying Currying we consider unranked trees as lambda terms. The term L(F , F , F ) for instance, is a lambda term that describes the application of function L to a triple of arguments. Its Curried encoding is the binary tree (((L@F )@F )@F ) which describes the application of function L to its arguments stepwise one by one. The Curried binary encoding of the unranked tree films is displayed in Figure 10.

Stepwise tree automata A over Σ can be understood as syntax for standard tree automata A b for binary trees over Σ ⊎ {@}, which operates on Curried binary encodings of unranked trees. The translation is as follows, where a ∈ Σ and p 0 ∈ initial (A), and p 1 , p 2 , p ∈ states(A)initial (A):

p 0 a → p ∈ rules(A) iff a → p ∈ rules(A b ) p 1 p2 → p ∈ rules(A) iff @(p 1 , p 2 ) → p ∈ rules(A b )
The translation of the stepwise automaton in Figure 4 is given in Figure 11. Generally, it holds that:

A is deterministic ⇔ A b is deterministic.
This follows immediately from the definitions. As an immediate consequence, it follows that every stepwise tree automaton can be determinized.

Labels: {@, A, H , W , F , L} States: {1, 2, 3, 4, 5, 6, 8, 9} Rules: A → 1 @(8, 1) → 9 H → 2 @(9, 2) → 4 F → 8 @(6, 4) → 6 L → 6 @(6, 5) → 5 W → 3 @(9, 3) → 5 @(6, 5) → 6 Final: {6} @ 6 @ 6 L 6 @ 4 @ 5 H 2 W 3 @ 9 @ 9 F 8 A 1 F 8 A 1
Figure 11 A standard tree automaton for binary encodings of film lists, corresponding to the stepwise tree automaton in Figure 4.

Furthermore, the language of both automata correspond modulo Currying, i.e., for all unranked trees t over Σ ⊎ {@}:

t ∈ L(A) ⇔ curry(t) ∈ L(A b )
This is because both automata produce runs that correspond precisely except for intermediate results stored in @-labeled nodes (which could be annotated to the edges of unranked trees). Since states(A b ) = states(A)initial (A), it also follows that there exists unique minimal deterministic stepwise tree automata for all regular languages of unranked trees.

The correspondence lifts to monadic queries defined by Nstts or pNstts even though this needs a little care. An Nstt A over Σ is a tree automaton over Σ ×B, so that A b is an automaton over (Σ ×B)⊎{@}. Unfortunately, A b is not an Nstt over Σ × {@}, but this problem can be resolved by replacing @ by @ 0 , which means that we do not want to extract any auxiliary nodes introduced by the binary encoding, which is of course consistent with our intuition. Modulo the equation @ = @ 0 it holds for every tree automaton A over Σ × B, and Σ-tree t:

A is functional ⇔ A b is functional q A (t) = q A b (curry(t))
Hence, A is an Nstt for unranked trees over Σ if and only if A b is an Nstt for binary trees over Σ ⊎{@}, and that both automata define the same query modulo the natural correspondence between nodes in unranked trees to leafs in binary encodings. As a consequence, we can reduce functionality testing and Nstt query answering on unranked trees to the respective problems on binary trees. The same arguments carry over to pNstts without any further changes. Modulo the equation @ = @ 0 it holds for every tree automaton A over (Σ × B) T , and Σ-tree t:

A is cut-functional ⇔ A b is cut-functional q A (t) = q A b (curry(t))

Testing functionality and cut-functionality

We next show how to test whether a tree automaton for binary trees over Σ × B is functional. As argued above, this is sufficient to solve the same problem for unranked trees We reduce functionality testing to unambiguity testing, a problem for tree automata that can be solved in polynomial time [START_REF] Seidl | On the finite degree of ambiguity of finite tree automata[END_REF].

A tree automaton is unambiguous if it permits at most one successful run per tree. Note that every deterministic tree automaton is unambiguous, since it permits at most one run per tree, may it be successful or not.

The projected automaton π(A) over Σ has states(π(A)) = states(A) × B, final (π(A)) = final (A)×B, and the rules are given by the following inference scheme where a ∈ Σ and b, b 1 , b 2 ∈ B:

(a, b)(p 1 , p 2 ) → p ∈ rules(A) a((p 1 , b 1 ), (p 2 , b 2 )) → (p, b) ∈ rules(π(A)) (a, b) → p ∈ rules(A) a → (p, b) ∈ rules(π(A)) Lemma 1 r ∈ runs A (t × β) iff r × β ∈ runs π(A) (t).
Lemma 2 A deterministic tree automaton A over Σ × B is functional and thus an Nstt if and only if its projection π(A) to Σ is unambiguous.

Proof For the one direction, let A be a deterministic Nstt. Suppose

r 1 × β 1 , r 2 × β 2 ∈ succ_runs π(A) (t) for some t ∈ tree Σ . Lemma 1 yields r 1 ∈ succ_runs A (t × β 1 ) and r 2 ∈ succ_runs A (t × β 2 ). The functionality of A implies that t × β 1 = t × β 2 and thus β 1 = β 2 . The unambiguity of A yields r 1 = r 2 so that r 1 × β 1 = r 2 × β 2 . This proves that π(A) is unambiguous.
For the converse, assume that π(A) is unambiguous and suppose t ×

β 1 , t×β 2 ∈ L(A). Let r 1 ∈ succ_runs A (t×β 1 ) and r 2 ∈ succ_runs A (t×β 2 ). Lemma 1 yields r 1 × β 1 , r 2 × β 2 ∈ succ_runs π(A) (t). The unambiguity of π(A) implies β 1 = β 2 , i.e., L(A) is functional.
Proposition 1 Whether a deterministic tree automaton over Σ ×B is functional and hence an Nstt can be tested in cubic time.

It is sufficient to prove this proposition for standard tree automata over binary trees, so that it carries over to stepwise tree automata for unranked trees.

Proof Let A be a deterministic tree automaton over Σ × B. By Lemma 2 it is sufficient to compute the Σ-projection π(A) and to test whether this automaton is unambiguous. This can be done in cubic time.

It remains to show that we can equally decide membership to the class of deterministic pNstt in polynomial time. This is stated by the following proposition that is proved in Section A.

Proposition 2 Cut-functionality of deterministic pNstts can be tested in cubic time.

Learning Nstts from Completely Annotated Examples

We have shown that monadic node selection queries can be represented by deterministic Nstts which are tree automata. It is known that regular tree languages represented by deterministic bottom-up tree automata are learnable from polynomial time and data [START_REF] Oncina | Inference of recognizable tree sets[END_REF]. But this result holds only when positive and negative examples are available, i.e. trees belonging to the target language or not. In our query learning framework, however, completely annotated trees for the target query will be available instead. These express a number of positive and implicit negative examples. We will prove in this section that monadic node selection queries represented by Nstts are learnable from polynomial time and data, provided that the data contains completely annotated examples for the target query. The difficulty is to show, that completely annotated examples are indeed equivalent to arbitrary samples of positive and negative examples.

Identification from polynomial time and data

We recall the learning model from polynomial time and data (Gold, 1967(Gold, , 1978;;de la Higuera, 1997), and adapt it to the problem of tree language inference using deterministic tree automata. An example is a couple (t, b) where t is a tree and b is its Boolean label. Positive examples are labeled by 1 and negative examples by 0. A (tree) sample is a finite set of examples. A tree automaton A is compatible with an example (t, b) if (t ∈ L(A)) ⇔ b, it is compatible with a sample if it is compatible with all its examples. We also say in this case that the sample is consistent with A. The size of a sample is the total number of nodes of all trees in the sample.

Definition 6 Tree languages represented by a class of tree automata C are said to be identifiable from polynomial time and data if there exist two polynomials p 1 and p 2 and an algorithm learner such that:

with as input a sample S of size m, learner returns a tree automaton A ∈ C compatible with S in O(p 1 (m)) time; -for each tree automaton A ∈ C of size n, there exists a sample -called the characteristic sample for Achar (A) of cardinality less than p 2 (n) such that, with input a sample S that contains char (A), learner returns a tree automaton A ′ ∈ C equivalent with A.

Regular tree languages represented by deterministic tree automata are identifiable from polynomial time and data [START_REF] Oncina | Inference of recognizable tree sets[END_REF]. In the sequel of the paper we mainly use the existence of a polynomial time learning algorithm learner . It is set to be the Rpni algorithm for deterministic tree automata which is defined in [START_REF] Oncina | Inference of recognizable tree sets[END_REF] as an extension of the Rpni algorithm for deterministic string automata [START_REF] Oncina | Inferring regular languages in polynomial update time[END_REF].

The reader should note that the model for tree languages differs from the model for string languages on one important point: it is required that the cardinality of the characteristic sample is polynomial in the size of the target automaton whereas for string languages it is required that the size of the characteristic sample is polynomial in the size of the target automaton. This is of course weaker and due to the fact that the size of trees -measured as the number of nodes -in the characteristic sample can be exponential. Indeed, consider the tree language containing a single balanced binary tree of height n on the alphabet Σ = {a, f } where a is a constant and f a binary symbol. The characteristic sample must contain this tree which has 2 n+1 -1 nodes while the corresponding tree automaton has only n + 1 states. This blow-up is indeed due to the intrinsic nature of trees. This problem could be solved with a new representation schema for trees in the characteristic sample: represent a tree by a deterministic automaton recognizing the language reduced to this unique tree. The proof is out of scope of the paper because we will only consider the learner defined with the Rpni algorithm presented in [START_REF] Oncina | Inference of recognizable tree sets[END_REF].

The learning model for tree languages is not well suited for node selection queries in trees. We can represent a node selection query by a regular tree language over Σ × B. But, for learning node selection queries, only completely annotated trees for the target query will be available. Thus, if q is the target query, only positive examples (t × q(t), 1) will be available. We will refer to them as completely annotated examples. Also, negative examples are useless as they can be deduced from completely annotated ones: for a completely annotated example t × β, every other annotated tree t × β ′ (β ′ = β) is negative. Two query representations are equivalent if they represent the same query. This leads to the following definition: Definition 7 Node selection queries represented in a class of automata C are said to be identifiable from polynomial time and data from completely annotated examples if there exist two polynomials p 1 and p 2 and an algorithm learner such that:

for all sets S of annotated trees of size m, learner (S) returns a query representation A ∈ C in time O(p 1 (m)) such that q A is compatible with S; -for all automata A ∈ C of size n, there exists a set of completely annotated examples for q A -called the characteristic sample for Achar (A) of cardinality less than p 2 (n) such that, for every sample S that contains char (A), learner (S) returns an automaton A ′ ∈ C such that q A = q A ′ .

We will simply talk of identifiability when we do not impose polynomial constraints.

tRpni: an Rpni extension for deterministic Nstts

We now want to prove that node selection queries represented by deterministic Nstts are identifiable from polynomial time and data. We first show that one can easily deduce identifiability of node selection queries represented by deterministic Nstts in this framework from the previous result of identifiability of tree languages represented by deterministic automatapolynomial constraints set aside.

Note that the proof presented here leads to an exponential time algorithm -as we will have to enumerate explicitly all negative examples induce by a functional set of completely annotated examples. Polynomiality can nevertheless be reached by using functionality directly. This leads us to a new variation of the learning algorithm Rpni which can identify node selection queries represented by Nstts.

Lemma 3 Node selection queries represented by deterministic Nstts are identifiable from completely annotated examples.

Proof First note that annotated tree languages represented by deterministic Nstts are identifiable as they are deterministic tree automata over Σ × B. Let learner be an algorithm according to Definition 6 and let char be a function that computes the characteristic sample for any deterministic tree automaton over Σ × B according to Definition 6.

To prove the lemma, we have to show that we can infer an Nstt defining the target query from completely annotated examples. A completely annotated example t × β for a query q defines a positive example (t × β, 1) and negative ones (t × β ′ , 0) for all β ′ = β. Thus, we define a function pn that takes as an input a set S of annotated trees and outputs a sample over

Σ × B. pn(S) = {(t × β ′ , b) | t × β ∈ S, b ⇔ (β = β ′ )} ∪ {(t × ∅, 0) | t ∈ T Σ )
We next define learner ′ and char ′ in the following manner:

learner ′ (S) = learner (pn(S)) L q = {t × q(t) | q(t) = ∅} char ′ (q) = {t × β ∈ L q | (t × β ′ , b) ∈ char (L q )}
First note that char ′ (q) is a set of completely annotated examples for q. Second, we show that char (L q ) ⊆ pn(char ′ (q)).

-For positive examples (t × β ′ , 1) ∈ char (L q ), we have t × β ′ ∈ L q and thus t × β ′ ∈ char ′ (q), so that (t × β ′ , 1) ∈ pn(char ′ (q)). -For negative examples, lets assume that (t×β ′ , 0) ∈ char (L q ). If q(t) = ∅ then t × q(t) ∈ L q and thus t × q(t) ∈ char ′ (q). Furthermore, β ′ = q(t) so that (t × β ′ , 0) ∈ pn(char ′ (q)).

Let q be a node selection query and S ⊇ char ′ (q) a sample consistent with L q . Then pn(S) ⊇ char (q) and pn(S) consistent with L q . As learner identifies regular tree languages represented by deterministic tree automata over Σ × B, learner (pn(S)) = learner ′ (S) outputs a deterministic tree automaton A such that L(A) = L q , as required for identifying queries represented by Nstts.

The functions learner ′ and char ′ witness that monadic queries representable by deterministic Nstts can be identifed for completely annotated examples (but not yet from polynomial time and data).

Our next objective is to adapt the functions learner ′ and char ′ in the previous proofs, in order to establish identifiability of Nstt-queries from polynomial time and data. There are two problems. First, algorithm learner ′ computes the set of implicit examples pn(S) induced by functionality, which may be of exponential in cardinality compared to S. This problem be solved by an alternative learning algorithm that always test the current automaton for functionality, rather than testing for consistency w.r.t. negative examples in pn(S). And fortunately, functionality can be tested in P-time for deterministic automata over Σ × B. Second, we need to show for all Nstts A that the sample char ′ (q A ) is always of polynomial cardinality in the size of A. This is the case, since we can compute in polynomial time another Nstt recognizing L qA , so that L qA is definable by some deterministic Nstt of size polyomial in that of A.

Theorem 1 Monadic node selection queries represented by deterministic Nstts are identifiable from polynomial time and data from completely annotated examples.

Proof First, let us recall the Rpni-algorithm [START_REF] Oncina | Inference of recognizable tree sets[END_REF][START_REF] Oncina | Inferring regular languages in polynomial update time[END_REF][START_REF] Lang | Random DFA's can be approximately learned from sparse uniform examples[END_REF]. Rpni inputs a sample S of positive and negative examples. It first computes a deterministic automaton which recognizes the set of positive examples in the sample called the initial automaton and denoted Nstt(S) -it is the largest deterministic tree automaton that recognizes exactly S. It then merges states exhaustively in some fixed order. A merging operation applies to the recent deterministic automaton A and two states q 1 , q 2 ∈ states(q) and returns a deterministic automaton det-merge(A, q 1 , q 2 ). A deterministic merge is a merge followed by recursive merges needed to preserve determinism. For example, merging q 1 and q 2 in an automaton with rules f (q 1 ) → q 3 and f (q 2 ) → q 4 requires merging q 3 with q 4 . A merging operation is licensed only if det-merge(A, q 1 , q 2 ) is consistent with all negative examples in the sample. The algorithm tRpni (described in Figure 12) behaves as Rpni except that it checks differently whether deterministic merging operation are licensed. It tests whether the language L of det-merge(A, q i , q j ) is functional and whether L ∩ {t × ∅ | t} = ∅. It thereby avoids to enumerate implicit negative examples. It checks functionality in polynomial time in the automaton size (Proposition 1), at this at most quadratically many times. Also, as the Nstt should not recognize trees that has no selectionned elements, we remove those trees (kept in a set N ), and the algorithm has to check that the language π Σ (L) ∩ N = ∅. Therefore:

-The polynomial time condition for learner equal to tRpni is satisfied.

Consistency with the input sample is also given: by construction, the inferred automaton always recognizes trees of S.

tRpni(S) -The characteristic set of completely annotated examples is given in the proof of Lemma 3. Given an Nstt A such that q = q A we first compute another automaton à so that L( Ã) = L q . This can be done in polynomial time in the size of A, by intersecting A with an automaton recognizing {t × β | t ∈ T Σ , β = ∅}. We then compute char (L q ) in polynomial time from Ã, and char ′ (q) in polynomial time from char (L q ). It follows that the cardinality of char ′ (q) is polynomial in the size of A. Furthermore, given any sample S containing char ′ (q), tRpni(S) behaves as the algorithm learner ′ (S) described in this lemma (except that it does not explicitly enumerate negative examples) and therefore induces the target Nstt. The polynomial cardinality of the characteristic set of annotated trees is guaranteed by the polynomial cardinality of the characteristic sample of the target Nstt.

N = {t ∈ S | t × β ∈ S, β = ∅} A ← Nstt({t × β | t × β ∈ S, β = ∅}) For i = 1 to |states(A)| do For j = 0 to i -1 do A ′ ← det-merge(A, qi, qj) If A ′

Interactive Learning of pNstts

The above framework has two main drawbacks:

completely annotated examples are required, which may be a problem in practical cases where sometimes hundreds of nodes would have to be selected by the user. Therefore, one should deal with examples that are only partially annotated. -Furthermore, it does not take into account the interactions between the user and the algorithm. The user does not simply provide a set of annotated examples. He should for example be able to give some annotations to the algorithm in order to have a candidate query that he could then correct if he is not happy with its behaviour.

To take into account those two points, a new learning model has to be defined. We present here the active learning model. The Squirrel system that we develop here is a learning algorithm for monadic node selection queries in this framework that allows the user -presented here as an oracle -to interact with a core learning algorithm, which will be a variant of tRpni able to deal with partial annotations.

Active Learning Model

Deterministic finite automata are learnable in the MAT model [START_REF] Angluin | Learning regular sets from queries and counterexamples[END_REF], i.e., by an active learner who may ask membership and equivalence queries to his teacher. This result extends to deterministic bottom-up tree automata [START_REF] Sakakibara | Learning context-free grammars from structural data in polynomial time[END_REF]Drewes & Hogberg, 2003). Such queries, however, are not well suited for active learning of node selection queries in trees. Indeed, a node selection query may be represented by a regular tree language over Σ × B. Thus, a membership query would need as input an annotated tree which is not manageable in practice. Moreover, a membership query answers yes or no whether the annotated tree is correctly annotated, but, if the answer is negative, a membership query gives no information on the annotation error. Also, recall that a monadic query can be represented by several languages of annotated trees. Therefore equivalence of tree languages is not adapted for equivalence of monadic node selection queries.

We introduce two new types of queries that the learner may ask to the teacher, correct labeling queries ( Clqs) and query equivalence queries ( Qeqs). This can be done with respect to an arbitrary formalism for representing queries -for instance by Nstts. We denote query representations by A and the query they represent by q A . A Clq about target q is defined as follows:

Input:

an annotated Σ × B-tree t × β Output: yes if q(t) = β, else some node v ∈ nodes(t) such that β(v) = q(t)(v)

Correct Labeling Query (Clq)

A Clq asks whether the current annotation hypothesis t × β is correct and requires a failure witness v otherwise. A Qeq about target q has the form:

Input:

a query representation A Output: yes if q = q A , else some Σ-tree t s. t. q A (t) = q(t).

Query Equivalence Query (Qeq)

A Qeq asks whether the current query hypothesis A is correct, and requires a failure witness t otherwise.

Before presenting the main result, let us discuss about queries in practice. The user (or query designer) plays the role of the oracle. This is not a problem for Clq: the user can check on the current web page if it is well annotated and correct it otherwise. This may however be a problem for Qeq. We do not want to show the inferred Nstt to the user, as we want a "black-box" system usable even for non-expert users. The only thing that the user can check is whether the inferred query annotates correctly web pages that he proposes. The user simply answers "yes" to the Qeq (by actually stopping the learning process) when he is satisfied with the behavior of the proposed query on web pages processed so far. The possible consequence is that this query may not behave correctly on some unseen web pages, especially web pages that have a general design which is different to the one of processed web pages. Solutions to this problem are discussed in Section 6 and in the conclusion. Nevertheless Qeqs and Clqs allow to define a rigorous framework for interactive learning of monadic queries. We have the following result:

Theorem 2 Monadic node selection queries represented by deterministic Nstts are learnable in polynomial time by active learning processes with correct labeling queries and query equivalence queries.

Proof Let q be the target query and L be a target functional language over Σ × B defining q. Let A be a learning algorithm with membership and equivalence queries for deterministic tree automata. At each call of A to a membership query t × β ∈ L, we ask the correct labeling oracle with input t × β and answer yes if the Clq answers yes and no if the Clq outputs a node. At each call of A to an equivalence query, we ask the query equivalence query oracle with the same hypothesis tree automaton and answers yes if the Qeq outputs yes. If the Qeq outputs a Σ-tree t, we have to construct the annotated tree t × β which is a counterexample for the equivalence query. To do so, ask the correct labeling oracle until we get the annotated tree t × β. The reader should note that the number of calls to the correct labeling oracle is bounded by the number of nodes to be selected in t. The modified algorithm is a learning algorithm with Clqs and Qeqs. It outputs in polynomial time a minimal tree automaton A of the functional language L, i.e. a deterministic Nstt defining the target query q.

The Squirrel Algorithm

The outer loop of the Squirrel algorithm in Figure 13 halts when the teacher considers the current query to be equivalent to the target query.

Otherwise a new tree is investigated. The inner loop halts when the teacher confirms that the current tree is correctly annotated by the current hypothesis query. Otherwise, it asks for further partial annotations for the current tree and learns from them.

A partially annotated tree over Σ is a triple t, p + , p -consisting of a tree t, a set p + ⊆ nodes(t) of positively annotated nodes, a set p -⊆ nodes(t) of negatively annotated nodes, and p + ∩p -= ∅. It is consistent with a query q if p + ⊆ q(t) and p -∩ q(t) = ∅. Squirrel is parametrized by an arbitrary algorithm Rpni prune , which we will fix later on to be a variant of the tRpni algorithm for Nstts. However, we could use every other algorithm that computes query representations from a set S of (completely) annotated trees (the set of correctly annotated trees seen so far) and a partially annotated tree t, p + , p -(the tree for which the teacher is answering Clq queries).

Pruning

In order to be able to benefit from partial annotations, we propose to prune subtrees that seem irrelevant for distinguishing positively annotated nodes. All remaining nodes are assumed to be unselected if not annotated positively (which seems reasonable for appropriate pruning heuristics). Thereby, we obtain complete annotations on pruned trees. Note that negatively annotated nodes may be pruned. This complicates the situation a little, as wrapper induction needs to ensure consistency with all negative annotations, pruned or not.

At the same time, pruning helps resolving the second drawback because the size of the target automaton is reduced. The idea is similar to that of windowing in wrapper induction from texts (see e.g. (Freitag & Kushmerick, 2000;Chidlovskii, 2001)).

tRpni with Pruning

The learning algorithm Rpni prune in Figure 14 is parametrized by a pruning function prune, which is an arbitrary function mapping Σ × B-trees to (Σ × B) T -trees such that for every possible argument t:

prune(t) ∈ cuts(t)
First, we prune all input trees in S and the partially annotated input tree t, p + , p -. This is done by computing a completely annotated tree t × p + in which all nodes of p + are labeled by 1 and all others by 0, to which prune is then applied. Let S ′ be the resulting set of completely annotated pruned trees.

Second, Rpni prune infers a pNstt by a variant of the tRpni algorithm which tests for cut-functionality. It starts with an initial pNstt for S ′ , denoted by pNstt(S ′ ), as usual with Rpni. This is the deterministic pNstt whose language consists of all pruned trees in S ′ , such that for all states q ∈ states(pNstt(S ′ )) there exists exactly one tree t over (Σ × B) T with a successful run by A. Then, we use a state merging for generalization. The function det-merge takes as input an automaton A and two states q i and q j of states(A) and outputs an automaton where q i and q j are merged such that det-merge(A, q i , q j ) is made deterministic.

The iteration continues with the merged automaton if it is cut-functional and consistent with all negative annotations in S and t, p + , p -, or else refuses the merging step and continues with the previous automaton. Consistency here means that there does not exist any tree t ′ × β ∈ S and node v ∈ q A (t ′ ) such that β(v) = 0, and there does not exist any node v ∈ p - such that v ∈ q A (t).

Improvements. The most classical one is to tweak the merging order, as illustrated by evidence driven state merging [START_REF] Lang | Results of the abbadingo one DFA learning competition and a new evidence-driven state merging algorithm[END_REF]. Here, we choose a merging order which favors merges leading to pNstts with "horizontal" recursion, since this type of recursion is more frequent in semi-structured documents. The second improvement is to use background knowledge in form of typing automata (Kermorvant & de la Higuera, 2002). For web documents, we use a very general typing automaton that recognizes all well-formed web documents. Merges between states of different types are forbidden. This restricts the class of pNstts that can be inferred.

To conclude, the reader should note that Rpni prune responds in polynomial time (as tRpni and Rpni). As the cut-functionality of a tree automaton A can be tested in O(|A| 3 ) (see Proposition 2), which is the most complex task of the inner loop, and as this test has to be performed a quadratic amount of time, the overall complexity of tRpni is O(|S| 5 ) (at worst, the working automaton is always the initial automaton, which has a size at worst equal to the size of the input sample). Note that we consider here the size of an automaton as the sum of its number of node and its number Rpniprune (S, t, p+, p-) Figure 15 The pruned trees applying the strategy paths_only (left) and paths_extended (right) to the tree films of rules, and the size of a sample as the total number of nodes of trees in the sample. For large trees and a strongly pruning function there would be a speed-up of the learning process. However there is a trade-off in that we loose completeness in learnability. We discuss this last point in the next subsection.

// prune all input trees // S ′ = {prune(t ′ × β) | t ′ × β ∈ S, β = ∅} ∪ prune(t × p+) // compute a deterministic pNstt by Rpni// A ← pNstt(S ′ ) For i = 1 to |states(A)| do For j = 0 to i -1 do A ′ ← det-merge(A, qi, qj) If A ′ is cut-functional and A ′ consistent

Pruning Heuristics

The choice of the pruning function determines the quality of Rpni prune . To be able to learn a target query, some conditions should be imposed on the pruning function. Namely that it should be possible to find a characteristic pruned set for the target language, given the pruning function. And that it should be possible to find a cut-functional pruned language satisfying the target, for a given pruning function. Therefore the class of learnable functions depends on the pruning function. The time complexity of the learning algorithm is measured w.r.t. the size of pruned trees. Thus, the more aggressive the pruning function is, the more efficient the learning algorithm will be. Generally, we will only consider pruning functions that keep all positively annotated nodes. We have considered three pruning strategies:

-The function paths_only cuts all nodes except those that are ancestors of or equal to positively labeled nodes. An example is given in Figure 15. Note that more than a single path is kept so that induction is not simply reduced to learning path expressions. The problem of defining the class of Nstts that can actually be identified by Rpni prune with the pruning function paths_only is still open. The experiments show that pruning by paths_only yields significantly better learning efficiency than less aggressive pruning functions. Also experimental results show that expressiveness is sufficient for monadic queries based on the structure. -The function paths_extended additionally keeps all the nodes whose parents are on such paths. An example is given in Figure 15. The problem of defining the class of Nstt that can actually be identified by Rpni prune with the pruning function paths_extended is still open. The class is larger than for the pruning function paths_only because some node selection queries using textual contents are learnable. For instance, a query for actor lists where the next sibling contains the textual value "Hitchcock". As soon as textual values are not involved, experimental results have shown lower learning efficiency and equivalent expressiveness than for the pruning function paths_only. -The function identity. Rpni prune restricted to completely annotated trees behaves as the tRpni algorithm for deterministic Nstts. All Mso-definable node selection queries could be the target of Rpni prune . However experimental results show that a large number of annotated examples is required to achieve learning. Also, in the interactive setting, learning from a small number of annotated positions could introduce wrong generalizations.

Squirrel Web Information Extraction System

We have developed a software tool, Squirrel (Figure 16). We first describe the system. Then we give experimental results in the off-line setting in order to compare our system with others. Finally we give experimental results in order to evaluate the number of interactions in the interactive setting.

System description. Squirrel preprocesses pages via the parser included in Mozilla. This yields a Dom Xhtml tree. We ignored textual values. Attributes were ignored too except for ID and CLASS, which were merged with the name of the tag, i.e. <DIV ID=title> gives a node labeled DIVtitle.

The user is the query designer. When a Clq is made by Squirrel, the query designer annotates an incorrect node (unwanted or missing). In a real setting, the query designer may annotate more than one position. When a Qeq is made by Squirrel, the query designer decides to halt the induction process or chooses a new Web page. The Squirrel algorithm calls the Rpni prune algorithm. For the experimental results we have chosen the pruning function paths_only.

Off-line Experiments. The aim of these experiments is to compare Rpni prune with state-of-the-art algorithms. Thus we do not consider the interactive framework and Rpni prune is given as an input completely annotated examples for the target query.

We considered benchmarks from Rise 2 , the only public repository of annotated documents designed to evaluate information extraction algorithms on Web pages. We had to discard some of the datasets, because the extraction tasks they defined were not Html element extraction tasks, and could therefore not be addressed by our algorithm. Typically, extracting a given word in a sentence is a problem outside the scope of our work.

The remaining datasets we used are these ones:

-18 of Kushmerick's Wien benchmark (Freitag & Kushmerick, 2000) used by Muslea in [START_REF] Muslea | Hierarchical wrapper induction for semistructured information sources[END_REF] For each dataset, we evaluate our algorithm using a 8-fold cross-validation protocol. The dataset is divided in 8 parts. A wrapper dedicated to one extraction task is learned from 7 parts, and tested on the last one. True positives, false negatives and false positives are counted and a F1-measure score is computed. Each part of the dataset is used as test set for each extraction task in a distinct experience, and an average F-measure is computed.

It is rather difficult to compare our own results to the ones of other systems, considering that we cannot test them ourselves and that we have to use published results whose experimental protocol are never exactly the same. Following Muslea in [START_REF] Muslea | Hierarchical wrapper induction for semistructured information sources[END_REF], we establish a comparison using a qualitative criteria: we consider three possible behaviours for each system on each benchmark: perfect (average F-measure of 100%), imperfect (average F-measure between 90% and 100%) and failure (F-measure below 90%). All results are presented in Fig. 17. Results concerning Wien [START_REF] Kushmerick | Wrapper induction: Efficiency and expressiveness[END_REF] and Stalker [START_REF] Muslea | Hierarchical wrapper induction for semistructured information sources[END_REF], two well known information extraction systems, are given for the sake of comparison. They have been directly taken from [START_REF] Muslea | Hierarchical wrapper induction for semistructured information sources[END_REF].

These results show that Squirrel behaves satisfyingly in a large majority of the benchmarks, and achieves performances on these benchmarks which are equals or greater than Wien and Stalker. A closer analysis of the failures of Squirrel (S-6 and S-11) shows that they have expected causes: in both cases, the structure is not informative enough because textual contents of leaves are necessary to define the query. Therefore Squirrel with the pruning function paths_only can not infer a relevant wrapper. One way to overcome this problem is to preprocess the data sets in order to distinguish text nodes which should be useful for the induction process, consider trees with these textual values, and use the pruning function paths_extended .

To end the comparisons with existing systems, we now compare our system with the system presented in [START_REF] Raeymaekers | Learning (k,l)-contextual tree languages for information extraction[END_REF]. They represent a monadic node selection query q by a tree language L q where each tree contains a single marked node. To decide if a node of a tree t is to be selected, the node is marked (replaced by a special symbol), if the tree is in L q , then the original node is to be selected. Whereas we use the Rpni algorithm from positive and negative examples, their base learning algorithm is from positive examples only. They consider a subclass of the class of regular languages which is chosen to be the class of (k, l)contextual tree languages where k and l are parameters. With parameter tuning, they achieve perfect results on benchmarks presented Fig. 17. They succeed in S-6 and S-11 because they use a preprocessing procedure to distinguish important textual values. They also present a method to learn the parameters from positive and negative examples.

Benchmarking interactive learning. For the experiments, we used the benchmarks Okra, Bigbook and real datasets3 from different Web sites:

the Yahoo dataset contains 80 pages of the Yahoo Web directory. The task is to extract a set of URLs from a list of URLs. There are different lists on a page, the pages have different structures and the position of the list is not fixed; the eBay dataset contains 40 pages of products. The task is to extract product names from a table. The product name can be mixed with other information in the cell; -the Google dataset contains 40 results of the search engine. The task is to extract the links. The structure of pages is not fixed and there are numerous auxiliary links; -the New York Times dataset contains 40 article pages with different structures. The task is to extract texts of the articles.

In order to evaluate the efficiency of the algorithm in the interactive mode, we simulated the behavior of a query designer. Squirrel is interfaced with a user simulator S: at each call of the correct labeling oracle, S answers the first wrong annotation of the page in reading order of the source file (which is the first positive annotation of the page for the first call) ; at each call of the equivalence oracle, S returns a Web page on which the pruned Nstt is not correct.

In an interactive setting, time complexity is important. For the different data sets, on a standard computer, the average time for learning the current hypothesis and annotating the current Web page is between 1 and 2 seconds and less than 5 seconds on the more intricate cases.

We also measured the number of Clqs and Qeqs which are needed to achieve perfect results on the set of Web pages. The results are given in Figure 18. The number of Clqs is the number of corrections made by the query designer. The results show that this number is quite small. We should note that this number is over-valued because in a real setting, the query designer may correct more than one wrong annotation at a time, and we can hope that his choice of correction is more relevant than the one used in our protocol. The number of Qeqs is the number of Web pages necessary to achieve perfect results. The number of necessary Web pages for the Yahoo dataset is greater than for other datasets because the dataset is heterogeneous. We should note that the number of necessary Web pages is lower than the number of Web pages viewed by the query designer. Indeed, in our protocol the user simulator selects only Web pages on which the current hypothesis is incorrect while, in the real setting, the query designer may choose a Web page on which the current hypothesis is correct. Therefore we now discuss the choice of the next Web page to be processed in the interactive setting.

Towards active learning

We should render our model active in the sense that the learner intelligently proposes the next Web page among a set of Web pages -the Web pages of the target Web site. We considered a method estimating the value of a tree according to the number of extracted nodes by the current hypothesis wrapper. We supposed that there is a linear dependence between the number of extracted nodes and the total number of nodes. This lead to the following strategy: let L be the set of Web pages not seen so far by Squirrel; for every Web page p in L, we compute the number x of nodes of p and y the number of selected nodes by the current hypothesis wrapper; we used the test of Grubbs for outlier selection to select the web page (the farthest point (x, y) from the regression line). The selected Web page is processed by the main loop of Squirrel.

We only considered the three most difficult datasets. We computed performance with a learning set of annotated documents of respectively 1, 2, 5, 10 Web pages. These Web pages were either randomly chosen or chosen according to the strategy given above. The experimental results are given in Figure 19. They show that our naive strategy for active learning leads to significant improvements. It remains to find an intelligent active learning strategy as a future work.

Conclusion

We have presented a wrapper induction system with the following characteristics:

it generates tree-based wrappers which select nodes in trees; -it uses new machine learning techniques based on grammatical inference and active learning; -it is integrated in a visual environment;

it has simple interactions with the query designer.

From the theoretical point of view, it is proved that Nstts and pNstts can express all MSO-definable node selection queries. However any pruning function, different from identity, will restrict the class of learnable node selection queries. In future work, We have to specify the subclass of node selection queries which is learnable depending on the chosen pruning strategy.

From the practical point of view, we have proved that our system achieves state-of-the-art performance on standard benchmarks and that the number of interactions with the query designer is quite small. Nevertheless there are still a number of possible improvements. First, we should render our algorithm active with intelligent strategies. Second, we do not consider textual values and omit some attribute values. Therefore, we should adapt our approach to take textual information into account. Finally, our current system is limited to one-slot information extraction since we only consider monadic node selection queries over trees. Work is under progress to extend our approach to multi-slot information extraction, i.e., the problem of learning n-ary regular queries in trees.

A Testing Cut-Functionality in Polynomial Time

We present a direct proof for Proposition 2 in the case of binary trees (and thus for unranked trees), stating that cut-functionality of deterministic tree automata can be decided in polynomial time.

We characterize cut-functionality of a tree automaton A with signature (Σ × B) T by a binary relation inc A ⊆ states(A) 2 , testing for two states whether they can be reached by two runs of A on some incompatibly annotated compatible trees. For all two states p, p ′ ∈ states(A):

inc A (p, p ′ ) iff        ∃t, t ′ compatible trees over Σ T ∃β, β ′ trees over B T ∃r ∈ runs A (t × β) : r(ε) = p ∃r ′ ∈ runs A (t ′ × β ′ ) : r ′ (ε) = p ′ Lemma 4 A tree automaton A over (Σ × B) T is cut-functional if and only if inc A (p, p ′ ) doesn't hold for any two states p, p ′ ∈ final (A).
Proof Suppose inc A (p, p ′ ) holds for some p, p ′ ∈ final (A). Then there exist runs r ∈ runs A (t×β) and r ′ ∈ runs A (t ′ ×β ′ ) for incompatible trees β and β ′ and compatible trees t and t ′ . These runs are successful since p, p ′ ∈ final (A). Thus, A is not cut-functional. The argument can be reversed.

It remains to show that the relation inc A can be computed in polynomial time. We prove that it can be computed by a saturation procedure over states. We first need to define another binary relation sim A on states. sim A holds if two states can be reached by compatible annotated trees: Definition 8 Let A be a deterministic tree automaton over (Σ × B) T , p and p ′ two states of A, then sim A (p, p ′ ) holds if there exist two compatible (Σ × B) T -trees t × β, t ′ × β ′ , a run r of A over t × β such that r(ε) = p, and a run r ′ of A over t ′ × β ′ such that r ′ (ε) = p ′ .

We now give an inductive characterization of the relation inc A which is based on the relation sim A and on the rule set of the tree automaton. We call an automaton trimmed if it has no useless state, i.e., if for each state p there is a run r of A some tree such that r(ε) = p.

Lemma 5 Let A be a trimmed deterministic tree automaton over (Σ ×B) T , inc A (p, p ′ ) holds if and only if there exist rules satisfying one of the cases in Figure 20 Proof Let us suppose that inc A (p, p ′ ). Then there exist two (Σ × B) T -trees t × β, t ′ × β ′ such that t and t ′ are compatible but t × β and t ′ × β ′ are not compatible, a run r of A over t × β such that r(ε) = p, and a run r ′ of A over t ′ × β ′ such that r ′ (ε) = p ′ .

Proposition 2 Cut-functionality of a deterministic tree automaton A over (Σ × B) T can be tested in cubic time.

Proof First, the relation sim A is computed by a saturation process: Initialize with the first three rules in Lemma 6: consider the set of {(p, p) | p ∈ states(A)} union {(p, p ′ ) | ∃(T → p ∈ rules(A))} union {(p, p ′ ) | ∃(T → p ′ ∈ rules(A))}; and then use the fourth rule (iv) inductively. There is at most a quadratic amount of linear tests to perform, therefore the construction is in cubic time. We use a similar construction for the relation inc A : First use the rule (i) in Lemma 5, second the rule (ii), and then apply inductively the rules (iii), (iv) and (v). Again, the construction is in cubic time.

B Efficient Query Answering for Nstts and pNstts

We next present algorithms for answering queries defined by Nstts or pNstts. Query answering will be needed in our interactive learning environment for testing the current query hypothesis on given trees.

B.1 Alternative definitions of monadic queries

We present two further ways for expressing monadic queries by tree automata. They will be useful for query answering for Nstts and pNstts.

Every tree A with signature Σ × B defines a MSO-definable monadic query q A in Σ-trees such that for all such trees t : q A (t) = {v ∈ nodes(t) | β(v) = 1 and t × β ∈ L(A)}

We can compute q A (t) for a given binary tree t and automaton A by enumerating all annotated trees t × β, filtering those that belong to L(A), and collecting the nodes that such β's annotates by 1. This way of answering queries defined by tree automata is highly non-deterministic, and thus inefficient. But we can do better, as we will see.

Run-based automata queries offer another way to define monadic queries, for which efficient algorithms are known. They are defined by a tree automaton A over Σ and a set of selection states S ⊆ states(A), and satisfy for all binary trees t: q A,S (t) = {v ∈ nodes(t) | ∃r ∈ succ_runs A (t), r(v) ∈ S} This query selects all those nodes of t are labeled by some selection state in S in some successful run of B.

Proposition 3 (Classical Result) Given a tree automaton A over Σ, a set S ⊆ states(A), and a binary Σ-tree t one can compute the set q A,S (t) in time O(|A| * |t|). moved from the signature into the states. Automaton e(A) may label all leaves by state T , as well as inner nodes whose descendants it has labeled by T before. At an arbitrary time point, e(A) can decide to move from state T to some state p of A for which T → p is a rule of A. Subsequently, e(A) behaves equally to A.

Note that we freely permit ε-rules, which can easily be eliminated while preserving the language. For these particular automata, ǫ-rules can be eliminated in linear time, since no two ǫ rules can be composed.

It now remains to show that q A = q e(A) for every pNstt A. We omit these details.

C Expressiveness of Nstts and pNstts

We show that deterministic Nstts as well as deterministic pNstts capture the class of monadic Mso-definable queries.

C.1 MSO-definable queries

In a logical perspective, a tree t is seen as a logical structure with domain nodes(t), unary relations label a for every a ∈ Σ, and two binary relations firstchild and nextsibling. We assume an infinite set of first-order variables x, y, z, and an infinite set of monadic second-order variables S. Formulas of Mso in unranked (or binary) trees have the following syntax: Standard logical connectives such as conjunction φ ∧ φ ′ , negation ¬φ, existential quantification ∃x.φ and ∃S.φ can be expressed as usual, as well set inclusion S ⊆ S ′ . Further relations such as child and lastchild are definable in Mso as well. Models of Mso formulas are defined in the usual Tarskian style. They consist of a tree structure t and a variable assignment α mapping firstorder variables to nodes(t) and second-order variables to 2 nodes(t) . We write t, α |= φ if t, α is a model of φ, and consider models of φ as equal if they coincide on the free variables of φ.

Every Mso formula φ(x) with a single free variable x defines a monadic query q φ(x) in unranked (resp. binary) trees, so that for all trees t: q φ(x) (t) = {α(x) ∈ nodes(t) | t, α |= φ(x)}

C.2 Nstt and pNstt-defined queries

The idea behind completely annotated examples (as recognized by Nstts) is to annotate all nodes that are selected in some tree in a single annotation. In Mso, we can express the same idea by collecting all nodes x selected by some query φ(x) in a single set S. φ ′ (S) ≡ ∀x. (S(x) ↔ φ(x))

More generally, we can use Mso formulas φ(S) with a single free set variable S to define monadic queries, such that for all trees t: q φ(S) (t) = {v ∈ nodes(t) | t, α |= φ(S), v ∈ α(S)} A monadic query is definable by a Mso formula with a single free first-order variable if and only if it is definable by an Mso formula with a single free second-order variable.

Annotated trees can be understood as the models of Mso formulas with a single set valued variable. A model t, α of Mso formulas with a single free variable S becomes the annotated tree t × α(S), which annotates all nodes in t belonging to α(S) by 1 and all others by 0.

Theorem 4 [START_REF] Thatcher | Generalized finite automata with an application to a decision problem of second-order logic[END_REF])) The set of annotated trees corresponding to models of an Mso formula φ(S) over signature Σ is a regular tree language over Σ × B, and vice versa.

The theorem states that a monadic query in binary trees over Σ definable by an Mso formula with one free set variable if and only it is definable by some tree automaton over the signature Σ × B. The original theorem is even more general in that it applies to n-ary queries which are definable by formulas with n free variables [START_REF] Niehren | N-ary queries by tree automata[END_REF].

Theorem 5 A query is definable in Mso iff it is definable by a deterministic Nstt iff it is definable by a deterministic pNstt.

Proof Consider a query that is defined by some Mso-formula φ(x). The same query is defined by the formula φ ′ (S) ≡ ∀x(x ∈ S ↔ φ(x)). Formula φ ′ (S) is functional in that the value of S is uniquely determined by the tree structure of models of φ ′ (S). Let A be the tree automaton over Σ × B that recognizes the set of annotated trees corresponding to the models of φ ′ (S), according to Thatcher and Wright's theorem 4. The language of this automaton is functional, given that the value of S in models t, α |= φ ′ (S) is uniquely defined. This proves that A is an Nstt. construction, it defines the same query as φ ′ (S) and thus φ(x). The same automaton is also a pNstt.

We have shown in Section B.2 that monadic queries represented by deterministic Nstts can be identified with run-based queries defined by unambiguous tree automata. Theorem 5 shows that runs of unambiguous tree automata can express all Mso definable monadic queries. This result has been shown before by [START_REF] Neven | Expressiveness of structured document query languages based on attribute grammars[END_REF]. The simple Mso-based proof presented here stems from [START_REF] Niehren | N-ary queries by tree automata[END_REF] where the expressiveness of n-ary queries by unambiguous tree automata has been studied too.

Figure 1

 1 Figure1A rendered Html document returned by some Web search machine.

Figure 2

 2 Figure2The parse tree of the Html document in Figure1.

Figure 5

 5 Figure 5 Three film lists completely annotated by the query actors_hitchcock

Figure 7

 7 Figure 7 Two trees obtained by pruning the tree films annotated by query actors_hitchcock . The Boolean annotations are compatible with this query.

Figure 8

 8 Figure 8 A deterministic pNstt defining the query actors_hitchcock .

Figure 12

 12 Figure 12 Learning from completely annotated examples.

Figure 14

 14 Figure14Learning from partially annotated trees.

Figure 16

 16 Figure 16 Screenshot of Mozilla Firefox with Squirrel: a toolbar has been added to help the user to annotate data in the web page and to dialog with the learning algorithm.

lFigure 21

 21 Figure 21 Rules of automata e(A) that recognizes expansions of trees in L(A).

φ

  ::= label a (x) | firstchild (x, y) | nextsibling(x, y) | φ → φ ′ | S(x) | ∀x.φ | ∀S.φ

  Squirrel // fix a representation formalism for queries // // we write qA for the query represented by A // let A represent the empty query let S be the empty set of completely annotated trees Loop until Qeq (A) returns yes let t be the output of Qeq let p+ = p-= ∅ be partial annotations for t Loop until Clq (t × qA(t)) returns yes let v be output of Clq // add the correct annotation of v to p+ or p-// If v ∈ qA(t) then add v to pelse add v to p+ // learn a new query representation// A ← Rpniprune(S, t, p+, p-) Add t × qA(t) to the set S Output : A Figure 13 Squirrel active learning algorithm.

  to establish a comparison between Wien and Stalker. They are denoted by S-XX in table of results. Each of them is constituted with 8 pages, and is associated with one four extraction tasks. -Bigbook, a set 235 pages extracted from an address book. Two tasks are associated with this set: name extraction and address extraction. -Okra, a set of 250 pages which corresponds to a people search engine output. Three tasks are associated with this set: name, mail address and score extraction.

  Figure17Comparison between Stalker, Wien and Squirrel on the Rise corpus. The symbolmeans failure, that is average F-measure lower than 90%, ≃ means imperfect, that is average F-measure between 90% and 100%, and √ means perfect, that is average F-measure equal to 100%.

	S-5	√	√	√
	S-6 BigBook	√	√	√

  Figure 18 #Qeq denotes the number of equivalence queries and #Clq denotes the number of correct labeling queries. Results are averaged over 100 experiments.

		#Qeq #Clq
	Okra-names	1.6	3.48
	Bigbook-addresses	1	3.02
	Yahoo	6.18	11.36
	E-bay	1.06	2.62
	NYTimes	1.44	1.44
	Google	1.86	4.78

Completeness with respect to expressiveness and learning are independent questions. Our learning algorithm tRpni for Nstts is a complete, while our algorithm Rpniprune inducing pNstts is not (for realistic pruning functions).

http://www.isi.edu/˜muslea/RISE/index.html

http://www.grappa.univ-lille3.fr/˜carme/corpus.html

Acknowledgments

We are grateful to Alain Terlutte for contributing his forces and enthusiasms into this work in the early phase.

We thank the referees for their invaluable comments on preliminary versions of the paper.

This research was partially supported by the research unit Inria Futurs, Cnrs Umr 8022, "Cper 2000-2006, Contrat de Plan état -région Nord/Pasde-Calais: programme Tac, projet Cocoa" and "Aci masse de données Aci-Mdd, Fns".

Colloquium on Grammatical Inference, Vol. 3264 of Lecture Notes in Artificial Intelligence, pp. 91-102. Springer Verlag. Carme, J., Niehren, J., & Tommasi, M. (2004b). Querying unranked trees with stepwise tree automata. In 19th International Conference on Rewriting Techniques and Applications, Vol. 3091 of Lecture Notes in Computer Science, pp. 105 -118. Springer Verlag. Chidlovskii, B. (2001). Wrapping web information providers by transducer induction. In Proc. European Conference on Machine Learning, Vol. 2167 of Lecture Notes in Artificial Intelligence, pp. 61 -73. Cohen, W., Hurst, M., & Jensen, L. (2003). Web Document Analysis: Challenges and Opportunities, chap. A Flexible Learning System for Wrapping Tables and Lists in HTML Documents. World Scientific. Comon, H., Dauchet, M., Gilleron, R., Jacquemard, F., Lugiez, D., Tison, S., & Tommasi, M. (1997). Tree automata techniques and applications. Available on: http://www.grappa.univ-lille3.fr/tata. Cristau, J., Löding, C., & Thomas, W. (2005). Deterministic automata on unranked trees. In 15th International Symposium on Fundamentals of Computation Theory, Vol. 3623 of Lecture Notes in Computer Science, pp. 68-79. Springer Verlag. de la Higuera, C. (1997). Characteristic sets for polynomial grammatical inference. Machine Learning, 27, 125-137. Drewes, F., & Hogberg, J. (2003). Learning a regular tree language from a teacher. In D.L.T. 2003, Vol. 2710 of Lecture Notes in Computer Science, pp. 279-291. Freitag, D., & Kushmerick, N. (2000). Boosted wrapper induction. In AAAI/IAAI, pp. 577-583. Freitag, D., & McCallum, A. K. (1999). Information extraction with hmms and shrinkage. In Proceedings of the AAAI-99 Workshop on Machine Learning for Information Extraction. Frick, M., Grohe, M., & Koch, C. (2003). Query evaluation on compressed trees. In 18th IEEE Symposium on Logic in Computer Science, pp. 188-197. Gold, E. (1967). Language identification in the limit. Inform. Control, 10, 447-474. Gold, E. (1978). Complexity of automaton identification from given data.

Inform. Control, 37, 302-320. Gottlob, G., & Koch, C. (2002). Monadic queries over tree-structured data.

In 17th Annual IEEE Symposium on Logic in Computer Science, pp. 189-202 Copenhagen. Hsu, C.-N., & Dung, M.-T. (1998). Generating finite-state transducers for semi-structured data extraction from the web. Information Systems, 23 (8), 521 -538. Kermorvant, C., & de la Higuera, C. (2002). Learning language with help. In 6th International Colloquium on Grammatical Inference, Vol. 2484 of Lecture Notes in Artificial Intelligence, pp. 161-173. Springer Verlag.

Figure 20 Cases of Lemma 5.

-First, note that neither t nor t ′ is equal to T (which would correspond to a tree entirely pruned), as otherwise β = T (resp. β ′ = T ), and as T is compatible with every tree, we would have β and β ′ compatible. -If t is a single leaf tree with t = a then t ′ = a also as t and t ′ are compatible. In this case β = b and β ′ = ¬b as they are not compatible.

As r(ε) = p and r ′ (ε) = p ′ , this implies that there are two rules (a, b) → p and (a, ¬b) → p ′ and (i) holds. -If t is a tree of the form t = a(t 1 , t 2 ) then, as t and t ′ are compatible, there are trees t ′ 1 and t

which are applied at the root of the trees t × β and t ′ × β ′ in the runs r and r ′ . As t 1 and t ′ 1 are compatible, and t 2 and t ′ 2 are compatible, the states satisfy sim

. First, consider the case where the Boolean values at the root of the trees t × β and t ′ × β ′ are different. In this case, one of the four conditions (ii), (iii), (iv) or (v) holds. If the Boolean values at the root of the trees t × β and t ′ × β ′ are equal, then inc A (p 1 , p ′ 1 ) or inc A (p 2 , p ′ 2 ) must hold and one of the conditions (iii), (iv) or (v) holds.

We now prove the other direction of the equivalence.

We have the same property for the right sub-term (the corresponding states, runs and terms are denoted by

We consider two rules satisfying (iii). We consider the two trees that are associated with the property inc A (p 1 , p ′ 1 ), and then we construct two trees proving that inc A (p, p ′ ) holds. The construction is similar to the one used in the precedent point. In this case, incompatibility between Boolean values comes from the left subtrees t 1 × β 1 and t

the cases (iv) and (v) are similar.

Lemma 6 Let A be a trimmed deterministic tree automaton over (Σ × B) T , sim A (p, p ′ ) stands if and only if there exist rules satisfying one of the following cases:

-If t = T , then there is a rule T → p in A and (ii) holds.

t×β and t ′ ×β ′ are compatible. In the first case, because of determinism, p = p ′ and (i) holds. In the second case, there is a rule T → p ′ in A and (iii) holds.

-If there are some trees

1 , p ′ 2 ) → p ′ which are applied at the root of the trees t × β and t ′ × β ′ in the runs r and r ′ . We should note that t 1 × β 1 and t ′ 1 × β ′ 1 are compatible, and t 2 × β 2 and t ′ 2 × β ′ 2 are compatible, thus the states satisfy sim A (p 1 , p ′ 1 ) and sim A (p 2 , p ′ 2 ), and (iv) holds. We now prove the other direction of the equivalence.

-(i) If p = p ′ , let t × β be any tree that has a run in A whose root is p, t × β is compatible with itself and sim A (p, p ′ ). -(ii) and (iii) If T → p ∈ rules(A), then we can consider any tree t ′ × β ′ that has a run in A whose root is p ′ then t ′ × β ′ is compatible with T and sim A (p, p ′ ). Case (iii) is similar.

The algorithm proceeds in two phases. In a bottom-up phase, every node v of t is annotated by all states of B into which the subtree rooted by v can be evaluated (determinization on the fly). In a second top-down phase, one underlines all those states that are used by successful runs. Finally, one selects all those nodes that are annotated by underlined states from the selection set S.

B.2 Nstts and pNstts

We first consider monadic queries defined by tree automata A over Σ × B. We show that we can express them by run-based queries via automata projection (which will be useful later on too).

Lemma 7 Queries by an automata A over Σ ×B can be defined equivalently by runs of the Σ projected automaton π(A): q A = q π(A),states(A)×{1} .

As a side product, Lemmas 7 show that every Nstt-defined query can be defined as run-based query by some unambiguous tree automaton.

Proposition 4 Given a tree automaton A over Σ × B and a binary Σ-tree t one can compute the set q A (t) in time O(|A| * |t|).

By Lemma 7 we can convert the query q A into a run-based query by automata projection, which requires linear time. This later query can be answered in linear time by Proposition 3.

Theorem 3 Queries q A (t) by Nstts or pNstts over binary trees can be computed in linear time O(|A| * |t|).

For Nstts this follows immediately from Proposition 4. Queries by pNstts can be answered the same way after conversion by the following lemma.

Lemma 8 Every pNstts can be transformed in linear time into an automata over Σ × B that defines the same query.

Note that the resulting automaton will not necessarily be an Nstt.

Proof Let A be a pNstt with signature (Σ × B) T . The idea of the transformation is to compute an automaton e(A) over Σ × B that recognizes all expansions of trees in L(A), obtained by replacing T -leaves by arbitrary trees over Σ × {0}.

states(e(A)) = states(A) ⊎ {T } final (e(A)) = final (A)

The rules of e(A) are induced by the schemata in 21, which are valid for all symbols a ∈ Σ, p ∈ states(A), and left hand sides l of rules in A: all rules of A are preserved by e(A) except those with the symbol T , which is