Alexander Kartzow

COLLAPSIBLE PUSHDOWN GRAPHS OF LEVEL 2 ARE TREE-AUTOMATIC

Keywords: 1998 ACM Subject Classification: F.4.1[Theory of Computation]:Mathematical Logic tree-automatic structures, collapsible pushdown graphs, collapsible pushdown systems, first-order decidability, reachability

We show that graphs generated by collapsible pushdown systems of level 2 are tree-automatic. Even when we allow ε-contractions and add a reachability predicate (with regular constraints) for pairs of configurations, the structures remain tree-automatic. Hence, their FO theories are decidable, even when expanded by a reachability predicate. As a corollary, we obtain the tree-automaticity of the second level of the Caucal-hierarchy.

Introduction

Higher-order pushdown systems were first introduced by Maslov [START_REF] Maslov | The hierarchy of indexed languages of an arbitrary level[END_REF][START_REF] Maslov | Multilevel stack automata[END_REF] as accepting devices for word languages. Later, Knapik et al. [START_REF] Knapik | Higher-order pushdown trees are easy[END_REF] studied them as generators for trees. They obtained an equi-expressivity result for higher-order pushdown systems and for higherorder recursion schemes that satisfy the constraint of safety, which is a rather unnatural syntactic condition. Recently, Hague et al. [START_REF] Hague | Collapsible pushdown automata and recursion schemes[END_REF] introduced collapsible pushdown systems as extensions of higher-order pushdown systems and proved that these have exactly the same power as higher-order recursion schemes as methods for generating trees.

Both -higher-order and collapsible pushdown systems -also form interesting devices for generating graphs. Carayol and Wöhrle [START_REF] Carayol | The Caucal hierarchy of infinite graphs in terms of logic and higher-order pushdown automata[END_REF] showed that the graphs generated by higherorder pushdown systems 1 of level l coincide with the graphs in the l-th level of the Caucalhierarchy, a class of graphs introduced by Caucal [START_REF]On infinite terms having a decidable monadic theory[END_REF]. Every level of this hierarchy is obtained from the preceding level by applying graph unfoldings and MSO interpretations. Both operations preserve the decidability of the MSO theory whence the Caucal-hierarchy forms a rather large class of graphs with decidable MSO theories. If we use collapsible pushdown systems as generators for graphs we obtain a different situation. Hague et al. showed that even the second level of the hierarchy contains a graph with undecidable MSO theory. But they showed the decidability of the modal µ-calculus theories of all graphs in the hierarchy. This turns graphs generated by collapsible pushdown systems into an interesting class from a model theoretic point of view. There are few natural classes that share these properties. In fact, the author only knows one further example, viz. nested pushdown trees. Alur et al. [START_REF] Alur | Languages of nested trees[END_REF] introduced these graphs for µ-calculus model checking purposes. We proved in [START_REF] Kartzow | FO model checking on nested pushdown trees[END_REF] that nested pushdown trees also have decidable first-order theories. We gave an effective model checking algorithm using pumping techniques, but we also proved that nested pushdown trees are tree-automatic structures. Tree-automatic structures were introduced by Blumensath [START_REF] Blumensath | Automatic structures[END_REF]. These structures enjoy decidable first-order theories due to the good closure properties of finite automata on trees.

In this paper, we are going to extend our previous result to the second level of the collapsible pushdown hierarchy. All graphs of the second level are tree-automatic. This subsumes our previous result as nested pushdown trees are first-order interpretable in collapsible pushdown graphs of level two. Furthermore, we show that collapsible pushdown graphs of level 2 are still tree-automatic when expanded by a reachability predicate, i.e., by the binary relation which contains all pairs of configurations such that there is a path from the first to the second configuration. Thus, first-order logic extended by reachability predicates is decidable on level 2 collapsible pushdown graphs.

In the next section, we introduce the necessary notions concerning tree-automaticity and in Section 3 we define collapsible pushdown graphs. We explain the translation of configurations into trees in Section 4. Section 5 is a sketch of the proof that this translation yields tree-automatic representations of collapsible pushdown graphs, even when enriched with certain regular reachability predicates. The last section contains some concluding remarks about questions arising from our result.

Preliminaries

We write MSO for monadic second order logic and FO for first-order logic. For words w 1 , w 2 ∈ Σ * , we write w 1 ⊓ w 2 for the greatest common prefix of w 1 and w 2 . A Σ-labelled tree is a function T : D → Σ for a finite D ⊆ {0, 1} * which is closed under prefixes. For d ∈ D we denote by T d the subtree rooted at d.

Sometimes it is useful to define trees inductively by describing their left and right subtrees. For this purpose we fix the following notation. Let T0 and T1 be Σ-labelled trees and σ ∈ Σ. Then we write T := σ( T0 , T1 ) for the Σ-labelled tree T with the following three properties 1. T (ε) = σ, 2. T 0 = T0 , and 3. T 1 = T1 .

In the rest of this section, we briefly present the notion of a tree-automatic structure as introduced by Blumensath [START_REF] Blumensath | Automatic structures[END_REF].

The convolution of two Σ-labelled trees T and T ′ is given by a function

T ⊗ T ′ : dom(T ) ∪ dom(T ′ ) → (Σ ∪ { }) 2
where is a new symbol for padding and

(T ⊗ T ′ )(d) :=      (T (d), T ′ (d)) if d ∈ dom(T ) ∩ dom(T ′ ) (T (d), ) if d ∈ dom(T ) \ dom(T ′ ) ( , T ′ (d)) if d ∈ dom(T ′ ) \ dom(T )
By "tree-automata" we mean a nondeterministic finite automaton that labels a finite tree top-down. f : L → B for L the language accepted by A B such that the following hold. For T, T ′ ∈ L, the automaton

A E i accepts T ⊗ T ′ if and only if f (T ), f (T ′ ) ∈ E i .
Tree-automatic structures form a nice class because automata theoretic techniques may be used to decide first-order formulas on these structures:

Lemma 2.2 ([2]
). If B is tree-automatic, then its first-order theory is decidable.

We will use the classical result that regular sets of trees are MSO definable.

Theorem 2.3 ([12], [START_REF] Doner | Tree acceptors and some of their applications[END_REF]). For a set T of finite Σ-labelled trees, there is a tree automaton recognising T if and only if T is MSO definable.

Definition of Collapsible Pushdown Graphs (CPG)

In this section we define our notation of collapsible pushdown systems. For a more comprehensive introduction, we refer the reader to [START_REF] Hague | Collapsible pushdown automata and recursion schemes[END_REF].

Collapsible Pushdown Stacks

First, we provide some terminology concerning stacks of (collapsible) higher-order pushdown systems. We write Σ * 2 for (Σ * ) * and Σ +2 for (Σ + ) + . We call an s ∈ Σ * 2 a 2-word.

Let us fix a 2-word s ∈ Σ * 2 which consists of an ordered list w 1 , w 2 , . . . , w m ∈ Σ * . We separate the words of this list by colons writing s = w 1 : w 2 : . . . : w m . By |s| we denote the number of words s consists of, i.e., |s| = m.

For another word s ′ = w ′ 1 : w ′ 2 : . . . : w ′ n ∈ Σ * 2 , we write s : s ′ for the concatenation w 1 : w 2 : . . . : w m : w ′ 1 : w ′ 2 : . . . : w ′ n . If w ∈ Σ * , we write [w] for the 2-word that consists of a list of one word which is w. A level 2 collapsible pushdown stack is a special element of (Σ × {1, 2} × N) +2 that is generated by certain stack operations from an initial stack which we introduce in the following definitions. The natural numbers following the stack symbol represent the socalled collapse pointer : every element in a collapsible pushdown stack has a pointer to some substack and applying the collapse operation returns the substack to which the topmost symbol of the stack points. Here, the first number denotes the collapse level. If it is 1 the collapse pointer always points to the symbol below the topmost symbol and the collapse operations just removes the topmost symbol. The more interesting case is when the collapse level of the topmost symbol of the stack s is 2. Then the stack obtained by the collapse contains the first n words of s where n is the second number in the topmost element of s.

The initial level 1 stack is ⊥ 1 := (⊥, 1, 0) and the initial level 2 stack is

⊥ 2 := [⊥ 1 ].
For k ∈ {1, 2} and for a 2-word s = w 1 : w 2 : . . . :

w n ∈ (Σ × {1, 2} × N) +2 such that w n = a 1 a 2 . . . a m with a i ∈ Σ × {1, 2} × N for all 1 ≤ i ≤ m:
• we define the topmost (k -1)-word of s as top k (s) :=

w n if k = 2 a m if k = 1 • for top 1 (s) = (σ, i, j) ∈ Σ × {1, 2} × N, we define the topmost symbol Sym(s) := σ,
the collapse-level of the topmost element CLvl(s) := i, and the collapse-link of the topmost element CLnk(s) := j.

For s, w n and k as before, σ ∈ Σ\{⊥}, and w ′ n := a 1 . . . a m-1 , we define the stack operations

pop k (s) :=      w 1 : w 2 : . . . : w n-1 if k = 2, n ≥ 2 w 1 : w 2 : . . . : w n-1 : w ′ n if k = 1, m ≥ 2 undefined otherwise clone 2 (s) := w 1 : w 2 : . . . : w n-1 : w n : w n push σ,k (s) := w 1 : w 2 : . . . : w n (σ, 2, n -1) if k=2 w 1 : w 2 : . . . : w n (σ, 1, m) if k=1 collapse(s) :=      w 1 : w 2 : . . . : w r if CLvl(s) = 2, CLnk(s) = r > 0 pop 1 (s) if CLvl(s) = 1 undefined otherwise
The set of level 2-operations is OP := push σ,1 , push σ,2 , clone 2 , pop 1 , pop 2 , collapse . The set of level 2 stacks, Stck(Σ), is the smallest set that contains ⊥ 2 and is closed under all operations from OP. Note that collapse-and pop k -operations are only allowed if the resulting stack is in (Σ + ) + . This avoids the special treatment of empty words or stacks. Furthermore, a collapse on level 2 summarises a non-empty sequence of pop 2 -operations. For example, starting from ⊥ 2 , we can apply a clone 2 , a push σ,2 , a clone 2 , and finally a collapse. This sequence first creates a level 2 stack that contains 3 words and then performs the collapse and ends in the initial stack again. This example shows that clone 2 -operations are responsible for the fact that collapse-operations on level 2 may remove more than one word from the stack. For s, s ′ ∈ Stck(Σ), we call s ′ a substack of s if there are n 1 , n 2 ∈ N such that s ′ = pop 1 n 1 (pop 2 n 2 (s)). We write s ′ ≤ s if s ′ is a substack of s.

Collapsible Pushdown Systems and Collapsible Pushdown Graphs

Now we introduce collapsible pushdown systems and graphs (of level 2) which are analogues of pushdown systems and pushdown graphs using collapsible pushdown stacks instead of ordinary stacks. Definition 3.1. A collapsible pushdown system of level 2 (CPS) is a tuple S = (Σ, Q, ∆, q 0 ) where Σ is a finite stack alphabet with ⊥ ∈ Σ, Q a finite set of states, q 0 ∈ Q the initial state, and ∆ ⊆ Q × Σ × Q × OP the transition relation.

