Eric Duchêne

Valentin Gledel

Aline Parreau

Gabriel Renault

Maker-Breaker domination game

Keywords: positional games, Maker-Breaker domination game, domination game, complexity, tree, cograph, AMS Subj. Class: 05C57, 05C69, 91A43

We introduce the Maker-Breaker domination game, a two player game on a graph. At his turn, the rst player, Dominator, select a vertex in order to dominate the graph while the other player, Staller, forbids a vertex to Dominator in order to prevent him to reach his goal. Both players play alternately without missing their turn. This game is a particular instance of the so-called Maker-Breaker games, that is studied here in a combinatorial context. In this paper, we rst prove that deciding the winner of the Maker-Breaker domination game is P SP ACE-complete, even for bipartite graphs and split graphs. It is then showed that the problem is polynomial for cographs and trees. In particular, we dene a strategy for Dominator that is derived from a variation of the dominating set problem, called the pairing dominating set problem.

Introduction

Since their introduction by Erd®s and Selfridge in [START_REF] Erd®s | On a combinatorial game[END_REF], positional games have been widely studied in the literature (see [START_REF] Hefetz | Positional games[END_REF] for a recent survey book on the topic). These games are played on an hypergraph of vertex set X, with a nite set F ⊆ 2 X of hyperedges. The set X is often called the board of the game, and an element of F a winning set. The game involves two players that alternately occupy a previously unoccupied vertex of X. The winner is determined by a convention: in the Maker-Maker convention, the rst player to occupy all the vertices of a winning set is the winner. Such games may end in a draw, as it is the case in Tic-Tac-Toe. In the Maker-Breaker convention, the objectives are opposite: one player (the Maker) aims to occupy all the vertices of a winning set, whereas Breaker wins if he occupies a vertex in every winning set. In view of the complexity of solving both kinds of games, Maker-Breaker instances are generally more considered in the literature as by denition, there is always a winner. In addition, rulesets of such games are often built from a graph. For example, one can mention the famous Shannon switching game (popularized as the game Bridg-it) [START_REF] Lehman | A solution of the Shannon switching game[END_REF], where, given a graph G = (V, E) and two particular vertices u and v, the board X corresponds to E, and winning sets correspond to all the subsets of E corresponding to a u -v path in G. In the Hamiltonicity game [START_REF] Chvátal | Biased positional games[END_REF], the winning sets correspond to all the sets of edges containing an Hamiltonian cycle.

In view of such examples, converting a graph property into a 2-player game is a natural operation. Hence it is not surprising that it has also been done for dominating sets. More precisely, several games having dierent rulesets and known as domination game have been dened in the literature. For example, in [START_REF] Alon | Game domination number[END_REF][START_REF] Favaron | Proof of a conjecture on game domination[END_REF], a move consists in orienting an edge of a given graph G and the two players try to maximize (resp. minimize) the domination number of the resulting digraph. In [START_REF] Bujtás | The Disjoint Domination Game[END_REF], the rules require two colors during the play. In [START_REF] Bresar | Domination game and an imagination strategy[END_REF], the domination game is dened in a sense where the players both select vertices and try to maximize (resp. minimize) the length of the play before building a dominating set. Since then, this version has become the standard one for the domination game, with regular progress on it [START_REF] Bresar | Domination game played on trees and spanning subgraphs[END_REF][START_REF] Dorbec | The domination game played on unions of graphs[END_REF][START_REF] Kosmrlj | Domination game on paths and cycles[END_REF][START_REF] Kinnersley | Extremal problems for game domination number[END_REF]. However, among the dierent variants of the domination game , the natural Maker-Breaker version (in the sense of Erd®s and Selfridge) has never been considered in the literature. In this paper, we consider the so-called Maker Breaker Domination game, where, given a graph G = (V, E), the board X is the set V , and F is the set of all the dominating sets of G. In other words, the two players alternately occupy a not yet occupied vertex of G. Maker wins if he manages to build a dominating set of G, whereas Breaker wins if she manages to occupy a vertex and all its neighbors. In what follows and in order to be consistent with the standard domination game, Maker will be called Dominator, and Breaker will be the Staller.

When dealing with Maker-Breaker games, there are two main questions that naturally arise:

• Given a graph G, which player has a winning strategy for the Maker-Breaker domination game on G ?

• If Dominator has a winning strategy on G, what is the minimum number of turns needed to win?

The current paper is about the rst question. In the next section, we give denitions for the dierent cases about the winner, together with rst general results. Section 3 deals with the algorithmic complexity of the problem, where the P SP ACE-completeness is proved. In Section 4, a so-called pairing strategy is given, yielding a strategy for Dominator in graphs having certain properties. The last section is about graph operators that lead to polynomial strategies on trees and cographs.

Preliminaries

A position of the Maker-Breaker domination game is denoted by a triplet G = (V, E, c), where V is a set of vertices, E is a set of edges on V and c is a function c : V → {Dominator, Staller, U nplayed}. In other words, the function c allows to describe any game position encountered during the play.

If, for all u in V , c(u) = U nplayed, then G is said to be a starting position.

In this case, we will identify G with the graph (V, E).

As by denition, Maker-Breaker games have no draw, there are four cases -also called outcomes -to characterize the winner of the game, according to who starts. We dene D, S, N and P as the dierent possible outcomes for a position of the Maker-Breaker domination game. Denition 1. A position G has four possible outcomes:

• D if Dominator has a winning strategy as rst and second player,

• S is Staller has a winning strategy as rst and second player,

• N if the next player (i.e., the one who starts) has a winning strategy,

• P otherwise (i.e., the second player wins).

Note that for proximity reasons, the notion of outcome and the last two notations are derived from combinatorial game theory [START_REF] Siegel | Combinatorial Game Theory[END_REF]. In addition, the outcome of G is denoted o(G).

If Staller has a winning strategy, then she manages to occupy the closed neighborhood of a certain vertex u. In this case, we say that she isolates u.

The following proposition is a direct application of a general result on Maker-Breaker games stated in [START_REF] Hefetz | Positional games[END_REF][START_REF] Beck | Combinatorial games: tic-tac-toe theory[END_REF]. It ensures that the outcome P never occurs. For the sake of completeness, we here give a proof of this result adapted to our particular case.

Proposition 2 (Imagination strategy).

There is no position G of the Maker-Breaker domination game such that o(G) = P.

Proof. Assume Dominator wins playing second on G. When he is the rst player, he plays any vertex and then imagines he did not. He thus considers himself as the second player, seeing this vertex as an extra vertex. Whenever his winning strategy (as a second player) requires to play the extra vertex, he plays any other unoccupied vertex u, and considers u as the new extra vertex. If Dominator was winning before all the vertices were chosen, he still wins no later than his last move in the game where he was playing second. Otherwise, when Staller chooses the last vertex of the graph, her strategy asks her to play the extra vertex since it is the only one available in the imagined game, but it means that Dominator had already won on the previous turn.

Hence if Dominator wins as second player he also wins as rst player and the outcome of the game is D. If he does not win as second player, then the outcome can be either S or N .

In other words, this proof ensures that a player has no interest to miss his/her turn. Figure 1 gives an example of graphs for the three remaining outcomes.

According to the three possible outcomes of a position, we now introduce an order relation on the outcomes derived from combinatorial game theory: S ≺ N ≺ D. This allows us to state the following proposition. Proof. A reformulation of the proposition is that if Dominator has a winning strategy on H as rst or second player, then he also have a winning strategy on G.

Assume Dominator has a winning strategy on H. A winning strategy for Dominator on G is to apply the same strategy as on H. Indeed, for every possible sequence of moves of Staller, Dominator is able to dominate H. Since every edge of H is also in G, Dominator is also able to dominate G.

In other words, this result says that adding edges to a position can only benet Dominator , and removing edges can only benet Staller. Note that this property does not hold in the standard domination game.

Another result can be derived from Maker-Breaker games. The following theorem is a well known result from the early studies about positional games.

Theorem 4 (Erd®s-Selfridge Criterion [START_REF] Erd®s | On a combinatorial game[END_REF]). Given a Maker-Breaker game G on an hypergraph (X, F), we have

A∈F 2 -|A| < 1 2
⇒ G is a Breaker's win .

In order to apply this theorem to the Maker-Breaker domination game, we need to consider a reverse version of it. Indeed, as the set F corresponds to the dominating sets of G, the sizes of the winning sets are not easy to control. Thus, we can also consider the Maker-Breaker domination game as the Maker-Breaker game where F is the set of the closed neighborhoods of every vertex of G. In that case, Dominator is the Breaker, and Staller is the Maker. Nom Theorem 4 can be applied on this game: Proposition 5. Let G be a starting position of the Maker-Breaker domination game and let δ be the minimum degree of G. If |V | < 2 δ then Dominator has a winning strategy for the Maker-Breaker domination game on G.

Proof. As stated before, the Maker-Breaker domination game on G is a Maker-Breaker game played on H = (V, F) where F is the set of the closed neighborhoods of G, and Staller plays the role of Maker in this game. Applying the Erd®s-Selfridge Criterion, we know that if u∈V 2

-|N [u]| < 1 2
then Dominator has a winning strategy. For all u in V , we have

N [u] ≥ δ +1, hence 2 -|N [u]| ≤ 2 -(δ+1) . Thus if |V | × 2 -(δ+1) < 1
2 then Dominator has a winning strategy.

Although this result can only be applied for very particular graphs (hypercubes with at least an additional edge for example), it suggests that highly connected graphs are more advantageous for Dominator.

Complexity

In this section, we consider the computational complexity of deciding whether a game position of the Maker-Breaker domination game is S, N , or D. First remark that in the general case, deciding the outcome of a Maker-Breaker game (X, F) is P SP ACE-complete. Indeed, this game exactly corresponds to the game POS CNF that was proved to be P SP ACE-complete in [START_REF] Schaefer | On the Complexity of Some Two-Person Perfect-Information Games[END_REF].

POS CNF is played on a formula F in conjunctive normal form, with variables

x 1 • • • x n , where each variable is positive, that is F = C 1 ∧ • • • ∧ C m with C i = x i 1 ∨ • • • ∨ x i k i .
Two players, Prover and Disprover, alternate turns in choosing a variable that has not been chosen yet. When all variables have been chosen, variables chosen by Prover are set to true, while variables chosen by Disprover are set to false. Prover wins if F is true under this valuation and Disprover wins otherwise. Without loss of generality, we can consider that each variable appears in the formula, otherwise we consider the formula

F = F ∧ (x 1 ∨ • • • ∨ x n ).
Clearly, any Maker-Breaker game (X, F) is equivalent to a POS CNF game, as X corresponds to the set of variables, and the winning sets correspond to the clauses. Prover has the same role as Breaker, and Maker the role of Disprover.

The next result shows that the complexity of this game remains P SP ACEcomplete when reduced to instances of the domination game. Theorem 6. Deciding the outcome of a Maker-Breaker domination game position is P SP ACE-complete on bipartite graphs.

Proof. We reduce the problem from POS CNF. Let 2 shows an example of such a construction, from the example where

F = C 1 ∧ • • • ∧ C m be a positive formula in conjunctive normal form using n variables X 1 • • • X n . We build a bipartite graph G = (V, E) from F as follows: V = {x i |1 ≤ i ≤ n} ∪ {c k j |1 ≤ j ≤ m, 0 ≤ k ≤ 1}, E = {(x i , c k j )|1 ≤ i ≤ n, 1 ≤ j ≤ m, 0 ≤ k ≤ 1, X i ∈ C j }. Figure
F = (X 1 ∨ X 2 ) ∧ (X 1 ∨ X n ) ∧ . . . ∧ (X 2 ∨ X 3 ∨ X n ).
We now show that Prover has a winning strategy in F if and only if Dominator has a winning strategy in G.

Assume rst Prover has a winning strategy in F . Dominator builds his strategy in G as follows: Whenever Prover's strategy requires to choose a variable X i , Dominator chooses the vertex x i . Whenever Staller chooses a vertex c k j , Dominator answers by choosing the vertex c 1-k j . Whenever Staller chooses a vertex x i , Dominator assumes Disprover chose the variable X i . When all vertices are chosen, since Prover was winning in F , for each vertex c k j , there is a neighbor x i that was chosen by Dominator. As all variables are in a clause, and for each j, Dominator chose either c 0 j or c 1 j , all vertices of the form x i are also dominated by Dominator's choice of vertices. Hence Dominator wins the game.

Assume now Disprover has a winning strategy in F . Staller builds his strategy in G as follows: Whenever Disprover's strategy requires to choose a variable X i , Staller chooses the vertex x i . Whenever Dominator chooses a vertex c k j , Staller answers by choosing the vertex c 1-k j . Whenever Dominator chooses a vertex x i , Staller assumes Prover chose the variable X i . When all vertices are chosen, since Disprover was winning in F , there exists a couple of vertices (c 0 j , c 1 j ) such that none of their neighbours was chosen by Dominator. As Staller managed to choose one among these two, this particular one is not dominated by Dominator's choice of vertices. Hence Staller wins the game. Corollary 7. Deciding the outcome of a Maker-Breaker domination game position is P SP ACE-complete on chordal graphs, and also in particular on split graphs.

x 1 x 2 x 3 x n • • • c 0 1 c 1 1 c 0 2 c 1 2 c 0 m c 1 m • • • Figure 2: Reduction from POS CNF on (X 1 ∨ X 2 ) ∧ (X 1 ∨ X n ) ∧ . . . ∧ (X 2 ∨ X 3 ∨ X n ).
Proof. This proof of Theorem 6 remains valid by adding edges between the vertices x i . In particular, it works if they form a clique, so that the resulting graph is a split graph, that is special case of chordal graphs.

In view of these complexity results, the question of the threshold between P SP ACE-completeness and polynomiality is of natural interest. The following section is a rst step towards it, with a characterization of a certain structure in the graph that induces a natural winning strategy for Dominator . [START_REF] Bresar | Domination game played on trees and spanning subgraphs[END_REF] Pairing strategy A natural winning strategy for Breaker in a Maker-Breaker game is the socalled pairing strategy as dened in [START_REF] Hefetz | Positional games[END_REF]. This strategy can be applied when a subset of the board X can be partitioned into pairs such that each winning set contains one of the pairs. In that case, a strategy for Breaker as a second player consists in occupying the other element of the pair that has been just occupied by Maker. By doing so, Breaker will occupy at least one element in each winning set and thus win the game. In the context of the Maker-Breaker domination game , such a subset can be described as follows:

Denition 8. Given a graph G = (V, E), a subset {(u 1 , v 1 ), . . . , (u k , v k )} of V is a pairing dominating set if by choosing any vertex in (u i , v i ) for each 1 ≤ i ≤ k, the resulting set (of size k) is a dominating set of G.
Figure 3 shows an example of a pairing dominating set.

u 1 v 1 u 2 v 2 u 3 v 3 Figure 3: The set {(u 1 , v 1 ), (u 2 , v 2 ), (u 3 , v 3 )} is a pairing dominating set.
Another way to consider a pairing dominating set is from the union of the closed neighborhoods of each pair:

Proposition 9. Given a graph G = (V, E), a set D = {(u 1 , v 1 ), . . . , (u k , v k )} is a pairing dominating set of G if and only if it satises V = k i=1 N [u i ] ∩ N [v i ] . Proof. Let S = k i=1 N [u i ] ∩ N [v i ]. If S = V ,
then by denition of S, choosing any element in (u i , v i ) for all i builds a dominating set of G. On the contrary, if S = V , then there exists a vertex w ∈ V \ S such that for all i, w is not a neighbor of either u i or v i . By choosing these non-adjacent vertices to w, they do not form a dominating set of G as w is not dominated.

From this property, we will say that a vertex w is pairing dominated if there exists a pair (u, v) from a pairing dominated set such that w Proof. If G admits a pairing dominating set, then Dominator applies the following strategy as a second player: each time Staller occupies a vertex of a pair (u i , v i ) for some i, Dominator answers by occupying the other vertex of the same pair if it is not yet occupied. Otherwise, Dominator plays randomly.

∈ N [u] ∩ N [v]. In addition, all the pairs (u, v) satisfying N [u] ∩ N [v] = ∅
By denition of a pairing dominating set, it ensures that the vertices chosen by Dominator form a dominating set of G.

This result induces the following corollary that ensures a winning strategy for Dominator as a rst player.

Corollary 11. Given a graph G, if there exists a vertex u of G such that