For q ∈ Q and s ∈ Stck(Σ) the pair (q, s) is called a configuration. We define labelled transitions on pairs of configurations by setting (q 1 , s) ⊢ (q 2 ,op) (q 2 , t) if there is a (q 1 , σ, q 2 , op) ∈ ∆ such that Sym(s) = σ and op(s) = t. The union of the labelled transition relations is denoted as ⊢:= l∈Q×OP ⊢ l . We set C(S) to be the set of all configurations that are reachable from (q 0 , ⊥ 2 ) via ⊢-paths. We call C(S) the set of reachable or valid configurations. The collapsible pushdown graph (CPG) generated by S is

CPG(S) := C(S), (C(S) 2 ∩ ⊢ ℓ ) ℓ∈Q×OP Example 3.2.
The following example of a collapsible pushdown graph of level 2 is taken from [START_REF] Hague | Collapsible pushdown automata and recursion schemes[END_REF]. Let Q := {0, 1, 2}, Σ := {⊥, a}, and ∆ given by (0, * , 1, clone 2 ), (1, * , 0, push a,2 ), (1, * , 2, push a,2 ), (2, a, 2, pop 1 ), and (2, a, 0, collapse), where * denotes any letter in Σ. In our picture (see Figure 1), the labels are abbreviated as follows: cl := (1, clone 2 ), a := (0, push a,2 ), a ′ := (2, push a,2 ), p := (2, pop 1 ), and co := (0, collapse). [START_REF] Hague | Collapsible pushdown automata and recursion schemes[END_REF] showed that modal µ-calculus model checking on level n CPG is n-EXPTIME complete. Note that there is an MSO interpretation which turns the graph of the previous example into a grid-like structure. Hence its MSO theory is undecidable.

The next definition introduces runs of collapsible pushdown systems.

Definition 3.4. Let S be a CPS. A run r of S of length n is a function

r : {0, 1, 2, . . . , n} → Q × (Σ × {1, 2} × N) * 2 such that r(0) ⊢ r(1) ⊢ • • • ⊢ r(n).
We write ln(r) := n and call r a run from r(0) to r(n). We say r visits a stack s at i if r(i) = (q, s).

For runs r, r ′ of length n and m, respectively, with r(n) = r ′ (0), we define the composition r • r ′ of r and r ′ in the obvious manner. Remark 3.5. Note that we do not require runs to start in the initial configuration.

Encoding of Collapsible Pushdown Graphs in Trees

In this section we prove that CPG are tree-automatic. For this purpose we have to encode stacks in trees. The idea is to divide a stack into blocks and to encode different blocks in different subtrees. The crucial observation is that every stack is a list of words that share the same first letter. A block is a maximal list of words in the stack that share the same two first letters2 . If we remove the first letter of every word of such a block, the resulting 2-word decomposes again as a list of blocks. Thus, we can inductively carry on to decompose parts of a stack into blocks and code every block in a different subtree. The roots of these subtrees are labelled with the first letter of the corresponding block. This results in a tree in which every initial left-closed path represents one word of the stack. By left-closed, we mean that the last element of the path has no left successor.

It turns out that -via this encoding -each stack operation corresponds to a simple MSO-definable tree-operation. The main difficulty is to provide a tree-automaton that checks whether there is a run to the configuration represented by some tree. This problem is addressed in Section 5. Now we encode a (σ, n, m)-blockline l in a tree by labelling the root with (σ, n), by encoding the blockline induced by the first block of l in the left subtree, and by encoding the rest of the blockline in the right subtree. In order to avoid repetitions, we do not repeat the symbol (σ, n) in the right subtree, but replace it by the default letter ε. Definition 4.2. Let s = w 1 : w 2 : . . . : w n ∈ (Σ × {1, 2} × N) +2 be a (σ, l, k)-blockline. Let w ′ i be words such that s = (σ, l, k) \ [w ′ 1 : w ′ 2 : . . . : w ′ n ] and set s ′ := w ′ 1 : w ′ 2 : . . . : w ′ n . As an abbreviation we write h s i := w h : w h+1 : . . . : w i . Furthermore, let w 1 : w 2 : . . . : w j be a maximal block of s. Note that j > 1 implies w j ′ = (σ, l, k)(σ ′ , l ′ , k ′ )w ′′ j ′ for all j ′ ≤ j, some fixed (σ ′ , l ′ , k ′ ) ∈ Σ × {1, 2} × N, and appropriate w ′′ j ′ ∈ Σ * . For ρ ∈ Σ × {1, 2} ∪ {ε}, we define recursively the Σ × {1, 2} ∪ {ε}-labelled tree Enc(s, ρ) via s,(⊥,1)) is called the (tree-)encoding of the stack s ∈ Stck(Σ).