G \ N [u] admits a pairing dominating set, then N o(G).
Proof. If such a vertex exists, then Dominator starts and occupy it. He then applies his pairing strategy on G \ N [u] as a second player to dominate the rest of the graph.

From this property, a natural question that arises is the detection of graphs having a pairing dominating set. An example of such graphs is when the vertices of the graph can be partitioned into cliques of size at least 2.

In that case, a trivial pairing dominating set consists in choosing any two vertices in each clique. Note that the question of the existence of such a partition is often referred to as the packing by cliques problem (with cliques of size at least 2). It was proved to be polynomial by Hell and Kirkpatrick in [START_REF] Hell | Packings by cliques and by nite families of graphs[END_REF]. A particular case of this decomposition is when the graph admits a perfect matching. As an example, Proposition 10 ensures that paths or cycles of even size are D as they have a perfect matching.

Remark 12. The condition of Proposition 10 is not necessary. Indeed, the graphs of Figure 4 are examples with outcome D and it can be shown that they do not admit a pairing dominating set. Yet, we will see in Section 5 two families of graphs (cographs and trees) for which there is an equivalence between the existence of a winning strategy for Dominator and the existence of a pairing dominating set. We conclude this section with a study of the complexity of the pairing dominating set problem.

Theorem 13. Given a graph G, it is N P -complete to decide whether G admits a pairing dominating set.

Proof. Let G = (V, E) be a graph. According to Proposition 9, the problem is clearly in N P . It remains to prove the N P -hardness of the problem by reducing it from 3-sat. Let F = C 1 ∨ • • • ∨ C m be an instance of 3-sat over the variables X 1 , . . . , X n . Without loss of generality, one can assume that all the variables appear in both their positive and negative version in F , but not in the same clause. From F , we build the following graph G as illustrated by Figure 5.

• For 1 ≤ j ≤ m, to each clause C j we associate a vertex c j .

• Each variable X i , 1 ≤ i ≤ n is associated to a gadget over seven vertices {x i , y i , z i , x i , y i , z i , t i } such that x i y i z i and x i y i z i are two triangles, and t i is adjacent to both x i and x i . The pairs (x i , y i ) and (x i , y i ) will be denoted e i and e i respectively.

• For each variable X i , we add the two edges c j x i and c j y i (resp. c j x i and c j y i ) each time X i appears in clause C j in its positive (resp. negative) form.

x i y i z i t i x i y i z i • • • c j 1 c j 2 c j k e i e i
Figure 5: Gadget around a variable X i for the proof of N P -completeness.

The clauses C j 1 , . . . , C j k are those where the variable X i appears.

We rst claim that any assignment of the variables X 1 , . . . , X n that makes F satisable induces a pairing dominating set in G. Let σ be such an assignment. Now build the following set D of pairs of vertices: for each variable X i , we add the pairs {(x i , y i ), (t i , x i ), (y i , z i)} to D if X i is true in σ , and the pairs {(x i , y i ), (t i , x i ), (y i , z i )} otherwise. It now suces to check that D is a pairing dominating set. First of all, one can easily remark that all the vertices of the gadgets (i.e., vertices dierent from the clauses c j ) are pairing dominated by D. In addition, as each clause C j is satised by σ, each vertex c j is adjacent to at least one pair (x i , y i ) or (x i , y i ) of D. Hence any choice of vertex in such a pair allows to dominate c j . Now consider a pairing dominating set D of G. We rst show that for each gadget associated a variable X i , up to symmetry, there are only four cases to dominate the vertices t i , z i and z i , depicted by Figure 6. Indeed, for each vertex t i , as it is of degree 2, there are three cases for it to be pairing dominated by D: either the pair (t i , x i ), or (t i , x i ), or (x i , x i ) belongs to D. (i) the pair (t i , x i ) belongs to D (cases (a), (b) and (c) of Figure 6). Then, by considering the vertex z i , the pair (y i , z i ) must belong to D. Indeed, if z i is not in a pair of D, then one can always nd vertices from D dierent from x i and y i such that z i is not dominated. The same argument holds if z i is in D, but not in a pair with y i . Concerning the vertex z i , it is necessarily dominated by vertices from the triangle x i y i z i , leading to the three cases (a), (b) and (c) of Figure 6. (ii) the pair (t i , x i ) belongs to D. By symmetry of the gadget, this case is similar to the previous one and we get the symmetric pairs from gures (a), (b) and (c). (iii) the pair (x i , x i ) belongs to D (Figure 6 (d)). Then both vertices z i and z i must belong to D in the pairs (y i , z i ) and (y i , z i ). Indeed, if z i (or, by symmetry z i ) is not in D, then one can always choose vertices from D dierent from x i and y i such that z i is not dominated. The same argument holds if z i is in D, but not in a pair with y i .

In order to nd an assignment for F , we now show that D can be transformed into a pairing dominating set where each pair is as in Figure 6 (a) (or its symmetrical, according to case (ii)). Consider rst that for the gadget associated to some variable X i , the pairs of D are those depicted by Figure 6 (b). As the vertex z i has no other neighbor than x i and y i , replacing a pair (x i , z i ) by the pair (x i , y i ) in D remains a valid pairing dominating set since both x i and y i are adjacent to z i . This operation is clearly possible if y i is not in D. In the case where y i is already in D, say in a pair (y i , u), remark that removing this pair from D does not break the pairing dominating property of D if (x i , y i ) is added. Indeed, as by denition of G, x i and y i have the same neighborhood (except t i , that is already in a pair), we have that

N [u] ∩ N [y i ] ⊆ N [x i ] ∩ N [y i ]
. Since x i and y i play a symmetrical role, we can use the same argument to replace the pairs of Figure 6 (c) by those of (a) in D. The last case is when the pairs of D are those of Figure 6 (d) for the variable

X i . Since N [y i ] ∩ N [z i ] ⊆ N [y i ] ∩ N [x i ] and N [x i ] ∩ N [x i ] = {t i } ⊂ N [t i ] ∩ N [x i
] (as X i and X i cannot be in the same clause), we can replace the pairs of Figure 6 (d) by those of Figure 6 (a) without breaking the pairing dominating property of D. In case t i was already in D, say in a pair (t i , u), once again this pair can be removed from D as N [t i ] ∩ N [u] is either empty or at most a subset of {x i , x i }, which is already pairing dominated by the pairs of Figure 6 (a).

Hence we have transformed D such that all the vertices dierent from the c j are pairing dominated by the pairs of vertices of Figure 6 (a). In addition, if D admits other pairs than those depicted by Figure 6 (a), then these pairs are necessarily of the form (c j , c l ), (z i , u), or (z i , u). The last two types of pairs can be removed from D as N [z i ] and N [z i ] is already pairing dominated. Concerning the pairs (c j , c l ), they can also be removed from D as the sets N [c j ] ∩ N [c l ] belong to the gadgets (and are dierent from the clause vertices), and are thus already pairing dominated.

We now build the following assignment of the variables of F : for all 1 ≤ i ≤ n, the variable X i is set to true if and only if the pair e i belongs to D. As each vertex c j is pairing dominated in D by at least a pair e i or e i for some i, it means that each corresponding clause C j has at least a variable equal to true, which concludes the proof.

Graph operations

In the rst part of this section, we study the outcome of operations of graphs for which the outcome is already known. This will lead to polynomial time algorithms to solve the Maker-Breaker domination game on cographs and forests, as these families can be built from joins, unions and by adjoining hanging edges.

V G ∪ V H and edge set E G ∪ E H ∪ {uv|u ∈ V G , v ∈ V H }.
Theorem 14. Let G and H be two starting positions of the Maker-Breaker domination game.

• If o(G) = S or o(H) = S then o(G ∪ H) = S. • If o(G) = o(H) = N then o(G ∪ H) = S. • If o(G) = o(H) = D then o(G ∪ H) = D. • Otherwise, o(G ∪ H) = N .
This result is summarized in Table 1. Note that the outcome S is absorbing for the union, while the outcome D is neutral. Finally, assume without loss of generality that o(G) = N and o(H) = D. If Staller plays rst, as in the rst case, by applying her winning strategy as the rst player in G she will be able to isolate a vertex and to win. On the other hand, if Dominator plays rst, he can play his winning move on G and then answers to Staller on the component she has played on with his winning strategy. So the rst player has a winning strategy and the outcome is N . (ii) Since we are not in the rst case, there are two possibilities : Either both G and H have at least two vertices or, without loss of generality, G = K 1 and o(H) N .

Assume rst that both G and H have more than two vertices. Let u 1 , v 1 be two vertices of G and u 2 , v 2 two vertices of H. Since every vertex of G is a neighbor of every vertex of H and conversely, {(u 1 , v 1 ), (u 2 , v 2 )} forms a pairing dominating set for G H and the outcome is D according to Proposition 10.

Assume now that G = K 1 and o(H) N . Note that Dominator has a winning strategy on H as rst player. Assume that Staller is the rst player. If on her rst move she does not play on the vertex of G, then Dominator wins immediately by playing on it. If she does play on it, then Dominator will apply his winning strategy as rst player on H. This will allow him to dominate H and, since each vertex of H dominates G, all the vertices of G H will be dominated. Dominator has a winning strategy as second player, hence o(G H) = D.

The combination of these two results gives a complexity result on the class of cographs. Recall that cographs (or P 4 -free graphs) can be inductively built from a single vertex by taking the union of two cographs or the join of two cographs. In addition, from a given cograph, recovering this construction from unions and joins can be found with a linear time algorithm [START_REF] Corneil | A linear recognition algorithm for cographs[END_REF]. Since we know the outcome of Maker-Breaker domination game for K 1 and for the union and the join operators, we can deduce the following corollary.

Corollary 16. Deciding the outcome of the Maker-Breaker domination game on cographs can be done in polynomial time.

As stated in Remark 12, for some families of graphs the outcome of a starting position is D if and only if it admits a pairing dominating set. We show that the family of cographs satises this property. Proof. We know from Proposition 10 that if a graph admits a pairing dominating set, then it has outcome D. It remains to prove that all cographs with outcome D admits a pairing dominating set.

The proof is done by induction on the number n of vertices of G.

First note that the result is true when n ≤ 2. The only such cographs are K 1 , K 2 and K 1 ∪ K 1 , and among them the only graph with outcome D is K 2 . K 2 admits a perfect matching and thus a pairing dominating set.

Assume now that every cograph of outcome D with a number of vertices less or equal to n admits a pairing dominating set. Let G be a cograph of outcome D with n + 1 vertices. By denition of a cograph, G is either the union or the join of two smaller cographs.

If G is the union of two cographs G 1 and G 2 , they necessarily have outcome D by Theorem 14. By induction hypothesis, they both admit a pairing dominating set, which union also is a pairing dominating set for G.

Assume now that G is the join of two cographs G 1 and G 2 .

If both G 1 and G 2 have more than two vertices, then if u 1 , v 1 are any two vertices of G 1 and u 2 , v 2 are any two vertices of G 2 , {(u 1 , v 1 ), (u 2 , v 2 )} forms a pairing dominating set for G. Indeed, both u 1 and v 1 are neighbors of every vertices of G 2 and both u 2 and v 2 are neighbors of every vertices of G 1 .

Assume now that G 1 = K 1 and let x be its unique vertex. Then G 2 has either outcome N or D by Theorem 15. If G 2 has outcome D then by induction hypothesis, it admits a pairing dominating set. Every vertex of this pairing dominating set is a neighbor of x and it remains also a pairing dominating set for G.

Assume now that o(G 2 ) = N . G 2 is either the union of two cographs or the join of two cographs.

If G 2 is the join of two cographs, by Theorem 15, it must be the join of a graph K 1 with vertex y and of a graph H with outcome S. Notice that x and y are both universal vertices so {(x, y)} is a pairing dominating set for G. If G 2 is the union of H 1 and H 2 then, without loss of generality, by Theorem 14 o(H 1 ) = D and o(H 2 ) = N . By induction hypothesis, H 1 admits a pairing dominating set S 1 . Note also that by Theorem 15, x H 2 has outcome D, so by induction hypothesis it admits a pairing dominating set S 2 . Since S 1 dominates H 1 and S 2 dominates {x}∪H 2 , S 1 ∪S 2 forms a pairing dominating set for G.

Glue operator and trees

We now study the operator consisting of gluing two graphs on a vertex. This operator will be useful in the study of trees. A more formal denition is the following: Denition 18. Let G = (V G , E G ) and H = (V H , E H ) be two graphs and let u ∈ V G and v ∈ V H be two vertices. The glued graph of G and H at u and v This proves that the conditions are necessary for (H, v) to be neutral. We now prove that they are sucient.