Enc(s, ρ) :=          ρ if |w 1 | = 1, n = 1 ρ(∅, Enc( 2 s n , ε)) if |w 1 | = 1, n > 1 ρ(Enc( 1 s ′ n , (σ ′ , l ′ )), ∅) if j = n, |w 1 | > 1 ρ(Enc( 1 s ′ j , (σ ′ , l ′ )), Enc( j+1 s n , ε)) otherwise. Enc(s) := Enc(
Figure 3 shows a configuration and its encoding.

Remark 4.3. In this encoding, the first block of a (σ, l, k)-blockline is encoded in a subtree whose root d is labelled (σ, l). We can restore k from the position of d in the tree Enc(s) as follows. If l = 1 then k = |d| 0 , i.e., the number of occurrences of 0 in d. This is due to the fact that level 1 links always point to the preceding letter and that we always introduce a left-successor tree in order to encode letters that are higher in the stack.

The case l = 2 needs some closer inspection. Assume that some d ∈ T := Enc(s) is labelled (σ, 2). Then it encodes a letter (σ, 2, k) and this is not a cloned element.

(c, 2, 1) (e, 1, 3) . By induction, one easily sees that for each such pair e, e1 ∈ T all the letters that are in words left of the letter encoded by e1 are encoded in lexicographically smaller elements. Furthermore, the size of ((0 * )1) * ∩ T corresponds to the number of words in s since the introduction of a 1-successor corresponds to the separation of the first block of some blockline from the other blocks. Each of these separation can also be seen as the separation of the last word of the first block from the first word of the second block of this blockline. Note that we separate two words that are next to each other in exactly one blockline. Putting these facts together our claim is proved. Another view on this correspondence is the bijection f : {1, 2, . . . , |s|} → R where R := ((0 * )1) * ∩ dom(T ) and i is mapped to the i-th element of R in lexicographic order. f (i) is exactly the position where the (i -1)-st word is separated from the i-th one for all i ≥ 2. In order to state the properties of f , we need some more notation. We write π for the canonical projection π : (Σ × {1, 2} × N) * → (Σ × {1, 2}) * and w i for the i-th word of s. Furthermore, let w ′ i be a word such that, w i = (w i ⊓ w i-1 ) • w ′ i (here we set w 0 := ε). Then the word along the path3 from the root to f (i) is exactly π(w i ⊓ w i-1 ) for all 2 ≤ i ≤ |s| and the path from f (j) to f (j) • 0 m for maximal m ∈ N is π(w ′ j ) for all 1 ≤ j ≤ |s|. In order to encode a configuration c := (q, s), we add q as a new root of the tree and attach the encoding of s as the left subtree, i.e., Enc(c) := q(Enc(s), ∅).

(b, 2, 0) (b, 2, 0) (c, 1, 2) (d, 2, 3) (a, 2, 0) (a, 2, 0) (a, 2, 2) (a, 2, 2) (a, 2, 2) (⊥, 1, 0) (⊥, 1, 0) (⊥, 1, 0) (⊥, 1, 0) (⊥, 1, 0) c, 2 e, 1 b, 2 ε c, 1 d, 2 a, 2 a, 2 ε ε ⊥, 1 ε
The image of this encoding function contains only trees of a very specific type. We call this class T Enc . In the next definition we state the characterising properties of T Enc . This class is MSO definable, whence automata-recognisable. Definition 4.4. Let T Enc be the class of all trees T that satisfy the following conditions.

(1) The root of T is labelled by some element of Q (T (ε) ∈ Q).

(2) Every element of the form {0, 1} * 0 is labelled by some (σ, l) ∈ Σ × {1, 2}; especially, T (0) = (⊥, 1) and there are no other occurrences of (⊥, 1) or (⊥, 2). (3) Every element of the form {0, 1} * 1 is labelled by ε. (4) 1 / ∈ dom(T ), 0 ∈ dom(T ). ( 5) For all t ∈ T , if T (t0) = (σ, 1) then T (t10) = (σ, 1). Remark 4.5. Note that (5) holds as T (t0) = T (t10) = (σ, 1) would imply that the subtree rooted at t encodes a blockline l such that the first block of l induces a (σ, 1, n)-blockline and the second one induces a (σ, 1, m)-blockline. But as level 1 links always point to the preceding letter, n and m are equal to the length of the prefix of l in the stack plus 1, i.e., if T encodes a stack s then s = s 1 : [w \ l] : s 2 and n = m = |w| + 1. This would contradict the maximality of the blocks in the encoding.

(σ, l) ε . . . ε ε (τ, k) . . . (σ ′ , l ′ ) (σ, l) ε . . . ε
Remark 4.6. Enc : Q × Stck(Σ) → T Enc is a bijection and we denote its inverse by Dec.

Our encoding turns the transitions of a CPG into regular tree-operations. The treeoperations corresponding to pop 2 and collapse can be seen in Figures 4 and5. For the pop 2 , note that if v 1 is the 0-successor of v 0 then v 0 and v 1 encode symbols in the same word of the encoded stack. As a pop 2 removes the rightmost word, we have to remove all the nodes encoding information about this word. As the rightmost leaf corresponds to the topmost symbol of the stack, we have to remove this leaf and all its 0-ancestors.

For the collapse (on level 2), we note that each ε represents a cloned element. The collapse induced by such an element produces the same stack as a pop 2 of its original version. The original symbol of the rightmost leaf is its first ancestor not labelled by ε.

Note that the operations corresponding to pop 2 and collapse are clearly MSO definable. All other transitions in CPG correspond to MSO definable tree-operations, too. Due to space restrictions we skip the details. Lemma 4.7. Let C be the set of encodings of configurations of a CPS S. Then there are automata A (q,op) for all q ∈ Q and all op ∈ OP such that for all c 1 , c 2 ∈ C A (q,op) accepts Enc(c 1 ) ⊗ Enc(c 2 ) iff c 1 ⊢ (q,op) c 2 .

Recognising Reachable Configurations

We show that Enc maps the reachable configurations of a given CPS to a regular set. For this purpose we introduce milestones of a stack s. It turns out that these are exactly those substacks of s that every run to s has to visit. Furthermore, the milestones of s are represented by the nodes of Enc(s): with every d ∈ Enc(s), we can associate a subtree of s which encodes a milestone. Furthermore, the substack relation on the milestones corresponds exactly to the lexicographical order ≤ lex of the elements of Enc(s). For every d ∈ Enc(s) we can guess the state in which the corresponding milestone is visited for the last time by some run to s and we can check the correctness of this guess using MSO or, equivalently, tree-automata.

We prove that we can check the correctness of such a guess by introducing a special type of run, called loop, which is basically a run that starts and ends with the same stack. A run from one milestone to the next will mainly consist of loops combined with a finite number of stack operations.

Milestones

Definition 5.1 (Milestone). A substack s ′ of s = w 1 : w 2 : . . . : w n is a milestone if s ′ = w 1 : w 2 : . . . : w i : w ′ such that 0 ≤ i < n and w i ⊓ w i+1 ≤ w ′ ≤ w i+1 . We denote by MS(s) the set of milestones of s.

Note that the substack relation ≤ linearly orders MS(s).

Lemma 5.2. If s, t, m are stacks with m ∈ MS(t) but m ≤ s, then every run from s to t visits m. Thus, for every run r from the initial configuration to s, the function f : MS(s) → dom(r), s ′ → max{i ∈ dom(r) : r(i) = (q, s ′ ) for some q ∈ Q} is an order embedding with respect to substack relation on the milestones and the natural order of dom(r).

In order to state the close correspondence between milestones of a stack s and the elements of Enc(s), we need the following definition. LStck(d,s) is a substack of s for all d ∈ dom(Enc(s)). This observation follows from Remark 4.3 combined with the fact that the left stack is induced by a lexicographically downward closed subset. In fact, LStck(d, s) is a milestone of s.

Lemma 5.5. The map given by g : d → LStck(d, Enc(s)) is an order isomorphism between (dom(Enc(q, s)) \ {ε}, ≤ lex ) and (MS(s), ≤).

Lemmas 5.5 and 5.2 imply that every run r decomposes as r = r 1 • r 2 • . . . • r n where r i is a run from the i-th milestone of r(ln(r)) to the (i + 1)-st milestone.

In order to describe the structure of the r i , we have to introduce the notion of a loop. Informally speaking, a loop is a run r that starts and ends with the same stack s and which does not look too much into s. Definition 5.6. Let r be a run of length n with r(i) = (q i , s i ) for all 0 ≤ i ≤ n.

• r is called a simple high loop if s 0 = s n and if s 0 < s i for all 0 < i < n.

• r is called a simple low loop of s if s 0 = s n = s, between 0 and n the stack s is never visited, s 1 = pop 1 (s), CLvl(s) = 1, |s i | ≥ |s| for all 0 ≤ i ≤ n, and r↾ [2,n-1] is the composition of simple low loops and simple high loops of pop 1 (s). • r is called loop if it is a finite composition of low loops and high loops.

Lemma 5.7. Let s be some stack, m 1 , m 2 milestones of s, and r a run from m 1 to m 2 that never visits any other milestone of s.

Then either r = l 1 • p • l 2 or r = l 0 • c • l 1 • p 1 • l 2 • p 2 • l 3 • . . . • p n • l n+1
where each l i is a loop, and all p i , p, and c are runs of length 1, p performs one push σ,k , c performs one clone 2 , and the p i perform one pop 1 each.

This lemma motivates why we only define low loops for stacks s with CLvl(s) = 1. Whenever the topmost symbol of a milestone m is not a cloned element, then pop 1 (m) is another milestone. Hence, the l i can only contain low loops if they start at a stack with cloned topmost symbol. But any stack s with cloned topmost symbol and CLvl(s) = 2 cannot be restored from pop 1 (s) without passing pop 2 (s) since a push σ,2 -operation would create the wrong link-level.

From Lemma 5.7 we can derive that deciding whether there is a run from one milestone to the next is possible if we know the pairs of initial and final states of loops of certain stacks s. Hence we are interested in the sets Loops(s) ⊆ Q × Q with (q 1 , q 2 ) ∈ Loops(s) if and only if there is a loop from (q 1 , s) to (q 2 , s). The crucial observation is that Loops(s) may be calculated by a finite automaton reading top 2 (s).

Lemma 5.8. For every CPS there exists a finite automaton A that calculates4 on input w ∈ (Σ × {1, 2}) * the set Loops(s) for all stacks s such that w = π(top 2 (s)). Here, π : (Σ × {1, 2} × N) * → (Σ × {1, 2}) * is the projection onto the symbols and collapse-levels.

Detection of Reachable Configurations

We have already seen that every run to a valid configuration (q, s) passes all the milestones of s. Now, we use the last state in which a run r to (q, s) visits each milestone as a certificate for the reachability of (q, s). To be precise, a certificate for the reachability of (q, s) is a map f : dom Enc(q, s) \ {ε} → Q such that there is some run r from ⊥ 2 to (q, s) and f (d) = q if and only if r(i) = q, LStck(d) for i the maximal position in r where LStck(d) is visited. Lemma 5.9. For every CPG G, there is a tree-automaton that checks for each map f : dom(Enc(q, s)) \ {ε} → Q whether f is a certificate of the reachability of (q, s), i.e., whether f is induced by some run r from the initial configuration to (q, s).

The proof of the lemma uses Lemma 5.8 and the fact that the path from the root to some d ∈ Enc(s) encodes the topmost word of LStck(d, Enc(s)). Hence, a tree automaton reading Enc(s) is able to calculate for each position d ∈ Enc(s) the pairs of initial and final states of loops of LStck(d). As every run decomposes as a sequence of loops separated by a single operation, knowing Loops(s ′ ) for each s ′ ≤ s enables the automaton to check the correctness of a candidate for a certificate of reachability.

As a tree-automaton may non-deterministically guess a certificate of the reachability of a configuration, the encodings of reachable configurations form a regular set.

Extension to Regular Reachability

By now, we have already established the tree-automaticity of each CPG G since we have seen that our encoding yields a regular image of the vertices of G and the transition relations are turned into regular relations of the tree encoding. Using similar techniques, we can improve this result: Theorem 5.10. If G is the ε-closure of some CPG G ′ then (G, Reach) is tree-automatic where Reach is the binary predicate that is true on a pair (c 1 , c 2 ) of configurations if there is a path from c 1 to c 2 in G.

Remark 5.11. Each graph in the second level of the Caucal-hierarchy can be obtained as the ε-contraction of some level 2 CPG (see [START_REF] Carayol | The Caucal hierarchy of infinite graphs in terms of logic and higher-order pushdown automata[END_REF]) whence all these graphs are tree-automatic.

For a CPS S let R ⊆ ∆ * be a regular language over the transitions of S. As collapsible pushdown graphs are closed under products with finite automata even the reachability predicate Reach R with restriction to R is tree-automatic. Here, Reach R xy holds if there is a path from x to y in CPG(S) that uses a sequence of transitions in R. If A is the automaton recognising R, we obtain that Reach R (q, s)(q ′ , s ′ ) holds in CPG(S) iff Reach (q, q i ), s (q ′ , q f ), s ′ holds in CPG(S × A) where q i is the initial and q f the unique final state of A. Using this idea one can define a CPG G ′ which is basically CPG(S ∪ (S × A)) extended by transitions from (q, s) to ((q, q i ), s) and to ((q, q f ), s). CPG(S) as well as Reach R w.r.t. CPG(S) are FO[Reach]-interpretable in G ′ . Hence we obtain: Theorem 5.12. Given a collapsible pushdown graph of level 2, its FO[Reach R ] theory is decidable for each regular R ⊆ ∆ * .

Computation of concrete tree-automatic representations of CPG

Up to now, we have only seen that there is a tree-automatic representation for each CPG. For computing a concrete representation, we rely on the following lemma. Lemma 5.13. Given some CPS S = (Γ, Q, ∆, q 0 ), some q ∈ Q, and some stack s, it is decidable whether (q, s) is a vertex of CPG(S).

The proof is based on the idea that a stack is uniquely determined by its top element and the information which substacks can be reached via collapse-and pop i -operations. Hence we can construct an extension S ′ of S and a modal formula ϕ q,s such that there is some element v ∈ CPG(S ′ ) satisfying CPG(S ′ ), v |= ϕ q,s iff (q, s) ∈ CPG(S). S ′ basically contains new states for every substack of s and connects the different states via the appropriate pop ioperations which are only applied if the topmost symbol of the stack agrees with the symbol we would expect when starting the pop i -sequence in configuration (q, s).

From this lemma we can derive the computability of the automata in Lemma 5.8. Having obtained these automata, the construction of a tree-automatic representation of some CPG is directly derived from the proofs yielding the following theorem.

Theorem 5.14. There is an algorithm that, given a level 2 CPG G and regular sets R 1 , . . . , R n ⊆ ∆ * , computes a tree-automatic representation of (G, Reach R 1 , . . . , Reach Rn ).

Conclusion

We have seen that level 2 collapsible pushdown graphs are tree-automatic. This result holds also if we apply ε-contractions and if we add regular reachability predicates. This implies that the second level of the Caucal-hierarchy is tree-automatic. But our result can only be seen as a starting point for further investigations of the CPG hierarchy: are level 3 collapsible pushdown graphs tree-automatic? We know an example of a level 5 CPG which is not tree-automatic. But even when tree-automaticity of all CPG cannot be expected, the question remains whether all CPG have decidable FO theories. In order to solve this problem one has to come up with new techniques.

A rather general question concerning our result aims at our knowledge about treeautomatic structures. Recent developments in the string case [START_REF] Kuske | Theories of automatic structures and their complexity[END_REF] show the decidability of rather large extensions of first-order logic for automatic structures. It would be interesting to clarify the status of the analogous claims for tree-automatic structures. Positive answers concerning the decidability of extensions of first-order logic on tree-automatic structures would give us the corresponding decidability results for collapsible pushdown graphs of level 2.

  : ⊥a cl 1, ⊥ : ⊥a : ⊥a a a ′ 0, ⊥ : ⊥a : ⊥aa cl 1, ⊥ : ⊥a : ⊥aa : ⊥aa a ′ a . . . 2, ⊥ : ⊥a p co 2, ⊥ : ⊥a : ⊥aa p co 2, ⊥ : ⊥a : ⊥aa : ⊥aaa p co . . . 2, ⊥ : ⊥ 2, ⊥ : ⊥a : ⊥a p co 2, ⊥ : ⊥a : ⊥aa : ⊥aa p co . . . 2, ⊥ : ⊥a : ⊥ 2, ⊥ : ⊥a : ⊥aa : ⊥a p co . . . 2, ⊥ : ⊥a : ⊥aa : ⊥ . . .

Figure 1 :

 1 Figure 1: Example of a collapsible pushdown graph

Figure 2 :

 2 Figure 2: Example of blocks in a stack. These form a c-blockline.

Figure 3 :

 3 Figure 3: A stack s and its encoding Enc(s): right arrows lead to 1-successors (right successors), upward arrows lead to 0-successors (left successors).

Figure 4 :Figure 5 :

 45 Figure 4: pop 2 -operation

Definition 5 . 3 .

 53 Let T ∈ T Enc be a tree and d ∈ T \ {ε}. Then the left and downward closed tree induced by d is LT (d, T ) := T ↾ D where D := {d ′ ∈ T : d ′ ≤ lex d} \ {ε}. Then we denote by LStck(d, T ) := Dec(LT (d, T )) the left stack induced by d. Remark 5.4.

see Figure2for an example of blocks and Definition 4.1 for their formal definition

By the word along a path from one node to another we mean the word consisting of the non ε-labels along this path.

We consider the final state reached by A on input w as the value it calculates for w.

This work is licensed under the Creative Commons Attribution-NoDerivs License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nd/3.0/.


Franck Chauvel

Olivier Barais

Jean-Marc Jézéquel

Isabelle Borne

A Model-Driven Process for Self-Adaptive Software

Keywords: Component-Based Systems, UML, Self-Adaptation, Simulation, Code Generation

Many Embedded Systems are supposed to run continuously, which includes recovering from errors by adapting their configuration or their architecture to changing conditions in their environment. The design of such systems has to relate some high-level extra-functional properties to some low level ones such as memory or CPU consumption by defining some complex feed-back loops for the dynamic adaptation of the system. However, the design of such feed-back loops (also called "adaptation policies") is still a very complex endeavour if you want to go beyond predefined fallback modes. Since the expression of extra-functional properties and the design of adaptation policies are complex activities, they are generally delayed down to implementation time. Adaptation policies are then implemented without either high level design nor dedicated tests, which may lead to costly roll-back operations in the design process.

To avoid such roll-back operations, we suggest a model-driven process based on new executable meta-modelling techniques. At modelling time, designers have to complement the architectural description with some sensors and actuators related to the involved extra-functional properties. It allows designers to specify in a consistent way the related adaptation policies. Then since the model is executable, some simulations of the adaptation policies can be performed at design time to evaluate their performances with respect to some relevant test scenarios.

Then, using model-driven transformations, it allows the generation of code skeletons for real-time embedded platforms. In this article we illustrate our approach with a simple case study based on a mobile video player that is able to adapt its architecture to varying conditions, such as bandwidth evolution or low battery conditions.

Introduction

Embedded systems are designed to provide specific services rather that general purpose software. Most embedded systems are deployed on hardware that is expected to run continuously for many years and which needs to recover when errors occur. Designing such systems implies to describe the quality of the provided services according to the resources and the services provided by the environment. Specifications for embedded software typically entail high-level quality requirements specified by the user. While these are related to the application domain, they also often have low level performance implications. For example, a videoplayer might be required to provide acceptable quality (defined, e.g. in terms of frame rate and resolution) through some video playback. Such requirements can be maintained using adaptation policies that try to maximise the quality in response to the environment changes. While several approaches make it possible to relate high level extra-functional properties to low-level concerns [START_REF]UML profile for schedulability, performance and time specification[END_REF][START_REF]UML profile for quality of service and fault tolerance characteristics and mechanisms[END_REF][START_REF] Shen | Performance nalysis of UML models using aspect-oriented modelling techniques[END_REF][START_REF] De | UML extensions for the specification and evaluation of latency constraints in architectural models[END_REF], none of them take into account adaptable component-based systems, where this relation is dynamic because it might depend on sophisticated adaptation policies introducing complex feedback loops by having a deep impact on the behaviour of some components or even on the component architecture itself.

In this paper we propose a tool supported approach allowing the development of such arbitrary complex adaptation policies. Our work is focused on component-based software architectures expressed using a subset of the UML2.0 notation [START_REF]Unified Modelling Language 2.0: Superstructure specification[END_REF] in which we enable the definition and simulation of adaptation policies. We propose to reify extra-functional concerns into so-called extra-functional components encapsulating both the monitoring of the relevant properties and the adaptation policies. Building on recent advances in executable meta-modelling techniques, these component-based architectures can be given operational semantics encompassing both functional and extra-functional aspects. This operational semantics then makes it possible to run simulations in order to get performance estimates with respect to some operational profiles.

The rest of the paper is organised as follows. Section 2 starts by introducing the motivating example of a hand-held wireless video player where the designers are interested in trying to maximise the frame rate while the bandwidth changes. It then describes how this video player can be modelled and given an operational semantics, taking into account both functional and extra-functional aspects, including for its adaptation policies. Section 4 shows how this model can be used in conjunction with an operational profile to get early performance evaluation of competing adaptation policies. Section 4 discusses the advantages and the drawbacks of our approach whereas Section 5 presents a model transformation which enables the generation of code skeleton for the Fractal platform. Section 6 discusses related works and the paper finishes with some conclusions and perspectives.

Motivations and overview of the process

Motivations

We propose a wireless video player as a running example for illustrating the ideas presented in this paper. This video player's main function is to stream a video downloaded from a wireless network. Figure 1 presents a possible architecture for that kind of video player. Since the video player component is dedicated for deployment on mobile devices where the environment might change quickly, designers need to include adaptation policies in order to maximise the quality of the provided service. According to the literature about multimedia streaming [START_REF] Cranley | User perception of adapting video quality[END_REF], the main user-perceived quality property is called the Frame Rate and corresponds to the number of video frames that the system is able to process per unit of time. If the frame rate is very high, then the movie seems to be fluent whereas if the frame rate falls, then the movie becomes jerky. Under a highly dynamic environment, one of the parameter which can impact the frame rate is the bandwidth available for downloading the video. The contribution of this paper is to enable the development of the adaptation policy which ensure the a high frame rate while the bandwidth decreases by adapting the architecture of the system.

Overview of the process

The process we suggest is introduced by the figure 2. It divides the development of self-adaptive software into 6 steps which are described in the remainder of the paper.

1. The first step consists in building the architecture without any consideration for the adaptation policies. We use a subset of the UML notation, including component diagram for the structural view, activity diagrams and statecharts for the behavioural aspects, and class diagram to describe the data. 2. Then, the designer needs to complete the architecture with some probes which measures the extra-functional properties that he wants to involve in the adaptation policies. We use the same language (the subset of UML) to design the probes used in the architecture. 3. The third step is devoted to complete the design with the self-adaptation policies which drive the response of the system to changes in the system or in the environment. We use a rule-based language to describe adaptation policies. 4. Once the full self-adaptive system has been described, it must be validated in order to avoid cost effective rollback operations in the development process. We use a simulation-based approach which enables a high level and abstract simulation at design time to validate the adaptation policies.

5.

When the self-adaptation policies have been validated, then the architectural model can be transformed into a platform model. This platform model reflects the specific characteristics of a component-based platform such as CORBA or Fractal. 6. From this platform model, executable code skeletons can be generated. This code generation is mainly focussed on the structural view but the interfaces between probes, functional architecture and the selfadaptation policies are preserved. Moreover, the adaptation policy described by rules can be directly interpreted by the an ad hoc Fractal extension that we have developed.

Component Architecture Design

Architecture Model Simulation

Executable Code Generation

Self-Adaptive Architecture Platform Model

Probes Design

Adaptation policies Design

Architecture Model

Platform Model Generation

Executable Code In order to be able to simulate component-based architectures, and thus to get performance results of adaptation policies, it is necessary to describe architecture in a precise and operational way. Components are described using three main points of view, namely the structural view, the behavioural view and the data view.

The structural view allows designers to group functionalities expressed as services on components. These components are the basic elements of the system and will be put together to build more complex collaborations encapsulated into composite components as shown in Figure 1. Figure 3 gives the structural view of the Demultiplexer component. It defines three ports, namely the input port which provides the data to process, the audioOutput port and the videoOutput port. Each port is typed by a set of provided or required interfaces which define the services provided (or required) by the port. The behavioural view enables the use of both statechart diagrams and activity diagrams to describe the different behaviours of a component. Statecharts are used to describe the coordination between the features that are provided by the component whereas activity diagrams are used to describe the internal use of the features that are required by the component. The link between statecharts and activities is set in both states and transitions. Transitions link an event to an activity whereas states might refer to an exit (or an entry) activity that will be performed by exiting (or entering) from the state. The goal of the behavioural view is to abstract away the functional processing performed by the component. Figure 5 shows an excerpt of the behavioural view of the Demultiplexer component.

The left part presents the process which handles the reading of the data on the input port whereas the details of the activity which is performed when some new data have been read on this port.

Modelling probes for extra-functional properties

In order to model the behaviour related to selfadaptation, the designer must deal with extrafunctional properties such as memory consumption for instance. These properties must be reified in the architecture as well as the others services which have been designed to provide functional services. For instance, if the designer wants to address the memory consumption, then he needs to design a service devoted to measure the current amount of free memory. This reification of extra-functional properties as functional services can be boiled down to the development of specific probes (sensor and/or actuators). Such probes are included in a real selfadaptive system to measure extra-functional properties. However, the large amount of technical details required to design such probes fall out of the scope of early design activities. What the designer need is to reflect the expected behaviour of the probe.

We describe probes as basic components and then connect them into the functional architecture. In the video player example, since the objective is to maximise the frame rate with respect to the available bandwidth, both of these two quality properties need to be reified.

Figure 6 -A possible design for the bandwidth probe

In order to make the probes effective, the designer needs to insert them into the architectures. This kind of hand-crafted "weaving" is applied at two levels:

• At the structural level, the probes which appears as component are connected to the rest of the architecture through ports and connectors

Modelling Self-Adaptation behaviour

Finally the designer must describe the selfadaptation behaviour, that is to say, the way he wants the system to respond to changes in the environment. In the video player for instance, the objective is to keep the frame rate as high as possible even if the bandwidth falls and this can be achieve by several fall-backs actions. First, the loss rate of the image encoding can be increased in agreement with the streaming server. Moreover, grey scale pictures can be used to save bandwidth if the bandwidth is still decreasing. Finally, if the bandwidth available is too low, then it is possible to dynamically change the component used for decoding. The system can switch from an MPEG2 to an MPEG4 data stream to save bandwidth. The self-adaptation policies are described as the behaviour of composite components. A composite component (such as the video-player) encapsulates collaboration between several components and it must be in charge of maintaining the correct configuration of the collaboration. For instance, since the main objective of the video-player is to maintain the frame rate as high as possible with respect to the bandwidth evolution, the video-player itself (the composite component) is in charge of updating the architecture. This self-adaptation policy is described using a rulebased notation where each rule describes how to react to event coming from probes or from other components. Events are mapped on asynchronous calls received by composite component.

Policy when

ExcellentBandwidth then setLowLossRate when HighBandwidth then setColorMode then setHighLossRate when MediumBandwidth then setGreyScaleMode then setMPEG2Decoder when lowBandwidth then setMPEG4Decoder end The previous example shows one adaptation policy that reacts to changes in the bandwidth. Four discrete ranges of bandwidth have been chosen to represent the space of bandwidth. For instance the threshold between the high and medium rate might be set to 100kbps and the threshold between low and medium rate might be set to 50kbps. In order to impact the frame rate, designers identified some actions, such as increasing the compression rate of the image encoding, decreasing the colour depth, or loading a different component that encapsulates a different compression (and decompression) algorithm. In order to enable the execution of the selfadaptation policy, composite components need to communicate directly with their sub components. Each component is completed with a special port which is devoted to communication with the composite component, that is to say the component which contains it. Figure 10 shows a part of the structure of the video player completed which those specific ports. Thus, a composite component can react to events or messages which come from probes but also from messages which come from functional components.

StreamDemultiplexer

Early Validation using Simulation

The description of the component-based architecture used (see Section 3.1) is detailed enough to be simulated: the structure, the behaviour and the data of each component are described.

All the concepts which are involved in the description of software component have been described into a specific meta-model. This meta-model allows designers to describe the component architecture they want to build and to record it into a component model.

To simulate these architectural models, an operational semantic has been added to the metamodel. It enables the animation of any architectural model, since the behaviour of components is included in the architectural model. The Kermeta language [START_REF] Muller | Weaving executability into objectoriented meta-languages[END_REF] which enables the description of an operational semantic of a meta-model has been used to implement the meta-model and its semantic. However for the sake of conciseness this metamodel and it semantics are shown in this paper.

As explained in the section 3.1, the meta-model which as been used to capture component-based architecture share a lot of concept with the UML2.0 meta-model. The semantic which has been chosen for our meta-model freezes some "semantic choices" for every semantic variation points concerned in the UML meta-model. For the sake of conciseness, all these variation points are not described in this paper, but the reader can refer to [START_REF] Chauvel | Code generation from UML models with semantic variation points[END_REF] to get more details about the management of semantic variation points.

The simulation of a component-based architecture which includes some adaptation policies might be done in 2 steps: 1. Model the self-adaptive component-based architecture and the adaptation policies which need to be validate. 2. Define an operational profile which will drive the simulation by defining the behaviour of environment of the architecture under test.

3. Simulate the architectural model using the simulator

Definition of operational profiles

An operational profile is a description of the environment around the architecture under test. For instance, it might be relevant to test the efficiency of the adaptation policies under an environment where the bandwidth is decreasing until it becomes very low. Such a scenario exercises adaptation policy and might happen if the user is moving far from the data source.

Operational profiles are described as stub components which close the architecture. An operational profile must provide a "test stub" port for each pending port in the component under test. Thus, the operational profile defines a test scenario which includes a sequence of calls to the features offered by the component under simulation. In the simulation we write to illustrate our simulator, every twenty simulation cycles, the operational profile decreases the bandwidth available for the video player component.

In this example we consider that the designer of our video player plans to deploy its video player on two kinds of platform: the first one enables high-level architectural adaptation actions (replacing the MPEG2 decoder by an MPEG4) whereas the second one is more basic and does not enables such actions. So the designer derives a second adaptation policy from the first one removing the actions which updated the architecture. He has to check to the performance of this new adaptation policy.

To sum up, the first adaptation policy decreases the loss rate, then switches to a grey scale mode and finally switches from an MPEG2 to an MPEG4 codec. The second adaptation policy is simpler and starts as well by decreasing the loss rate and then decreases the colour rate, but it does not switch from an MPEG2 codec to an MPEG4 codec. So the second adaptation policy does not include any architectural actions and can be deployed on a simpler execution platform than the first one.

Simulation results

Figures 11 and12 show the evolution of the frame rate with respect to the bandwidth changes. The frame rate that is measured throughout the simulation as the number of simulation cycles used to process a frame. In the following figures, we convert it as the number of frames processed by simulation step. Figure 11 presents the simulation obtained with a component that uses no adaptation policy. In this case, we use the BandwidthMonitor and the FrameRateMonitor components just for measuring the evolution of the frame rate. The frame rate is increasing as a function of the bandwidth. Figure 12 shows the result of the simulation of our two adaptation policies. In the figures 11 and 12, we can see the three levels of bandwidth which have been specified in the operational profile. As explained, in this simulation, the bandwidth is decreasing from a high level to a low one and simulation results show the performance of each adaptation policy (as a frame rate measurement). The first adaptation policy maintains the frame rate when the bandwidth falls and even if the bandwidth becomes low.

The second adaptation policy keeps the frame rate when the bandwidth is "medium" and just reduces the frame rate increase when the bandwidth is low. Since this adaptation policy does not use any architectural actions it can be deployed on a simpler (and cheaper) execution platform but the final product will not support a very low bandwidth. However the results shown in this section are simple but illustrate our approach. In an industrial casestudy, a set of simulations must be performed for each operational profile in order to get representative statistical data.

Code Generation for Fractal

The code generation has been developed as a two stages model transformation. First, the architecture description is mapped on a model of the platform such as a meta-model of the Fractal component model. Then, code generation is performed from this platform model to produce executable code.

Fractal is component based model which has been implemented in several ways. The main implementation is named Julia and is based on the Java language.

From architectural model to platform model

The transformation which produces a Fractal model from the description which has been introduced previously mainly concerns the structural aspects.

• The structural view is directly transformed into the structural concept of the Fractal platform. Each component is mapped onto a Fractal component and since Fractal is a hierarchical model, the hierarchy of component is maintained. Our model includes multiple ports on component (but not multiplicity on connector ends) and we use interface name to reify ports into the Fractal model. • The description of the data handled by component cannot be used in the transformation. Indeed, that description is mainly included for the simulation purpose and it is an abstraction of the real data that will be processed by the system at run time. • The behavioural view is currently not either used and the transformation which remains mainly focused on structural aspects. The Fractal model does not include any behavioural artefacts which would enable the reification of the behavioural description on the platform level. 5.2 From model platform to executable code We implement a basic transformation which enables to Java code generation from the Fractal model. The challenge here is to map the component structure on the object-oriented model used in the Java implementation of Fractal. For instance, our high level description enables the description of component which implements a service in two Moreover, in order to make effective the adaptation policies, we have developed an extension of the Fractal platform which is able to directly execute rule-based adaptation policies as they are described into the section. Then, developers just need to complete the code skeletons of the functional components and of the probes to get the final executable artefacts.

Related Work

Balsamo and al. [START_REF] Balsamo | Model-based performance prediction in software development: A survey[END_REF] survey several approaches to compute performance predictions on software models, and especially on UML models. Several approaches used queuing network-based methodologies; others use Stochastic Petri Nets, yet others are based on simulation. For the sake of conciseness we have selected here the most representative works on the area. To describe extra-functional requirements, the OMG provides two specific UML profiles called SPT 1 and QoS. The SPT Profile [START_REF]UML profile for schedulability, performance and time specification[END_REF] was a first attempt to extend UML with basic property definitions concerning time and performance. The QoS Profile [START_REF]UML profile for quality of service and fault tolerance characteristics and mechanisms[END_REF], allows UML users to define a wide variety of extra-functional requirements. With these two profiles, one can annotate UML models with metrics that can be used to conduct performance analysis such as in [START_REF] Shen | Performance nalysis of UML models using aspect-oriented modelling techniques[END_REF]. Then these UML models are processed to obtain performance models (as Layered Queuing Networks) on which performance analysis can be conducted. Here, as the performance model is obtained by model transformations, there is no dynamic feedback possible between the performance model and the UML model, to take into account any architectural reconfigurations such as the one that is performed to change codecs in our example. Another way to obtain performance analysis on UML models is described in [START_REF] De | UML extensions for the specification and evaluation of latency constraints in architectural models[END_REF]. As in previous approaches, the UML models are annotated using an ad-hoc profile, and then, transformed into a simulable model. Here, as the simulated model is the result of the Analysis Model Generator, the behaviour described in the original model cannot impact the quality attributes which are defined thanks to the profile. Thus, no feedback is possible between the quality information and the adaptation policies. Based on ROOM and UML-RT, the work of V. Cortellessa [START_REF] Cortellessa | Performance modeling and validation of a software system in a RT-UML-based simulative environnement[END_REF][START_REF] Vittorio Cortellessa | On the adequacy of UML-RT for performance validation of an sdh telecommunication system[END_REF] enables the design of hardware resources in an object-oriented way. Then, on the functional side, the behaviours (expressed as statecharts) can be annotated with requests to the objects that represent the hardware resources. This approach enables some resource consumption prediction on ROOM models. Here we suggest to extend this approach to the Profile for Schedulability, Performance and Time express not only resources requests but also full component-based reconfiguration, including functional and extrafunctional reconfiguration and to test them. Many Architecture Description Languages (ADLs) have been suggested in the literature [START_REF] Medvidovic | A classification and comparison framework for software architecture description languages[END_REF], such as ACME [START_REF] Garlan | Acme: An architecture description interchange language[END_REF], Darwin [START_REF] Magee | Specifying distributed software architectures[END_REF], ArchWare ADL [START_REF] Morrison | Support for evolving software architectures in the archware ADL[END_REF], Wright [START_REF] Allen | Specifying and analyzing dynamic software Architectures[END_REF], SOFA [START_REF] Plasil | Behavior protocols for software components[END_REF] and many others. All of them allow designers to address the structural features of component-oriented architectures and some of them have been extended to provide a way to describe the dynamics of the system such as Dynamic ACME, Dynamic Wright. However it is not possible in these approaches to manage component reconfiguration and to link it with functional behaviour. Some works have already addressed the issue of specifying the dynamic reconfiguration of component-based architectures and many of them are surveyed into [START_REF] Bradbury | A survey of selfmanagement in dynamic software architecture specifications[END_REF]. Among this, Allen and al. [START_REF] Allen | Specifying and analyzing dynamic software Architectures[END_REF] present an extension of Wright which allows designers to deal with component-based reconfiguration but only on the functional side: nothing is suggested to deal with extra-functional properties. Batista and al. present in [START_REF] Thaıs | Managing dynamic reconfiguration in component-based systems[END_REF] an extension of ACME to specify reconfiguration for a reflective component runtime called OpenCOM. There again,nothing is provided to link reconfiguration policies with QoS information at design time.

Conclusion

To design embedded systems, it is necessary to deal with high-level quality requirements which are often specified by the final user. Meeting these requirements has a lot of low-level quality implications such as memory or bandwidth consumption. Designers of such systems need to describe adaptation policies that maximise high-level quality properties with respect to changes in the lowlevel ones. However these adaptation policies are the result of various design choices that might have a deep impact on the final executable artefact and any rollback operation in such a design process has a very high cost. To avoid such problems, designers need to get support for the development of adaptation policies at design time. The approach presented in this paper is based on new executable meta-modelling techniques which enable the creation of process devoted to support the development of self-adaptive systems. The use of a subset of the UML2.0 standard, makes possible to get early simulation results from componentbased models which include adaptation policies. To keep models executable throughout the design process, each quality property that is involved in adaptation policy is reified with a component which is able to monitor it. Then, the side effects of the functional behaviour of each component are described using service calls between functional and extra-functional components. With all the required elements reified in the design model, adaptation policies can be described as behaviours of composite components. Executable models allow designers to perform simulation according to a specific operational profile that describes a test scenario. This approach enables to get suitable results to check if adaptation policies meet the high-level requirements or to select a particular adaptation policy among the set of possible ones. Then a model transformation allows designers to get code skeletons where the adaptation policies have been fully generated but where the functional components and the probe components must be implemented.

Figure 1 -

 1 Figure 1 -A possible software architecture of a video player Since video decoding is a data-oriented process, the video-player system is shown as a composite component which encapsulates a collaboration between several sub-components where each subcomponent represents a step of the process. 1. A StreamSource component reads data from a file or from the network. 2. A Demultiplexer component separates the audio stream from the video stream. 3. Each stream is decoded by the relevant Decoder component. 4. A Synchroniser sends audio and video data to relevant renderers while managing the synchronisation between the two streams. 5. A Controller component propagates the user command to the process.

Figure 2 -

 2 Figure 2 -The model driven process devoted to self-adaptive systems

Figure 3 -Figure 4 -

 34 Figure 3 -The structural view of the Stream-Demultiplexer component depicted as a UML component diagramThe data view describes the data processed or stored by a component as a class diagram. These data might contain operations but only as passive objects, that is to say objects which cannot call any external features. Figure4presents the data used by Demultiplexer component as a class diagram attached to it. It defines 3 buffers: one for recording the data read on the input port, and two other ones for recording the audio and video data which have just been demultiplexed.

Figure 5 -

 5 Figure 5 -The behavioural view of the StreamDemultiplexer component

Figure 8 -

 8 Figure 8 -The behavioural view updated with the side effects of the functional behaviour.

Figure 9 -

 9 Figure 9 -The video player architecture with the "configuration port" which enable the communication between the composite component and its sub components

Figure 11 -

 11 Figure 11 -The simulation results obtained without deploying any adaptation policy.

Figure 12 -

 12 Figure 12 -Simulation results obtained with adaptation policies.Figure12shows the result of the simulation of our two adaptation policies. In the figures 11 and 12, we can see the three levels of bandwidth which have been specified in the operational profile. As explained, in this simulation, the bandwidth is decreasing from a high level to a low one and simulation results show the performance of each adaptation policy (as a frame rate measurement). The first adaptation policy maintains the frame rate when the bandwidth falls and even if the bandwidth becomes low. The second adaptation policy keeps the frame rate when the bandwidth is "medium" and just reduces the frame rate increase when the bandwidth is low. Since this adaptation policy does not use any

Figure 103 -

 103 Figure 103 -A pattern used to implement multiple implementations of the same interfaceFigure13shows the pattern which is applied to resolve multiple implementations of the same interface. A new class is created for each port of the component which implements the specific interface(s). These specific classes are connected to the component class which provides various implementations under different names (performServiceAdmin, performServiceUser). Then, the standard methods of the Component interface and of the BindingController interface must overridden to use the port objects. Moreover, in order to make effective the adaptation policies, we have developed an extension of the Fractal platform which is able to directly execute rule-based adaptation policies as they are described into the section. Then, developers just need to complete the code skeletons of the functional components and of the probes to get the final executable artefacts.

•

  At the behavioural level, the designer needs to update the behaviour of each component in order to reflect the side effects of the functional behaviour on the extra-functional properties.

	bandwidth		dataSource
				Video Player
			dataSource	ctrl	source	user
		StreamSource	reader	Controller
			output		synchro
	context	user[*]	input
	Bandwidth Monitor	StreamDemultiplexer
		videoOutput	audioOutput
		input	input
	VideoDecoder	AudioDecoder
	output		output
		videoInput	audioInput
				ctrl
	FrameRate Monitor	StreamSynchroniser	clock	clock
		videoOutput	audioOutput
		videoOutput	audioOutput

bandwidth user frameRate Figure 7 -The structural view of the video player component updated with the two probes components

  Figure7shows the structural view of the videoplayer where two probes have been added. The first one (BandwidthMonitor) measures the bandwidth consumption and is connected to the StreamSource component. The second one (FrameRateMonitor) measures the frame rate and is connected to the StreamSynchronizer component. On the behavioural view, the behaviours of both the StreamSource and StreamSynchronizer have been updated. Figure8shows the way we have completed the behavioural view. The ReadData activity of the StreamDemultiplexer component as been updated with two activities which computes the amount of bandwidth needed to read data on the network. The left part of the figure shows that the Synchronize activity of the FrameRateMonitor when a new frame is ready to be displayed.

call input.

readData ReadData Activity result bandwidth.request Compute Request Store Data Notify ouput.startReadData request data request Synchronize Activity call audioInput.readData call videoInput.readData call audioInput.readData call videoInput.readData Notify framerate.synchronized

	(from StreamReader Component)	(from Synchronizer Component)
		result	result
		audioData	videoData


Nader H Bshouty
email: bshouty@cs.technion.ac.il

Hanna Mazzawi

OPTIMAL QUERY COMPLEXITY FOR RECONSTRUCTING HYPERGRAPHS

In this paper we consider the problem of reconstructing a hidden weighted hypergraph of constant rank using additive queries. We prove the following: Let G be a weighted hidden hypergraph of constant rank with n vertices and m hyperedges. For any m there exists a non-adaptive algorithm that finds the edges of the graph and their weights using O " m log n log m « additive queries. This solves the open problem in [S. Choi, J. H. Kim. Optimal Query Complexity Bounds for Finding Graphs. STOC, 749-758, 2008]. When the weights of the hypergraph are integers that are less than O(poly(n d /m)) where d is the rank of the hypergraph (and therefore for unweighted hypergraphs) there exists a non-adaptive algorithm that finds the edges of the graph and their weights using O m log n d m log m ! .

additive queries.

Using the information theoretic bound the above query complexities are tight.

Introduction

In this paper we consider the following problem of reconstructing weighted hypergraphs of constant rank 1 (the maximal size of a hyperedge) using additive queries: Let G = (V, E, w) be a weighted hidden hypergraph where E ⊂ 2 V , |e| is constant for all e ∈ E, w : E → R, and n is the number of vertices in V . Denote by m the size of E. Suppose that the set of vertices V is known and the set of edges E is unknown. Given a set of vertices S ⊆ V , an additive query, Q G (S), returns the sum of weights in the sub-hypergraph induced by S. That is,

Q G (S) = e∈E∩2 S
w(e).

Our goal is to exactly reconstruct the set of edges using additive queries. 1: Results for weighted and un-weighted hypergraphs with optimal query complexity.

† A non-optimal adaptive query complexity algorithm for Hypergraph can be found in [START_REF] Choi | Almost Tight Upper Bound for Finding Fourier Coefficients of Bounded Pseudo-Boolean Functions[END_REF]. § A non-optimal non-adaptive query complexity algorithms can be found in [START_REF] Indyk | Near-Optimal Sparse Recovery in the L1 Norm[END_REF] and the references within it.

One can distinguish between two types of algorithms to solve the problem. Adaptive algorithms are algorithms that take into account outcomes of previous queries while nonadaptive algorithms make all queries in advance, before any answer is known. In this paper, we consider non-adaptive algorithms for the problem. Our concern is the query complexity, that is, the number of queries needed to be asked in order to reconstruct the hypergraph.

The hypergraph reconstructing problem has known a significant progress in the past decade. For unweighted hypergraph of rank d the information theoretic lower bound gives

Ω m log n d m log m
for the query complexity for any adaptive algorithm for this problem. Many independent results [START_REF] Djackov | On a search model of false coins[END_REF][START_REF] Grebinski | Optimal Reconstruction of Graphs Under the Additive Model[END_REF][START_REF] Rykov | On a Coding Model for a Multiple-Access Adder Channel[END_REF][START_REF] Biglieri | Multiple Access Channels Theory and Practice Volume 10 NATO Security through Science Series -D: Information and Communication Security[END_REF] 2 have proved a tight upper bound for hypergraph of rank 1, i.e., loops. A tight upper bound was proved for some subclasses of unweighted hypergraphs of rank two, i,e., graphs (Hamiltonian graphs, matching, stars and cliques etc.) [START_REF] Grebinski | On the Power of Additive Combinatorial Search Model[END_REF][START_REF] Grebiniski | Reconstructing a hamiltonian cycle by querying the graph: Application to DNA physical mapping[END_REF][START_REF] Grebinski | Optimal Reconstruction of Graphs Under the Additive Model[END_REF][START_REF] Bouvel | Combinatorial Search on Graphs Motivated by Bioinformatics Applications: A Brief Survey[END_REF], unweighted graphs with Ω(dn) edges where the degree of each vertex is bounded by d [START_REF] Grebinski | Optimal Reconstruction of Graphs Under the Additive Model[END_REF], graphs with Ω(n 2 ) edges [START_REF] Grebinski | Optimal Reconstruction of Graphs Under the Additive Model[END_REF] and then the former was extended to d-degenerate unweighted graphs with Ω(dn) edges [START_REF] Grebinski | On the Power of Additive Combinatorial Search Model[END_REF], i.e., graphs that their edges can be changed to directed edges where the out-degree of each vertex is bounded by d. A recent paper by Choi and Kim, [START_REF] Choi | Optimal Query Complexity Bounds for Finding Graphs[END_REF], gave a tight upper bound for all unweighted graphs. In this paper we give a tight upper bound for all unweighted hypergraphs of constant rank. Our bound is tight even for weighted hypergraphs with integer weights |w| = poly(n d /m) where d is the rank of the hypergraph.

For weighted hypergraph of constant rank with unbounded weights the information theoretic lower bound gives Ω m log n log m

In [START_REF] Choi | Optimal Query Complexity Bounds for Finding Graphs[END_REF], Choi and Kim prove a tight upper bound for loops (hypergraph of rank 1). For weighted graphs (hypergraph of rank 2) Choi and Kim, [START_REF] Choi | Optimal Query Complexity Bounds for Finding Graphs[END_REF], proved the following: If m > (log n) α for sufficiently large α, then, there exists a non-adaptive algorithm for reconstructing a weighted graph where the weights are real numbers bounded between n -a and n b for any positive constants a and b using O m log n log m queries.

In [START_REF] Bshouty | Reconstructing Weighted Graphs with Minimal Query Complexity[END_REF], Bshouty and Mazzawi close the gap in m and proved that for any weighted graph where the weights are bounded between n -a and n b for any positive constants a and b and any m there exists a non-adaptive algorithm that reconstructs the hidden graph using O m log n log m queries. Then in [START_REF] Bshouty | On Parity Check (0, 1)-Matrix over Zp[END_REF] they extended the result to any weighted graph with any unbounded weights.

In this paper extend all the above results to any hypergraph of constant rank, i.e., the edges of the graph has constant size. This solves the open problems in [START_REF] Choi | Optimal Query Complexity Bounds for Finding Graphs[END_REF][START_REF] Bshouty | Reconstructing Weighted Graphs with Minimal Query Complexity[END_REF][START_REF] Bshouty | On Parity Check (0, 1)-Matrix over Zp[END_REF].

The paper is organized as follows: In Section 2, we present notation, basic tools and some background. In Section 3, we prove the main result.

Preliminaries

In this section we present some background, basic tools and notation. For an integer r let [r] be the set {1, 2, . . . , r}. For S ⊂ [r] we define x S ∈ {0, 1} r where x S i = 1 if and only if i ∈ S. The inverse operation is S x = {i | x i = 1}. We say that x 1 , . . . , x d ∈ {0, 1} n are pairwise disjoint if for every i = j, we have x i * x j = 0 where * is component-wise product of two vectors. For a prime p and integers a and b we write a = p b for a = b mod p. We will also allow p = ∞. In this case a and b can be any real numbers and a = ∞ b will mean a = b as real numbers.

d-Dimensional Matrices

A d-dimensional matrix A of size n 1 × • • • × n d over a field F is a map A : d i=1 [n i ] → F. We denote by F n 1 ו••×n d the set of all d-dimensional matrices A of size n 1 × • • • × n d . We write A i 1 ,...,i d for A(i 1 , . . . , i d ).
The zero map is denoted by 0

n 1 ו••×n d . The matrix B = (A i 1 ,i 2 ,...,i d ) i 1 ∈I 1 ,i 2 ∈I 2 ,...,i d ∈I d where I j ⊆ [n j ], is the |I 1 | × • • • × |I d | matrix where B j 1 ,...,j d = A ℓ 1 ,.
..,ℓ d and ℓ i is the j i th smallest number in I i . When I j = [n j ] we just write j and when I j = {ℓ} we just write j = ℓ. For example,

(A i 1 ,i 2 ,...,i d ) i 1 ,i 2 =ℓ,i 3 ∈I 2 ,...,i d ∈I d = (A i 1 ,i 2 ,...,i d ) i 1 ∈[n 1 ],i 2 ∈{ℓ},i 3 ∈I 2 ,...,i d ∈I d .
When

n 1 = n 2 = • • • = n d = n then we denote F n 1 ו••×n d by F × d n and 0 n 1 ו••×n d by 0 × d n .
We say that the entry

A i 1 ,i 2 ,...,i d is of dimension r if |{i 1 , . . . , i d }| = r.
For d-dimensional matrix A we denote by wt(A) the number of points in d i=1 [n i ] that are mapped to non-zero elements in F. We denote by wt r (A) the number of points in d i=1 [n i ] of dimension r that are mapped to non-zero elements in F. Therefore,

wt(A) = wt 1 (A) + wt 2 (A) + • • • + wt d (A). We denote by A d,m the set of d-dimensional matrices A ∈ F × d n where wt d (A) ≤ m and A ⋆ d,m the set of d-dimensional matrices A ∈ F × d n where 1 ≤ wt d (A) ≤ m. For d-dimensional matrix A of size n 1 × • • • × n d and x i ∈ F n i we define A(x 1 , . . . , x d ) = n 1 i 1 =1 • • • n d i d =1 A i 1 ,i 2 ,...,i d x 1i 1 • • • x di d . The vector v = A(•, x 2 , . . . , x d ) is n 1 -dimensional vector that its ith entry is n 2 i 2 =1 • • • n d i d =1 A i,i 2 ,...,i d x 2i 2 • • • x di d . For a set of d-dimensional matrices B, a set S ⊆ ({0, 1} n ) d is called a zero test set for B if for every A ∈ B, A = 0, there is x ∈ S such that A(x) = 0. A d-dimensional matrix is called symmetric if for every i = (i 1 , . . . , i d ) ∈ [n] d and

any permutation φ on [d], we have

A i = A φi , where φi = (i φ(1) , . . . , i φ(d) ). Notice that for a symmetric d-dimensional matrix A ∈ F × d n , x i ∈ {0, 1} n and any permutation φ on [d], we have A(x 1 , . . . , x d ) = A(x φ(1) , . . . , x φ(d) ).
We will be interested mainly in the fields F = R the field of real numbers and F = Z p the field of integers modulo p and in matrices of constant d = O(1) dimension. Also p > d!.

Although it seems that we are restricting the parameters, the final result has no restriction on the parameters except for d = O(1). We will also abuse the notations Z p and = p and allow p = ∞ (so in this paper ∞ is also prime number). In that case Z ∞ = R and = ∞ is equality in the filed of real numbers.

Hypergraph

A hypergraph G is a pair G = (V, E) where V = [n] is a set of elements, called nodes or vertices, and E is a set of non-empty subsets of 2 V called hyperedges or edges. The rank r(G) of a hypergraph G is the maximum cardinality of any of the edges in the hypergraph. A hypergraph is called d-uniform if all of its edges are of size d.

A weighted hypergraph G = (V, E, w) over Z p is a hypergraph (V, E) with a weight function w : E → Z p . For two weighted hypergraph

G 1 = (V, E 1 , w 1 ) and G 2 = (V, E 2 , w 2 ) we define the weighted hypergraph G 1 -G 2 = (V, E, w) where E = {e ∈ E 1 ∪ E 2 | w 1 (e) =
w 2 (e)}, and for every e ∈ E, w(e) = w 1 (e)w 2 (e). Obviously,

G 1 = G 2 if and only if G 1 -G 2 is an independent set, i.e., E = ∅.
We denote by G d the set of all weighted hypergraphs over Z p of rank at most d, G d,m the set of all weighted hypergraphs over Z p of rank at most d and at most m edges and G ⋆ d,m the set of all weighted hypergraphs over Z p of rank d and at most m edges. Let w ⋆ : 2 V → Z p be w extended to all possible edges where for e ∈ E, w ⋆ (e) = w(e) and for e ∈ E, w ⋆ (e) = 0.

An adjacency d-dimensional matrix of a weighted hypergraph G is a d-dimensional matrix A G d where d ≥ r(G) such that for every set e = {i 1 , i 2 , . . . , i ℓ } of size at most d we have A G d(j 1 ,...,j d ) = p w ⋆ (e)/N (d, ℓ) for all j 1 , . . . , j d such that {j 1 , j 2 , . . . , j d } = {i 1 , . . . , i ℓ } where

N (d, ℓ) = ℓ i=0 (-1) i ℓ i (ℓ -i) d .
That is, N (d, ℓ) is the number of possible sequences (j 1 , . . . , j d ) such that {j 1 , . . . , j d } = {i 1 , . . . , i ℓ }. Note that N (d, ℓ) ≤ d! < p and therefore N (d, ℓ) = p 0 and A G d is well defined. It is easy to see that the adjacency matrix of a weighted hypergraph is a symmetric matrix and r(G) = r if and only if the adjacency matrix of G has an non-zero entry of dimension r and all entries of dimension greater than r are zero.

Additive Model

In the Additive Model the goal is to exactly learn a hidden hypergraph with minimal number of additive queries. Given a set of vertices S ⊆ V , an additive query, Q G (S), returns the sum of weights in the subgraph induces by S. That is, Q G (S) = p e∈E∩2 S w(e). Our goal is to exactly reconstruct the set of edges and find their weights using additive queries. See the many applications of this problem in [START_REF] Bouvel | Combinatorial Search on Graphs Motivated by Bioinformatics Applications: A Brief Survey[END_REF][START_REF] Choi | Optimal Query Complexity Bounds for Finding Graphs[END_REF][START_REF] Choi | Almost Tight Upper Bound for Finding Fourier Coefficients of Bounded Pseudo-Boolean Functions[END_REF].

We say that the set

S = {S 1 , S 2 , • • • , S k } ⊆ 2 V is a detecting set for G d,m if for any hypergraph G ∈ G d,m there is S i such that Q G (S i ) = 0. We say that the set S = {S 1 , S 2 , • • • , S k } ⊆ 2 V is a search set for G d,m if for any two distinct hypergraphs G 1 , G 2 ∈ G d,m there is S i such that Q G 1 (S i ) = Q G 2 (S i ). That is, given (Q G (S i )) i one can uniquely determines G. We now prove the following, Lemma 2.1. If S = {S 1 , S 2 , • • • , S k } ⊆ 2 V is a detecting set for G d,2m then it is a search set for G d,m . Proof. Let G 1 , G 2 ∈ G d,m be two distinct weighted hypergraphs. Let G = G 1 -G 2 . Since G ∈ G d,2m there must be S i ∈ S such that Q G (S i ) = 0. Since Q G (S i ) = Q G 1 (S i ) -Q G 2 (S i ) we have Q G 1 (S i ) = Q G 2 (S i ).

Algebraic View of the Model

It is easy to show that for any hypergraph G of rank r the adjacency d-dimensional matrix of G, A G d , for d ≥ r, is symmetric, contains a nonzero entry of dimension r and ,x,d . . ., x) where x ∈ {0, 1} n . When x 1 , . . . , x d ∈ {0, 1} n are pairwise disjoint the following lemma shows that A(x 1 , . . . , x d ) can be found by 2 d values of B.

Q G (S) = p A G d (x S , x S , d . . ., x S ) ∆ = B G d (x S ). For a symmetric d-dimensional matrix A let B(x) = p A(x
Lemma 2.2. If x 1 , . . . , x d ∈ {0, 1} n are pairwise disjoint then A(x 1 , . . . , x d ) = p 1 d! I∈2 [d] (-1) d-|I| B i∈I x i . Proof. Since A(x 1 + x ′ 1 , x 2 , . . . , x d ) = p A(x 1 , x 2 , . . . , x d ) + A(x ′ 1 , x 2 , . . . , x d ) and A(x 1 , x 2 , . . . , x d ) = p A(x φ(1) , x φ(2) , . . . , x φ(d) )
for any permutation φ on [d], the result is analogous to the fact that

y 1 y 2 • • • y d = p 1 d! I∈2 [d] (-1) d-|I| i∈I y i d , (2.1)
for formal variables y 1 , . . . , y d . Now notice that

i∈I y i d = p q 1 +•••+q d =d χ [{i|q i = 0} ⊆ I] d q 1 q 2 • • • q d y q 1 1 • • • y q d d ,
where χ[L] = 1 if the statement L is true and 0 otherwise. Therefore, the coefficient of

y q 1 1 • • • y q d d
in the right hand side of (2.1) is

I∈2 [d] (-1) d-|I| χ [{i|q i = 0} ⊆ I] d q 1 q 2 • • • q d = p d q 1 q 2 • • • q d I∈2 [d] (-1) d-|I| χ [{i|q i = 0} ⊆ I] . Now if ℓ = |{i|q i = 0}| < d then I∈2 [d] (-1) d-|I| χ [{i|q i = 0} ⊆ I] = p d i=ℓ (-1) d-i d -ℓ i -ℓ = p d-ℓ i=0 (-1) d-ℓ-i d -ℓ i = 0. If ℓ = |{i|q i = 0}| = d then q 1 = q 2 = • • • = q d = 1 and
I∈2 [d] (-1) d-|I| χ [{i|q i = 0} ⊆ I] = p 1.
This implies the result.

Let G be a hypergraph of rank d and G (i) , i ≤ d, be the sub-hypergraph of G that contains all the edges in G of size i then Lemma 2.3. If x 1 , . . . , x d ∈ {0, 1} n are pairwise disjoint then, we have that

A G d (x 1 , . . . , x d ) = A G (d) d (x 1 , . . . , x d ). In particular, if r(G) < d then A G d (x 1 , . . . , x d ) = 0. Proof. Since x 1 , . . . , x d ∈ {0, 1} n are pairwise disjoint we have A G d (x 1 , . . . , x d ) = n 1 i 1 =1 • • • n d i d =1 w ⋆ ({i 1 , i 2 , . . . , i d }) N (d, |{i 1 , i 2 , . . . , i d }|) x 1i 1 • • • x di d = |{i 1 ,...,i d }|=d w ⋆ ({i 1 , i 2 , . . . , i d }) N (d, d) x 1i 1 • • • x di d = A G (d) d (x 1 , . . . , x d ).
Now when r(G) < d then G (d) is an independent set (has no edges) and

A G (d) d = 0. Then A G d (x) = A G (d) d (x) = 0.
We

S Φ d ∆ =    S y J y J = j∈J z (d) i,j , J ⊂ [d]    is a detecting set for G ⋆ d,m . Proof. Let Φ d be a zero test set for A ⋆ d,(d!)m . Let G ∈ G ⋆ d,m . Then A G d = 0 and A G d ∈ A ⋆ d,(d!)m . Therefore, for every G ∈ G ⋆ d,m there is z (d) i such that A G d (z (d) i ) = 0. By Lemma 2.2, A G d (z (d) i ) = p 1 d! J∈2 [d] (-1) d-|J| B G d   j∈J z (d) i,j   = 0,
and therefore for some

J 0 ⊂ [d], B G d   j∈J 0 z (d) i,j   = 0, which implies that Q G (S y J 0 ) = 0 for y J 0 = j∈J 0 z (d)
i,j . We now show Lemma 2.5. A detecting set for G d,m over Z p is a detecting set for G d,m over R.

Proof. Consider a detecting set

S = {S 1 , S 2 , • • • , S k } ⊆ 2 V for G d,m over Z p . Consider a k × q matrix M where q = d i=0 n i
that its columns are labelled with sets in 2 [n] of size at most d and for every S ⊂ [n] of size at most d we have M [i, S] = 1 if S ⊆ S i and 0 otherwise. Consider for every graph G ∈ G d,m a q-vector v G that its entries are labelled with subsets of [n] of size at most d and v G [S] = w ⋆ (S). The labels in v G are in the same order as the labels of the columns of M . Then it is easy to see that

M v G = p (Q G (S 1 ), . . . , Q G (S k )) T . Since M v G = p 0 for every v G ∈ Z q
p of weight at least one and at most m, every m columns in M are linearly independent over Z p . Since the entries of M are zeros and ones every m columns in M are linearly independent over R. Therefore,

M v G = (Q G (S 1 ), . . . , Q G (S k )) T = 0,
for every v G ∈ R q of weight at least 1 and at most m.

Reconstructing Hypergraphs

In this section we prove,

T (n, m, d) = O m log n log m , (3.1)
then

T ′ (n, 2m, d) = O(T (n, m, d))
. Therefore it is enough to prove the following.

Lemma 3.3. Let p be a prime number such that m < p < 2m. There exists a set

S = {x 1 , x 2 , . . . , x k } ⊆ ({0, 1} n ) d where x i = (x i,1 , . . . , x i,d ) ∈ Γ d,n for i ∈ [k] and k = O m log n log m , such that: for every d-dimensional matrix A ∈ Z × d n p \ {0 × d n } with 1 ≤ wt d (A) ≤ m there exists an i such that A(x i ) = p 0.
Proof. Since wt d (A) > 1 the matrix A has at least one nonzero entry of dimension d. We will assume that all the entries of dimension less than d are zero, that is, wt(A) = wt d (A). This is because, by Lemma 2.3, the entries of dimension less than d have no effect when the vectors x i ∈ Γ d,n .

We divide the set of such matrices non-zero elements in I j = {i j |∃(i 1 , i 2 , . . . , i j-1 , i j+1 , . . . , i d ) :

A = {A | A ∈ Z × d n p \ {0 × d n }
A i 1 ,i 2 ,...,i d = 0}. Note that I = {(i 1 , i 2 , . . . , i d )|A i 1 ,i 2 ,...,i d = 0} ⊆ I 1 × I 2 × • • • × I d and therefore either I = wt(A) ≤ m/ log m or there is j such that |I j | > (m/ log m) 1/d . Therefore, A = A 0 ∪ A 1 ∪ • • • ∪ A d .
Using the probabilistic method, we give d + 1 sets of pairwise disjoint tuples of vectors S 0 , S 1 , . . . , S d such that for every j ∈ {0} ∪ [d] and A ∈ A j there exists a d-tuple x in S j such that A(x) = 0 and

|S 0 | + |S 1 | + • • • + |S d | = O m log n log m .
Case 1: A ∈ A 0 : For a random d-tuple x, chosen according to the distribution Ω d,n we have that Pr

x [A(x) = p 0] ≤ 1 - 1 (d + 1) d .
If we randomly choose

k 1 =
cm log n log m d-tuples, x 1 , . . . , x k 1 , according to the distribution Ω d,n , then the probability that A(

x i ) = 0 for all i ∈ [k 1 ] is Pr[∀i ∈ [k 1 ] : A(x i ) = p 0] ≤ 1 - 1 (d + 1) d k 1 .
Therefore, by union bound, the probability that there exists a matrix A ∈ A 0 such that

A(x i ) = 0 for all i ∈ [k 1 ] is Pr[∃A ∈ A 0 , ∀i ∈ [k 1 ] : A(x i ) = p 0] ≤ n d m log m p m log m 1 - 1 (d + 1) d cm log n log m < n d m log m n m log m n -c ′ cm log m < 1,
for some constant c. This implies the result.

Case2: A ∈ A j where j = 1, . . . , d: We will assume w.l.o.g that j = 1. We first prove the following lemma

Lemma 3.4. Let U ⊆ Z × d-1 n p
be the set of all d -1-dimensional matrices with weight smaller than m d/(d+1) . For A ∈ U let Υ(A) ⊆ [n] be following set

Υ(A) = {j | ∃A i 1 ,i 2 ,...,i d-1 = 0 and j ∈ {i 1 , i 2 , . . . , i d-1 }}. Define Q = {(A, j) | A ∈ U and j ∈ Υ(A)}.
Then, there is a constant c 0 such that for every C > c 0 and

k 2 = C m log n log m there exists a multi-set of d -1-tuples of (0,1)-vectors Z = {z 1 , z 2 , . . . , z k 2 } ⊆ ({0, 1} n ) d-1 such that for every (A, j) ∈ Q the size of the set Z (A,j) = {i |A(z i ) = 0 and j is a free index} is at least k 2 2d d .
Proof. Let z i = (z i,1 , z i,2 , . . . , z i,d-1 ) ∈ ({0, 1} n ) d-1 be random d -1-tuple of (0, 1)-vector chosen according to the distribution Ω d-1,n . For (A, j) ∈ Q, and by Lemma 2.6, we have Pr

z i ∈Ω d-1,n [A(z i ) = 0 and j is a free] = Pr[j is free] Pr[A(z i ) = 0|j is free] ≥ 1 d • 1 d d-1 = 1 d d .
Therefore, the expected size of Z (A,j) is greater than k 2 d d . By Chernoff bound, if we randomly choose all z i , i ∈ [k 2 ] according to the distribution Ω d-1,n , then, we have

Pr |Z (A,j) | ≤ k 2 2d d ≤ e -k 2 8d d .
Thus, the probability that there exists (A, j)

∈ Q such that |Z (A,j) | ≤ k 2 2d d is Pr ∃(A, j) ∈ Q : |Z (A,j) | ≤ k 2 2d d ≤ |Q| e -k 2 8d d ≤ |U × [n]| e -k 2 8d d ≤ n n d-1 m d/(d+1) p m d/(d+1) e Cm log n 8d d log m ≤ n n d-1 m d/(d+1) n m d/(d+1) n C(log e)m 8d d log m ≤ n O(m d/(d+1) ) n Cc ′ m log m < 1,
for large enough C. This implies the result. Now, Let U and Q be the sets we defined in Lemma 3.4. Let A ∈ A 1 . Since wt(A) ≤ m there are at most m 1/(d+1) d -1-dimensional matrices (A i 1 ,i 2 ,...,i d ) i 1 =j,i 2 ,...,i d with weight greater than m d/(d+1) . Therefore, there is at least

q = m log m 1/d -m 1/(d+1)
indices j such that (A i 1 ,i 2 ,...,i d ) i 1 =j,i 2 ,...,i d ∈ U . Let U ′ contain any q indices such that (A i 1 ,i 2 ,...,i d ) i 1 =j,i 2 ,...,i d ∈ U . Let A U be the matrix (A i 1 ,i 2 ,...,i d ) i 1 ∈U ′ ,i 2 ,...,i d .

Let z 1 , z 2 , . . . , z k 2 ∈ ({0, 1} n ) d-1 be the set we proved its existence in Lemma 3.4. We now choose x i ∈ {0, 1} n , i ∈ [k 2 ] in the following way: Take z i . For every free index j, choose x ij to be "1" with probability 1/2 and "0" with probability 1/2 (independently for every j). All other entries in x i are zero, that is, all entries that correspond to non-free index j in z i are zero. Let u ∈ {0, 1} n be a vector where u j = 1 if j ∈ U ′ and zero otherwise. Also, for a d -1-tuple z i let v i ∈ {0, 1} n be the vector where v ij = 1 if j is a free index in z i and v ij = 0 otherwise. By Lemma 2.7 we have that Pr

x [A(x i , z i ) = p 0] ≤ i 1 ι(wt(v i * A(•, z i ))) β ≤ i 1 ι(wt(v i * (u * A(•, z i )))) β . (3.2)
Note that, A is a hypergraph, thus, for every j such that (A i 1 ,i 2 ,...,i d ) i 1 =j,i 2 ,...,i d ∈ U , we have that ((A i 1 ,i 2 ,...,i d ) i 1 =j,i 2 ,...,i d , j) ∈ Q. Therefore,

i )))) ≥ q ⌊ qk 2 2d d -k 2 q-1 ⌋ = m c 1 k 2 .
Therefore, using (3.2), Pr x [A(x i , z i ) = p 0] ≤ 1 m c 1 βk 2 . Thus, the probability that there exists a matrix A ∈ A 1 such that for all i ∈ [k 2 ] we have A(x i , z i ) = 0 is Pr