is the graph G u v H with vertex set (V G \ {u}) ∪ (V H \ {v}) ∪ {w} (
Let H be a graph, v be a vertex of H and H = H \ {v}, such that o(H) = N and o(H ) = D. Let G be a graph and u a vertex of G. In the following, we identify the vertices u and v to w and the glued graph of G and H will be denoted by G H.

Since

o(H ) = D, o(G ∪ H ) = o(G)
(G u v H) o(G), this prove that o(G u v H) = o(G).
A question that could be asked is whether or not neutral graphs exist. We solve it by exhibiting an innite family of neutral graphs: Denition 20. For n ≥ 2, the hanging split graph of size n, H n , is the graph composed of a clique of size n with vertex set {u, u 1 , . . . , u n-1 } and an independent of size n -1 with vertex set {v 1 , . . . , v n-1 }. Add an edge u i v i for all 1 ≤ i ≤ n -1. If Dominator plays rst on H n , a winning strategy is to start on u, then the remaining graph has a perfect matching and he will win.

If Staller plays rst on H n , a winning strategy is to play on each u i . Dominator has to answer on v i otherwise Staller wins immediately by isolating this vertex. When every u i is played, she can play on u and isolate it.

So both players have a winning strategy when playing rst and thus o(H n ) = N . By Theorem 19, (H n , u) is neutral.

An interest of the neutral graphs is that if a graph G is of the form G v H with (H, v) being neutral, then we can restrict the study of G to the study of G . In the following, we apply this idea to trees by noticing that P 3 is isomorphic to H 2 and thus neutral.

We dene a P 2 -irreducible graph as a graph without pendant P 2 , where a pendant P 2 is a P 2 attached to a graph by an edge. Lemma 22. Every P 2 -irreducible tree has one of the following form :

u u K n u H 2 H 3 H n
• K 1 • P 2 • K 1,n with n ≥ 3
• Trees where there are at least two vertices with more than two leaves as children.

Figure 9 shows a representation of these dierent cases. Proof. Let T be a P 2 -irreducible graph. If T has only one vertex, T = K 1 .

T K 1 K 2 K 1,n
Otherwise T must have leaves. If a leaf is connected to a vertex of degree 2, then there is a pendant P 2 and T is not irreducible. If there is a leaf connected to a vertex of degree 1, then the only possible case is that T = K 2 . If we are in none of the previous cases, each leaf parent is connected to at least two leaves. If there is only one leaf parent, then T = K 1,n with n ≥ 3 and otherwise there are at least two leaf parents connected to at least two leaves.

Theorem 23. Deciding the outcome of the Maker-Breaker domination game on trees is polynomial.

Proof. The following algorithm solves the Maker-Breaker domination game on trees in polynomial time: For a tree T , iteratively remove a pendant P 2 until it is not possible anymore. Let T be the obtained tree. If T = P 2 , return the answer D. If T = K 1 or K 1,n with n ≥ 3, then return N . Otherwise, return S.

Note that the above algorithm is polynomial. Indeed, removing pendant P 2 's can be done in polynomial time by keeping in memory the set of leaves at each time and updating it when necessary. Verifying that a tree is K 1 , P 2 or a star can also be done in polynomial time.

We now prove the correctness of the algorithm. Let T 1 , . . . , T k be the intermediary trees obtained after removing a pendant P 2 . From Proposition 21, we know that P 3 is neutral and a pendant P 2 can be seen as the glue with a P 3 . So o(T ) = o(T 1 ) = . . . = o(T k ) = o(T ), and the outcome of T is the same as the outcome of T . As T is P 2 -irreducible so it corresponds to one of the situations described in Lemma 22. If it is a P 2 , the outcome is D. If it is K 1 or K 1,n with n ≥ 3, the rst player wins by playing on the central vertex and thus the outcome is N . In the last case, two distinct vertices are attached to two leaves or more. Assume that Staller plays second on T . After Dominator's rst move, one of these two vertices and its leaves are unplayed by Dominator. Staller can play this vertex and will isolate one of its leaves after her next move. Hence T is indeed S in this last case.

We conclude that the outcome of T is the same as the outcome of T and the algorithm correctly returns the right output.

Remark 24. Note that a tree has outcome D only if by removing pendant P 2 's the remaining graph is a P 2 . This means that a tree has outcome D if and only if it admits a perfect matching and thus if and only if there is a pairing dominating set.

Conclusion and perspectives

In this paper, the complexity of the Maker-Breaker domination game is studied for dierent classes of graphs. P SP ACE-completeness is proved for split and bipartite graphs, whereas polynomial algorithms are given for cographs and trees. An interesting equivalence property is that in these last two cases, the outcome is D if and only if the graph admits a pairing dominating set. The study of the pairing dominating set problem might be a key in the study of the threshold between P SP ACE and P for the Maker-Breaker domination game.

As stated in the introduction, another problem that might be relevant to consider is the number of moves needed by Dominator to win. In particular, it could be worth studying the correlation of this value with the dominating number or the game dominating number.

Also, this game has been built from the dominating set problem. Other remarkable structures in graphs could have been chosen, such as total dominating sets. Another variant would be to consider the game in an oriented version.

Figure 1 :

 1 Figure 1: Example of a graph for each possible outcome.

  are useless in the construction of a pairing dominating set. Hence the pairing strategy applied to the Maker-Breaker domination game can be translated into a strategy on a pairing dominating set: Proposition 10. If a graph G admits a pairing dominating set, then o(G) = D.

Figure 4 :

 4 Figure 4: Graphs with outcome D and without a pairing dominating set.

Figure 6 :

 6 Figure 6: Possible pair dominating sets for the gadget of the proof of Theorem 13 (up to symmetry).

5 . 1

 51 Union and join Let G = (V G , E G ) and H = (V H , E H ) be two graphs on disjoint sets of vertices. The union G ∪ H of G and H is the graph with vertex set V G ∪ V H and edge set E G ∪ E H . The join G H of G and H is the graph with vertex set

  Proof. Assume Staller has a winning strategy on G or H. Then she has a winning strategy on G ∪ H. Indeed, without loss of generality assume that o

Theorem 15 .

 15 Let G and H be two starting positions of the Maker-Breaker domination game.(i) If G = K 1 and o(H) = S (or H = K 1 and o(G) = S) then o(G H) = N . (ii) Otherwise, o(G H) = D.Proof. (i) Assume that G = K 1 and o(H) = S. If Dominator starts, he will win by playing on the only vertex of G and dominates the join, so he has a winning strategy as a rst player. However, since o(H) = S, if Staller starts, she can play on the only vertex of G and then apply her winning strategy as second player on H. So she wins on G H as rst player as well as Dominator. So o(G H) = N .

Theorem 17 .

 17 A cograph G has outcome D if and only if it admits a pairing dominating set.

Figure 8

 8 Figure 8 gives a representation of the rst two hanging split graphs and of the general case. Proposition 21. For all n ≥ 2, (H n , u) is neutral for the glue operator. Proof. Note that H n \ {u} has a perfect matching so it has outcome D by Proposition 10.If Dominator plays rst on H n , a winning strategy is to start on u, then the remaining graph has a perfect matching and he will win.If Staller plays rst on H n , a winning strategy is to play on each u i . Dominator has to answer on v i otherwise Staller wins immediately by isolating this vertex. When every u i is played, she can play on u and isolate it.So both players have a winning strategy when playing rst and thus o(H n ) = N . By Theorem 19, (H n , u) is neutral.

Figure 8 :

 8 Figure 8: Examples of hanging split graphs.

Figure 9 :

 9 Figure 9: Dierent possible reductions for trees.

Table 1 :

 1 Outcomes of the Maker-Breaker domination game played on the union of G and H. she has a winning strategy on G. Her strategy on G ∪ H is to play only on G following her winning strategy. If at some point Dominator is playing on H, this can be considered as a passing move in G and by Proposition 2 this does not compromise Staller's strategy. At some point she will isolate a vertex in G and thus in G ∪ H. Thus if G or H has outcome S, then whatever Dominator plays as a rst move, Staller still has a winning strategy on this graph. If both positions have outcome N then after Dominator's rst move, Staller can play on the other component and also wins. This proves the rst two points. If both positions have outcome D, then Dominator has a winning strategy on both graphs playing second. He can answer to every move of Staller on the component she plays with his winning strategy on this component. At the end, Dominator dominates both components and so G ∪ H has outcome D.

  where w is a new vertex) and for which xy is an edge if and only if xy is an edge of G or H or y = w and xu is and edge of G or xv is an edge of H.If the vertex u is clear from the context or does not matter, the glue will be denoted by G v H. Similarly if the vertex v is not useful in the notation, we might also remove it. Figure7gives a representation of the glued of two graphs. Representation of the glued graph of G and H on u and v.Let H be a graph and v a vertex of H. We say that the couple (H, v) is neutral for the glue operator if for every graph G and every vertex u of G,o(G u v H) = o(G).19. Let H be a graph and v be a vertex of H. (H, v) is neutral for the glue operator if and only if o(H) = N and o(H \ {v}) = D.Proof. First, let H be a graph and v be a vertex of H. Assume that (H, v)is neutral. Then o(K 1 v H) = o(K 1 ). Notice that K 1 v H = H and since o(K 1 ) = N , we necessarily have o(H) = N .Now consider the graph G that consists of H with a pendant vertex v attached to v. This corresponds to K 2 v H. Since (H, v) is neutral, G has the same outcome as K 2 that is D. In particular, Dominator has a winning strategy on G by playing second. If Staller plays rst on v, Dominator has to play on v . His remaining winning strategy is a winning strategy on H \ {v}.

					G u v H
	G u	v	H	G	w	H
	Figure 7: Theorem

  by Theorem 14. Note that G ∪ H is a subgraph of G H where only edges are removed so, by Proposition 3, o(G H) o(G ∪ H ) = o(G). We now show that o(G H) o(G) to conclude the proof. Note that if o(G) = D we necessarily have o(G H) o(G). Assume that o(G) N . This means that Staller has a winning strategy on G as rst player. Since o(H) = N , Staller also has a winning strategy on H as rst player. The following strategy is a winning strategy on G H for Staller as rst player. Staller begins by applying her winning strategy on H until the strategy requires her to play on w. If during this stage Dominator plays on w, by following her strategy, Staller will isolate a vertex on H dierent from w. This vertex is not connected to G so she wins. If Dominator plays on G \ {w} then Staller can imagine that Dominator has played on w and will win similarly. So we can assume that Dominator always answers in H . When Staller's strategy on H is to play on w, she switches to her winning strategy on G instead. Similarly as before, if Dominator does not answer in G \ {w}, Staller will win by isolating a vertex of G dierent from w. She continues to apply her winning strategy on G until this strategy requires her to play on w. Note that at this point w is a winning move for Staller both in G and H. Staller now plays w and answers to every move of Dominator with her strategy in the same component. Since she follows her winning strategy in G and H she will isolate a vertex in each of these graphs. If one of those two vertices is not w, then Staller wins because this vertex is isolated in G H. If both of these vertices are w, then w and its whole neighborhood are played by Staller in the glued graph and Staller wins. So Staller has a winning strategy as rst player in G H and o(G H) N . Assume now that o(G) = S, i.e. Staller has a winning strategy on G as second player. If Dominator begins by playing on w, then Staller can apply her winning strategy in G, she will isolate a vertex dierent from w will win. If Dominator begins by playing in H , then Staller can imagine that he played on w, apply her winning strategy on G and win similarly as before. So we can assume that Dominator begins by playing in G \ {w}. Then Staller can follow the same strategy as when she when playing rst and she wins. Thus o(G H) = S. These three cases prove that o(G u v H) o(G). Since we also have o


H Delebecque Supélec
email: henri.delebecque@supelec.fr

OPTIM: AUTHORING INTERACTIVE TEACHING DOCUMENTS WITH MINIMAL PROGRAMMING COST

This paper describes an open framework for teachers and lecturers in science. It will help them write their teaching documents even if these documents include interactive or multimedia content, leaving the entire presentation burden to the OPTIM rendering engine. This framework will also allow the global editor to define the authoring language automatically, and to put the structure common to sets of documents into classes for subsequent reuse.