x [A(x i , z i ) = p 0] ≤ |A 1 | m c 1 βk 2 ≤ n d m p m m c 1 βk 2 ≤
n dm n m m c 1 βk 2 < 1, for large enough constant. This implies Lemma 3.3. This completes the proof of Theorem 3.1.

Theorem 3 . 1 ..Theorem 3 . 2 .

 3132 There is a search set for G d,m over R of size k = O m log n log m There is a search set for G ′ d,m over R of size k = O m log n d m log m , where G ′ d,m denotes the set of all weighted hypergraphs over R of rank at most d, at most m edges and weights that are integers bounded by w = poly(n d /m).Proof. We give the proof of Theorem 3.1. The proof of Theorem 3.2 is similar. More details in the full paper. Let m < p < 2m be a prime number. Suppose there is a zero test set from Γ d,n for A ⋆ d,m over Z p of size T (n, m, d). By Lemma 2.4, there is a detecting set for G ⋆ d,m over Z p of size 2 d T (n, (d!)m, d). Therefore, by Lemma 2.3, there is a detecting set for G d,m over Z p of size T ′ (n, m, d) = d ℓ=1 2 ℓ T (n, (ℓ!)m, ℓ). By Lemma 2.5, there is a detecting set for G d,m over R of size T ′ (n, m, d). Finally, by Lemma 2.1, there is a search set for G d,m over R of size T ′ (n, 2m, d). Now for constant d, if

  and wt(A) ≤ m} into d + 1 (non-disjoint) sets: • A 0 : The set of all non-zero matrices A ∈ Z × d n p such that wt(A) ≤ m/ log m. • A j for j = 1, . . . , d: The set of all non-zero matrices A ∈ Z × d n p such that m ≥ wt(A) > m/ log m and there are at least