Moreover, OPTIM gives the authors a way to insert interactive parts into their documents without any GUI programming skills.

INTRODUCTION

OPTIM is a general framework for authoring teaching material, which uses HDSML [START_REF] Delebecque | HDSML: a Hyper Document Structuring Meta Language[END_REF]), a meta-language more dedicated to the definition of teaching documents than XML [START_REF] Cowan | Extensible Markup Language 1[END_REF]. XML allows the definition of any markup language, a versatility that leads to a heterogeneity of XML based authoring languages, and a lack of standards in the pedagogical domain. A generalpurpose authoring language such as DocBook©, however, has its own drawbacks, since it defines only very general structural entities, like "header", "footer", "body".

We want to allow global document editors to define their own authoring language using the authors' usual terms as tag names. We think that this will be of great help for content authors, who are not always familiar with programming languages, and even less familiar with XML, to write their concrete documents. For example, mathematicians will greatly appreciate finding tags named «theorem», «premises», «conclusion» and «proof» in the authoring language they use. This is something that people have to do manually if they use authoring languages such as Latex.

The OPTIM framework extends HDSML capabilities by allowing authors to insert interactive objects into their teaching documents. Students and learners that use such material can visualize the concepts described in a graphical manner, while keeping additional textual descriptions.

The pedagogical domain has several good properties that help us: the graphical objects found in applications are of a limited variety, as is the kind of interaction the learners have with them. Pedagogical software (even simulators) commonly outputs its results either as graphs or as animated diagrams, and requires minimal or no user interaction for the inputs.

OPTIM: UNDERLYING PRINCIPLES

The acronym OPTIM stands for Open Platform for Teaching Interactively with Multimedia. OPTIM's goal is to give teachers an adaptable and lightweight framework that allows them to spend more time on content (whatever its form) and less in presentation problems, while using their favorite editing tool. This last point is a key one in the world of education, where languages and tools are usually domain-specific. It contributes to the openness of the OPTIM framework, a property that allows the author's investment to keeps its value over time and resists changes in proprietary format. OPTIM uses HDSML to describe the structure of the document's static part.

The global editor of the global teaching document will help teachers to write their sections/chapters/ books in a fairly uniform manner, by defining a structural model. It defines all the mandatory or optional elements available, which authors have to include in their document. The projection of the actual documents written by teachers onto various media is done by defining one presentation model per publishing medium. These models should be written probably by a specific designer, more familiar with ergonomics and graphics than our usual authors. HDSML has to be clearly a Meta language, since the structural model is also used to define the markup language, described above, that we will call the content authoring language.

Definitions

HDSML is used by the three different kinds of authors described in the following paragraph, while defining four kinds of documents, which are: the class (the structural model), the presentation model, the concrete document (a class instance), the interactive objects (OPTIM objects). The HDSML engine works in three phases, using the four different kinds of document listed above.

We want to guaranty the uniqueness of the source document, whatever publishing medium is used. The pair of models (one structural model and one presentation model) helps to achieve this goal by allowing the necessary separation between presentation and content as soon as possible. This dramatically reduces the authoring time spent during the meta-authoring phase that ends with the generation of a XSLT et al. 2001) file for each pair of models. Each XSLT file implements a projection function from the class to one specific publishing medium. As mentioned earlier, the HDSML engine will also define the authoring language grammar, based on the class definition.

Teachers will write their teaching documents using this grammar. This authoring task can be facilitated if they use XML compliant tools providing a syntax-sensitive help based on the grammar definition. Nevertheless, HDSML has proved its openness by working with documents written using other tools (and formats).

The HDSML engine takes the concrete documents and transforms them to publishable ones by applying the projection function devoted to the chosen publishing medium. These later documents are a mix between items taken from concrete documents, and others dedicated only to presentation purposes like a logo or the background.

During the publication phase (and when learners use them) the published documents can activate the OPTIM objects they contain. This activation will produce events that are filtered by the GUI defined in the OPTIM description file, and compiled as Java© objects by the OPTIM compiler during the previous phase.

Two different kinds of event may occur: purely "graphical" events (such as mouse-down, key-down, etc.) fully managed by the Java code, or "applicative" events. These last ones are transformed into requests sent to the computational code that answers with numerical results displayed as a graphic, a diagram, which can both be static or animated. This division into purely graphical events (also called low-level events) and more semantic events follows the evolution between Java's 1.0 and 1.2 event model.

OPTIM Architecture

Every interactive object included in a concrete document should be described in two complementary ways. First, the graphical designer has to explain how the graphical sub-objects will respond to enduser stimuli (click, keyboard events…). And, second the computation code should be able to send refresh orders to the GUI, when the code changes the data displayed. These two aspects are managed by a conventional MVC architecture evangelized by Java. This very efficient and robust way of separating the Model (in charge of all the computational tasks) and the View (that displays the values in the most convenient way) has proved its value since its first definition by the Smalltalk object-oriented design team [START_REF] Goldberg | Smalltalk-80: The language and its implementation[END_REF].

STRUCTURING ELEMENTS

The class designer builds the class using either generic blocks and objects or semantically qualified elements, such as those defining the author, the authoring platform, the document version, or others.

The block is the most versatile element, able to hold either generic elements, acting as sub-blocks, or objects. The inclusion of semantically qualified elements is not currently supported, since they are limited to the whole page description. A block definition in the class has a very important «name» attribute, that will give its name to the corresponding tag used by the teacher when the concrete document is written. The «name» attribute allows the domain-centered definition of the content authoring language. Finally, a block can be structured using sub-elements taken from the following non-exhaustive list: Block, Object, Keyword, OPTIM. The recursive nature of the block avoids the definition of a limiting list of structuring levels, as in DocBook, while giving it more descriptive power.

The object element is always a leaf of the XML node tree. It describes either non-structured elements (such as a picture, sound or movie) included by reference, or very basic structured elements. The keyword is a powerful tool for the content author, who can use it to add semantics to (potentially) every document element, even the smallest. The OPTIM element is the link between the actual concrete document and the interactive objects built using the OPTIM platform.

RELATED WORK OPTIM Versus Current IDEs

One can think that existing Integrated Development Environments, JBuilder©, or Visual Studio©, are the better choice for developing the interactive parts of our teaching documents. We think that these products are too complex for the rather simple graphical objects authors need. The complexity of the programming task should not be measured in the GUI's design, but rather in the development of the simulation part. And we think that versatility and openness is crucial here, allowing our teachers to use their favorite programming languages. Moreover, IDEs often impose the mastering of many specific programming skills -such as animation techniques, graphical algorithms, which are clearly not trivial-which requires a considerable investment, and constant updates.

Programmingless Development Tools

New products, like Gatonero appeared recently that allow the rapid design of interactive applications by non-programmers. It offers the ability to describe sophisticated prototypes using the specific language Gatonero defines, or the Gatonero Studio tool with drag-and-drop capabilities. Gatonero's architecture relies on a framework which is announced as "fully programmable and object based". Gatonero obviously offers inheritance capabilities but also prototypes re-usability, as multi-platform deployment, since it is Java based. We think that this kind of products does not fully meet the requirements of the teaching community. These products tend to propose Rapid Application Development tools for business purposes. Teachers , on the other hand, ask for a framework that allows them to present data produced by a regular computational code in a more pedagogical way. Moreover, like the SimTools project mentioned below, Gatonero suffers from a lack of openness, since it offers only one programming language. Clearly, this gives it the ability to be multi-platform but OPTIM can reach this goal in a different way by allowing the highly portable client-side software to interact with a computational code located on a dedicated remote server. This also requires the teacher to convert the computational code into a foreign programming language, at a great cost.

E-Learning Development Tools

We have found active projects, like the one described in [START_REF] Addison | A Tiered Approach Utilizing Reusable Componentware Methodologies for Multimedia Educational Software Creation and Development Proceedings of ED-MEDIA[END_REF], that try to give teachers a way to design interactive teaching documents without programming. This project is component-ware based, and has the same openness property as OPTIM, since it offers links with databases, e-mail, etc. But this project is currently based on the Delphi© programming language, and seems to have no capability to deal with other programming languages. Moreover, it lacks the regular model given by HDSML to OPTIM, and which guarantees a high level of adaptability to upcoming application domains.