i

  wt(v i * (u * A(•, z i ))) ≥ qk 2 2d d .Using Lemma 2.8 we have i ι(wt(v i * (u * A(•, z

  now prove Lemma 2.4. Let Φ d = {z ({0, 1} n ) d where for every i the vectors z

	(d) 1 , . . . , z k d } ⊂ (d) (d) i,1 , . . . , z i,d (d) are pairwise disjoint. If Φ d is a zero test set for A ⋆ d,(d!)m then

In[START_REF] Djackov | On a search model of false coins[END_REF] Djackov mentions this bound without a proof.

This work is licensed under the Creative Commons Attribution-NoDerivs License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nd/3.0/.

Distributions

In this subsection we give a distribution that will be used in this paper. The uniform disjoint distribution Ω d,n (x) over ({0, 1} n ) d is defined as

In order to choose a random vector x according to the uniform disjoint distribution, one can randomly independently uniformly choose n elements w 1 , w 2 , . . . , w n where w i ∈ [d + 1] and define the following vector x = (x 1 , x 2 , . . . , x d ) ∈ ({0, 1} n ) d :

be the set of all pairwise disjoint d-tuple.

Preliminary Results

In this section we prove,

Proof. Let e = {i 1 , . . . , i d } be an edge of size |e| = d and let x ′ j = (x j,i 1 , . . . , x j,i d ). Consider φ(x ′ 1 , . . . , x ′ d ) that is equal to A(x) with some fixed x j,i = ξ j,i ∈ {0, 1} for i ∈ e. Since A(x) contains the monomial M = x 1,i 1 x 2,i 2 • • • x d,i d and no other monomial in A(x) contains it, φ contains monomial M and therefore φ(x ′ 1 , . . . , x ′ d ) ≡ 0. If we substitute x j 1 ,i j 2 = 0 in φ for all j 1 = j 2 we still get a nonzero function φ

and x j 1 ,i j 2 = 0 for all j 1 = j 2 is (1/d + 1) d . This implies the result.

We will also use the following two lemmas from [START_REF] Bshouty | Reconstructing Weighted Graphs with Minimal Query Complexity[END_REF][START_REF] Bshouty | On Parity Check (0, 1)-Matrix over Zp[END_REF].

Lemma 2.7. Let a ∈ Z n p be a non-zero vector, where p > wt(a) is a prime number. Then for a uniformly randomly chosen vector x ∈ {0, 1} n we have

Let ι be a function on non-negative integers defined as follows: ι(0) = 1 and ι(i) = i for i > 0.

Lemma 2.8. Let m 1 , m 2 , . . . , m t be integers in [m]∪{0} such that m 1 +m 2 +• • •+m t = ℓ ≥ t. Then t i=0 ι(m i ) ≥ m ⌊(ℓ-t)/(m-1)⌋ .