Another project, SimTool [START_REF] Sassen | Instructional Design and Implementation of Interactive Learning Proceedings of ED-MEDIA[END_REF]) shares some of our goals. Experiments conducted using SimTool have shown that students greatly appreciate interactive counterparts to textual presentations. One of the major limits of SimTool is the choice of Java for both the GUI construction and the computational tasks. We think that these two complementary parts are better implemented by different authors, and that one should leave greater freedom in the choice of the computational language. The mastering of computer animation, graphic algorithms, and the full knowledge of the GUI's object library are required to design a good graphical user interface. On the contrary, the teacher who is, in this case, the knowledge reference, should only describe the computations required to supply data to be displayed. This task is complex enough, and we have to let teachers use their favorite programming language to achieve it. Moreover, SimTool's goal is the building of simulation applets, and it does not cover the whole design of their teaching document, as does HDSML.


Henri Delebecque Supelec
email: henri.delebecque@supelec.fr

OPTIM: AN OPEN PLATFORM FOR TEACHING INTERACTIVELY WITH MULTIMEDIA

Keywords:

In this paper, we propose an open framework for teachers and lecturers in science, to help them write their pedagogical documents with both static textual parts, and interactive and multimedia content. This framework will also allow them to factorize the structure common to all this documents into classes, and to free themselves from all other design considerations. Moreover, OPTIM allows authors to build interactive parts of these documents without any programming skills. The author can focus his attention to the pedagogical aspects, leaving the GUI generation to our engine. The computational code the teacher supplied, and that provides numerical values displayed by the GUI can be developed in various programming languages.

INTRODUCTION

We propose a general authoring framework, called OPTIM, which uses HDSML, a meta-language more specifically suited for the definition of structured documents than XML [Cowan 2002]. Moreover, OPTIM will allow the author to define interactive objects into pedagogical documents. This is of great interest in the pedagogical context, where students and learners can visualize the concepts described in an alternate graphical manner, while keeping an additional textual description.

OPTIM Principles

The OPTIM acronym means «Open Platform for Teaching Interactively with Multimedia». OPTIM's objective is to give to content authors a framework that allow them to focus on contents (in all its richness) and ignore presentation's problems, while using their favorite editing tool. OPTIM uses HDML [Delebecque 2003] as structuring language that allows the description of the static part of the document. Authors can add interactive parts into their documents using first the OPTIM's GUI generator, and then its ability to link this GUI with the computational code that supplies the information displayed as curves or dynamic schematics.

To allow authors to focus their attention to content, and ignore presentation problems, a structural model is defined by the editor of the whole pedagogical document. This model defines all the mandatory or optional elements content authors have to put into their documents. HDSML is clearly a meta language, since this model is also used to define a markup language that we will call the content authoring language. This language defines tag names that are very familiar to the content authors, since they are defined by the editor, using the words and terms authors currently use.

We will start with some definitions, which help us while presenting the general principles. For more clarity, the following definitions are done in the context of a large pedagogical document, we will generalize hereafter under the global document term.

Definitions

HDSML can be used by authors following three different roles described in the next paragraph, while defining three kinds of documents, which are:

 The class (the structural model),  The presentation model,  The concrete document (a class instance).  The interactive objects to be inserted (Optim objects)

The class designer, who is also the whole pedagogical document editor, defines the structural model common to all the pedagogical sub-documents. The graphics designer, or the ergonomist, designs the look-and-feel used to display these structure elements on a specific presentation medium, in a presentation model. Last, the content author instantiates the class in concrete documents.

The HDSML engine works in three phases, using the four different kinds of document described above.

HDSML Engine

Meta authoring phase

To ensure the uniqueness of the source document, whatever publishing medium is used, we define the notion of pairs of models. For every meaningful subset of the global document (book, chapter, section…), the document editor can supply a specific class (the structural model) using HDSML, and the graphics designer can provide a specific presentation model for any presentation medium. This is done during the first phase, we call the meta-authoring phase.

The HDSML engine takes all these pairs of models, and then automatically generates a XSLT [Adler et al 2001] style-sheets for each one, building a projection function from the class to the presentation model. Moreover the HDSML engine produces the grammar of the authoring language, which will be used by the content author in the next phase.

Authoring Phase

Then, the content authors will write the concrete documents, using any tools they want, including not XML compliant ones. The great advantage of using XML compliant editing tools is that they are able to provide context sensitive help. Obviously, an editing tool able to understand the XML Schema [Brown et al 2001] grammar definition (provided by HDSML during the previous phase) can display the attributes which are valid for the tag currently edited, or the children it will accept.

Pre-publication phase

In this phase, the HDSML engine applies the projection function to the concrete documents that conform to the class structure, generating the documents to be published. These later documents are a mix between items supplied by content authors, and others solely bounded to presentation (i.e. background, logo,…) and provided by the presentation model.

Publication phase

In this last phase, the authors can activate the new functionality OPTIM adds to HDSML, and transform their static documents into interactive ones. Since the concrete documents can reference OPTIM objects, these objects will be activated at publishing time by the student. This activation will produce events that are sent to the GUI defined by the author, and compiled as Java© objects by the OPTIM compiler. Every event is either completely managed by the Java code, or transformed into a request sent to the code that the content author supplied, to achieve the computation required. This code can, for example, compute a new 3D-curve to be displayed, the new state of a data path into a processor, or some animation, sound, etc.

OPTIM versatility 1.3.1 Computational language

OPTIM accepts currently Java computational code. But it will be quickly extended to many other domain specific languages, since its working principle requires only basic exchanges between the GUI and the domain-specific code, as explained in the section devoted to the OPTIM architecture. We plan to interface languages like Mathematica and Matlab.

Concrete documents format

HDSML also accepts as concrete document any file not expressed in one of its authoring language at all. We have designed for a special kind of files (namely Microsoft Word © [Microsoft 2004] ones) a specific front-end. It analyzes the content according to grammatical rules, stored in a specific file, called the front-end grammar file. These rules describe how the bookmarks and styles found in the document have to be interpreted to reveal the document internal structure.

One advantage of XML is the great amount of flexibility its tags offer; however, this flexibility also results in a great variety of semantics given to tags by the various authoring languages based on XML, and a lack of standard in this domain. On the contrary, a general authoring language like DocBook © [Walsh et Muellner 1999] have its drawback, since it defines only very general structural entities, like header, footer, body.

We want to help content authors, not always familiar with programming languages, and even less with XML, to write their concrete documents, by defining an authoring language that will use only their domain specific terms. For example, a mathematician will greatly appreciate to find tags named «theorem», «premises», «conclusion», «proof» in the authoring language he/her uses. This is something that people have to code manually if they use languages like Latex.

HDSML Concepts

Let us start with the main structuring entity that both the class designer and the content authors will use: the element.

The Element

All the authors structure their classes or concrete documents by dividing them in meaningful parts they will put into elements. For HDSML, an element is a XML tree node, such as a header or footer structure description (in the class), its content (in a concrete document) or its appearance (in the presentation model, actually using HTML nodes).

The Class

The class definition, (also called the structural model) shared by all the concrete documents, is the editor's responsibility. The actual structure of the concrete documents can be loosely linked to the model that the class defines, since the class designer can describe some elements as optional or mandatory, unique or multiple (like using the Kleene operators).

The class design is done customizing the building blocks that HDSML defines (or instantiating them in a object-oriented meaning), to describe the structure common to the global document.

The Presentation Model

The presentation model should probably be designed by a specific author, since it implies more knowhow in ergonomics and graphics than in the normal content domain. This author can choose the presentation language best suited for his/her presentation medium, as long as it is supported by the HDSML engine (currently all the HTML dialects). The author also can use any authoring tool for this task. This model defines the appearance of the all building blocks defines into the class, and that should or can be displayed on that medium.

The Concrete Document

Content authors can freely edit their concrete documents, using their favorite publishing tool, without the burden of sharing a common document. Despite this complete freedom, the global document editor can always compile all the concrete documents in a single one which references them, and publish it after the projection by the HDSML engine.

Another great advantage of this concrete document set is its uniqueness, even if it has to be published on multiple media, thanks to projection functions generated by the HDSML engine. This uniqueness gives to the content authors the insurance that the information published on every medium will conform to the content they have defined, even if it is very dynamic.

OPTIM Architecture

Every interactive object included into a concrete document should be described in two complementary ways. First, the author have to explain how the graphical sub-objects will answer to end-user stimuli (click, keyboard events,…). On the opposite, the computation code should be able to send refresh orders to the GUI, when new data arrives. These two aspects are managed by a classical MVC architecture evangelized by Java. This very efficient and robust way to separate the Model (in charge of all computational tasks) and the View (that displays the values in the most convenient way for a given context or user) has proved its value since its first definition in the Smalltalk [Goldberg et Robson 1998] object-oriented language.

STRUCTURING ELEMENTS

The class designer builds the class using generic blocks, objects and semantically qualified elements, such as those defining the author, the authoring platform, the document version, or others.

Every element of a class definition inherits the occurrence constraints that HDSML defines. But the class author can modify them, according to the structural freedom he wants to give to his concrete document authors. This way, he will define the occurrence constraints of the content authoring language elements.

The Elements

The Page Element

The page is the XML root node of every HDSML document. A page includes the semantically qualified elements that describe the whole page, and generic ones, that define a common document structure.

The Block Element

The block is the most general element, able to hold other generic ones, like (sub) blocks or objects. The inclusion of semantically qualified elements is not currently supported, since they are theoretically limited to the whole page description.

A block owns a very important «name» attribute, that will give its name to the corresponding tag used by the content author when he writes his concrete document. An optional «type» attribute specifies the kind of block as for example: header, menu, footer, body or form.

The «name» attribute allows the domain centered definition of the content authoring language. This language will be very fine tuned to content authors, since it named the structuring units they will use with their most familiar terms.

Finally, a block can be structured using sub elements taken in the following non exhaustive list:

 Block  Object  Keyword  Import  Optim
The block recursive nature avoids the definition of a specific structuring levels, as defined by some structuring languages like DocBook, while giving it more descriptive power.

The Object Element

The object element is always a leaf of the XML node tree. Its purpose is to describe either non-structured elements (such as picture, sound or movie) or very basically structured elements (such as the «link» or the «field» objects).

The «link» object is a regular association between a text part (the link source) and an URI (the link target). The «field» object is also an association, between a text part (the field name) and an un-typed value (the field value), mostly used in forms. Many other object types exist, and more can be added by class designers.

The Keyword Element

The keyword is a powerful tool for the content author, who can use it to add semantics to potentially every document element.

These fine grain defined keywords are of great utility for information retrieval systems or more generally the Semantic Web Activity [START_REF] Bourda | Henri Delebecque Learning Resources and the Semantic Web Proceedings of Ed-MEDIA 2003[END_REF]] applications. The current full text search tools often return irrelevant documents, since they are unable to use the word definition context for filtering. We all know that the same word can have a lot of meanings, depending on this context: for example, «Washington» can be understood as the last name of a person, a state's name, a city name, …. HDSML allows the definition of keywords in an element context, allowing finer semantically based searches.

The Import Element

The import element allows content authors to factorize document parts (either structured or non structured) in external files, dramatically reducing the global document maintenance cost by removing redundant information. The same feature is of course available to the class designer, to factorize without inheritance, reaching multiple inheritance power.

The Optim Element

The Optim element is the link to interactive objects build using the OPTIM platform. Since the description language of Optim elements is still the authoring language, we keep the content author in a familiar context. Moreover, by allowing the user to supply the computational code in many languages (including those that require specific run-time), we insure the maximal adaptability to most scientific domains.

Example

Let us give an example, with few lines of HDSML defining a class block named «Theorem», followed by an example of one theorem definition in a concrete document. <Block name="Theorem" type="body"> <Object name="Name" type="text" Occurs="1" /> <Object name="Premises" type="text" Occurs="1"/> <Object name="Conclusion" type="text"Occurs="1" /> <Object name="Proof" type="text" Occurs="1" /> <Object name="Keyword" type="text" Occurs="*" /> </Block>

The previous HDSML fragment means that the class designer defines the Theorem generic structure with the following sub-elements:  a mandatory name (which is a text zone),  a mandatory proposition, conclusion and proof,  some optional keywords, as in the following example: <Theorem> <Name>Thales</Name> <Keyword>Geometry</Keyword> <Premises>Let and be two points …</Premises> … </Theorem> We can see that the content authoring language uses domain centered entity names, instead of the generic ones (like block) HDSML defines.

RELATED WORK

HDSML versus Tag Libraries or XSLT

One can think that the powerful capabilities tag libraries like those defined by Struts [Apache group 2000] add to HTML, allowing an easy creation of a coherent set of HTML pages, fulfill our objectives. We think that tag libraries are clearly a good solution, but limited to the HTML production, and probably more oriented towards dynamic HTML. Moreover, they tend to stress on the look-and-feel, when we want to free the authors from such considerations, and stress on semantics and document's structure. CSS share the same drawback.

The XSL sheets offered in the XML tools family, has multiple drawbacks for a content author: he has to fully master XML and XSL. And this mastering has to be regularly exercised for two reasons. First, the author has to write a separate XSL sheet for every presentation medium used, and for every subset of the document. Then, this XSL writing task must be redone every time the user changes the look and feel, and for every presentation medium, and for every subset of the global document.

Moreover, this way of producing web pages doesn't allow the factorization and genericity our tool allows, nor any possibility for handling interrelations between documents. It doesn't provide either any way to manage the document versioning the HDSML engine supports, and which is of great help in managing the production of many contents author.

OPTIM versus current IDEs

One can think that existing Integrated Development Environments, like JBuilder©, or Visual Studio©, are solutions to our problem. We think that these products are really powerful, and maybe too powerful for the rather simple graphical objects authors need. The complexity of the programming task should not be measured in the GUI's design, but rather in the simulation part. And we think that it is very important to leave our content author using his/her favorite programming language in that case. Moreover, IDEs impose often the mastering of many specific programming skills, such as animation techniques, graphical algorithms, which are clearly not trivial, and require a great investment.

E-Learning Development Tools

We can found currently projects, like the one described in [START_REF] Matsuno | Richard Gilbert A Tiered Approach Utilizing Reusable Componentware Methodologies for Multimedia Educational Software Creation and Development Proceedings of[END_REF], that tends to help teachers in designing interactive pedagogical documents. This component-ware based software allows the teacher to create very sophisticated graphical applications without programming. It offers links with databases, and many other services. But it is based on a component-ware architecture, and lacks of a general paradigm, like HDSML. Moreover, this software is currently based on the Delphi© programming language, and seems to have no capability to cooperate with other programming language, for the computational requirements of the simulated objects.

Another project, named SimTool [START_REF] Sassen | Stefan Voß Instructional Design and Implementation of Interactive Learning Tools Proceedings[END_REF], embedded in the more ambitious VORMS project, shares some of our goals. Experiments done using SimTool have proved that students are highly motivated by interactive counterparts to textual presentations. One of the major differences we have found between SimTool and OPTIM is the implementation language, Java, which is, in the case of SimTool, the unique programming language, used for both the GUI construction and the computational tasks. We think that these two complementary parts will be better implemented by different authors. The GUI design involves the mastering of computer animation, graphic algorithms, and the full knowledge of the GUI's object library available. On the opposite, the computational part has to be written by the teacher, which is, in this case, the knowledge reference. Moreover, SimTool is only a tool for building simulation applet, and does not try to help the teacher throughout the whole design of his/her pedagogical document, as HDSML.

Another Hypertext Language?

The author familiar with HTML can have fear to throw away all this heavily acquired knowledge and to learn another hypertext dialect. We have multiple answers.

First, many excellent XML editors exist, for every platform, allowing everybody to find the one that meets its requirements. Such tools can be configured using the HDSML syntax we supplied, allowing a very high learning curve of HDSML, even for beginner editors. Such editing tools tutor users and help them by supplying only the tags allowed in the current context of definition.

The content author can also find all the legal attributes of every element, with a list of their possible values. Moreover, we plan to work on more conversion tools, expanding the way opened with the Word front-end processor already operational [Delebecque 2003]. These tools will be able to extract the structure of documents produced by the most common word processing tools available. Our goal is to simplify authors work and no to ask them to learn a new and strange language.

Is OPTIM universal?

We do not think to solve all the problems that communication between GUI and applicative code can rise, nor pretend to define an universal tool for building interactive applications. We try to describe an architecture that allows an easy separation between GUI and applicative code in an educational context, that have two main characteristics. First the GUI used in a pedagogical context are rather simple, and use a small number of