Valentin Gledel

Nacim Oijid

Avoidance games are PSPACE-Complete

Keywords: 2012 ACM Subject Classification Theory of computation → Problems, reductions and completeness Games, Avoider-Enforcer, Maker-Breaker, Complexity, Avoider-Avoider, PSPACE-complete

Avoidance games are games in which two players claim vertices of a hypergraph and try to avoid some structures. These games have been studied since the introduction of the game of SIM in 1968, but only few complexity results have been found out about them. In 2001, Slany proved some partial results on Avoider-Avoider games complexity, and in 2017 Bonnet et al. proved that short Avoider-Enforcer games are Co-W[1]-hard. More recently, in 2022, Miltzow and Stojaković proved that these games are NP-hard. As these games correspond to the misère version of the well-known Maker-Breaker games, introduced in 1963 and proven PSPACE-complete in 1978, one could expect these games to be PSPACE-complete too, but the question has remained open since then. Here, we prove here that both Avoider-Avoider and Avoider-Enforcer conventions are PSPACE-complete.

Using the PSPACE-hardness of Avoider-Enforcer, we provide in appendix proofs that some particular Avoider-Enforcer games also are.

Introduction

Related works

Avoidance games belong to the class of positional games, that were introduced by Hales and Jewett in 1963 [START_REF] Hales | Regularity and positional games[END_REF] and popularized by Erdős and Selfridge in 1973 [START_REF] Erdös | On a combinatorial game[END_REF]. In this class of games, the board is a hypergraph and two players alternately claim a vertex of the hypergraph that has not been claimed before. Winning conditions depend on the convention and are related to the hyperedges. Tic-Tac-Toe and Hex are two famous examples of positional games.

To learn more about positional games, we refer the reader to the recent survey of Hefetz et al. [START_REF] Hefetz | Positional games[END_REF].

Among positional games, a natural dichotomy exists: on the one hand, there are games in which players seek to build a structure, and on the other hand, there are games in which players want to avoid a structure. The former set contains both Maker-Maker and Maker-Breaker conventions, in which the hyperedges are winning sets, and the player either wants to fill up a winning set (Maker role), or to play at least once in each of them (Breaker role). The latter contains Avoider-Avoider and Avoider-Enforcer conventions, that can be seen as the misère version of the former. In these games, the hyperedges are losing sets, and the players either want not to fill up one losing set (Avoider role), or to force their opponent to fill up one of them (Enforcer role).

When positional games were introduced, the focus was on Maker-Breaker games, i.e.

games in which one player, Maker, aims to fill up a hyperedge, and the second one, Breaker, wants to prevent it by claiming at least one vertex in each hyperedge. This convention is the most popular one, and several games have been studied according to this convention. In particular, the survey of Beck [START_REF] Beck | Combinatorial games: tic-tac-toe theory[END_REF] presents several results obtained for Maker-Breaker games.

The field of Maker-Breaker games is still well investigated today, and some Maker-Breaker games were introduced recently [START_REF] Duchene | Maker-Breaker domination game[END_REF][START_REF] Nenadov | On the threshold for the Maker-Breaker H-game[END_REF].

The first Avoider-Avoider game was introduced in 1968 with the game of SIM and is presented in [START_REF] Simmons | The Game of SIM[END_REF], but the first study of the complexity of Avoidance games was done by Schaefer in 1978 [START_REF] Thomas | On the Complexity of Some Two-Person Perfect-Information Games[END_REF]. Avoider-Enforcer games were introduced later by Lu in 1991 [START_REF] Lu | A matching game[END_REF][START_REF] Lu | A note on biased and non-biased games[END_REF] under the name of Antimaker-Antibreaker games and correspond to the misère version of Maker-Breaker games. The standard name for this convention, Avoider-Enforcer, was popularized by Hefetz and different co-authors in 2007 [START_REF] Hefetz | Positional games on graphs[END_REF][START_REF] Hefetz | Fast winning strategies in positional games[END_REF][START_REF] Hefetz | Avoider-Enforcer games[END_REF][START_REF] Hefetz | Bart-Moe games, JumbleG and discrepancy[END_REF]. In this game, Enforcer wins if at some point during the game, Avoider has claimed all the vertices of a hyperedge, otherwise Avoider wins.

Even if most of the studies of positional games are focused on Maker-Breaker games, Avoider-Enforcer games have become more and more relevant: the famous Ramsey game was introduced in Avoider-Enforcer convention by Beck in 2002 [START_REF] Beck | Ramsey games[END_REF] as a generalization of SIM.

As it was done in the Maker-Breaker convention, some games on graphs were introduced in Avoider-Enforcer or Avoider-Avoider conventions, where the loosing sets correspond to some structure in the graph, see [START_REF] Anuradha | How long can a graph be kept planar? the electronic journal of combinatorics[END_REF][START_REF] Barát | On winning fast in Avoider-Enforcer games[END_REF][START_REF] Grzesik | Avoider-Enforcer star games[END_REF][START_REF] Hefetz | Avoider-Enforcer: The rules of the game[END_REF].

In terms of complexity, an overview of the field is proposed by Demaine [START_REF] Demaine | Playing games with algorithms: Algorithmic combinatorial game theory[END_REF]. In positional games, as they are perfect information games, one player always has a winning strategy (or both players can ensure a draw). The natural decision problem related to games is therefore: does the first player have a winning strategy? This problem was quickly proven to be PSPACE-complete for Maker-Breaker games by Schaefer in 1978 [START_REF] Thomas | On the Complexity of Some Two-Person Perfect-Information Games[END_REF] even restricted to 11-uniform hypergraphs (i.e. hypergraphs in which all hyperedges have size 11). This bound was recently improved by Rahman and Watson in 2021 [START_REF] Md | 6-Uniform Maker-Breaker Game Is PSPACE-Complete[END_REF], proving that the problem is still PSPACE-complete if the hypergraph is 6-uniform. These two proofs are very technical and a simpler proof of the PSPACE-completeness was provided by Byskov in 2004 [START_REF] Makholm | Maker-Maker and Maker-Breaker games are PSPACE-complete[END_REF], proving at the same time that Maker-Maker games are also PSPACE-complete. The complexity of Maker-Breaker games is still studied today, as Galliot et al. [START_REF] Galliot | Maker-Breaker is solved in polynomial time on hypergraphs of rank 3[END_REF] have proven that the winner of a 3-uniform Maker-Breaker game can be computed in polynomial time, but the gap between the complexity of 6-uniform hypergraphs and 3-uniform hypergraphs remains to be closed.

Despite the fact that Avoidance games were introduced at the same time as Maker-Breaker games, only partial results on complexity are known: determining the winner in Avoider-Avoider games, was proven to be PSPACE-complete by Slany in 2002 [START_REF] Slany | Endgame problems of Sim-like graph Ramsey avoidance games are PSPACEcomplete[END_REF] for endgames, i.e. games in which some vertices are already attributed to the players, but there are no results yet in the general case. Concerning Avoider-Enforcer, Bonnet et al. in 2017 [START_REF] Bonnet | The Parameterized Complexity of Positional Games[END_REF] mentioned that the complexity of this problem is still open, when they proved that short games, i.e. games in which a player only has few moves to make, are co-W[1]-hard, with the number of moves taken as a parameter. The best known result today is due to Miltzow and Stojaković in 2022 [START_REF] Miltzow | Avoider-Enforcer Game is NP-hard[END_REF] that states the NP-hardness of this decision problem and conjectures its PSPACE-completeness.

Presentation of the results

The Avoider-Enforcer game is played as follows: given a hypergraph This paper will focus on the proof of the following result:

Theorem 2. The Avoider-Enforcer problem is PSPACE-complete, even when the entry is restricted to hypergraphs with hyperedges of size at most 6.

Our proof of Theorem 2 follows a similar idea to the proof of Rahman and Watson [START_REF] Md | 6-Uniform Maker-Breaker Game Is PSPACE-Complete[END_REF] and the proof of Schaefer [START_REF] Thomas | On the Complexity of Some Two-Person Perfect-Information Games[END_REF], by constructing some hyperedges forcing the order of the moves. Contrary to Maker-Breaker games, in Avoider-Enforcer convention, there is no vertex in which the players are urged to play, as in general, players do not want to move in avoidance games. The key idea of this reduction is to create some structures in which playing first is a losing move. In the provided construction, at any moment of the game, only few moves are not losing moves. Thus, we can control the vertices played by the two players.

The proof provided for PSPACE-completeness of Avoider-Enforcer games, enables us to state the following corollary for Avoider-Avoider games that will also be proven later: This paper is organized as follows. In Section 2, we introduce two lemmas that will be used in the proof of Theorem 2. In particular, we show that pairing strategies that are often used in Maker-Breaker conventions can also be applied to Avoider-Enforcer games.

Section 3 describes the reduction used to prove the PSPACE-completeness and define an order on the move that we call the legitimate order. We also show in this section that the proof holds if both players follow the legitimate order. In Section

Preliminaries

In Maker-Breaker games, if a vertex is in all the hyperedges, it is always an optimal move for both players to play it. Here, we present a similar result for Avoider-Enforcer games. This result was proved by Miltzow and Stojaković [START_REF] Miltzow | Avoider-Enforcer Game is NP-hard[END_REF], and intuitively states that if a vertex v is in all the hyperedges that contains another vertex u, then claiming v before u cannot benefit any player.

Lemma 5.

Let H be a hypergraph, and u, v two vertices of H such that, for every hyperedge e containing u, e also contains v. If a player has a winning strategy, then this player has a winning strategy in which he never claims v while u is unclaimed.

The second tool we introduce here is pairing strategies in Avoider-Enforcer games. In Maker-Breaker convention, these strategies are often described by using the fact that a player can claim at least one vertex in each pair of vertices. Here in Avoider-Enforcer convention, the main idea of pairing strategies is that this is always possible to force the opponent to claim at least one vertex in each pair.

In this section, we will refer to the players as Alice and Bob, as the strategy can be applied both by Avoider and by Enforcer. Bob has a strategy which forces Alice to claim v and at least one vertex in each pair (a i , b i ).

Lemma
A strategy satisfying the hypothesis of Lemma 6 will be called a pairing strategy.

Proof. Consider the following strategy for Alice:

If Bob claims a vertex in a pair (a i , b i ), she claims the other vertex of the pair.

Otherwise, she claims any vertex that is not in a pair.

By construction; when it is Bob's turn, in any pair in which he has played, Alice has also played. Therefore, when it is Alice's turn, there is at most one pair of vertices in which she has to play. As Alice plays the last move, whenever it is her turn to play, the number of remaining vertices is odd. Therefore, if Bob does not play in a pair, at least one vertex in no pair will be available for Alice. Thus, Alice has a strategy to force Bob to claim at least one vertex in each pair (a i , b i ). Now, consider the following strategy for Bob:

If Alice claims a vertex in a pair (a i , b i ), he claims the other vertex of the pair.

If Alice claims v, if there exists at least one pair (a, b) in which Alice has not played, he claims a and he considers now that b is the new vertex that Alice will be forced to claim.

Otherwise, he claims any vertex that is not in a pair nor v.

For the same reason, with this strategy, when it is Alice's turn, in any pair in which she has played, Bob has played too. When it is Bob's turn, note that the number of remaining moves is even, and there always exists exactly one vertex that is not in a pair, and that Bob wants Alice to claim. Thus, the number of vertices on which Bob cannot play before Alice is odd. Therefore, he always has an available move that fulfills this strategy.

Proof of the main theorem

In this section, we begin the proof of Theorem 2 by describing the reduction from 3-QBF, introducing an order on the move of Avoider and Enforcer called the legitimate order and providing a sketch of the general proof.

Theorem 2. The Avoider-Enforcer problem is PSPACE-complete, even when the entry is restricted to hypergraphs with hyperedges of size at most 6.

The first step of the proof is to prove that this game is in PSPACE.

Lemma 7. The Avoider-Enforcer problem is in PSPACE.

Proof. Let H = (V, E) be a hypergraph. As the players are not allowed to play an already claimed vertex, any game ends after at most |V | moves. Therefore, according to Lemma 2.2

of Schaefer [START_REF] Thomas | On the Complexity of Some Two-Person Perfect-Information Games[END_REF], as the game has a polynomial length and a polynomial number of moves, its winner can be computed with polynomial space.

Construction of the hypergraph

We reduce the problem 3-QBF to an Avoider-Enforcer game. This problem has been proven PSPACE-complete by Stockemeyer and Meyer [START_REF] Larry | Word problems requiring exponential time (preliminary report)[END_REF], and we use the gaming version of this problem as it was formulated by Rahman and Watson [START_REF] Md | 6-Uniform Maker-Breaker Game Is PSPACE-Complete[END_REF]. The game is played on a quantified formula ϕ of the form ∀X 1 ∃X 2 . . . ∀X 2n-1 ∃X 2n ψ, with ψ a 3-SAT formula.

Alternately, two players, namely Falsifier and Satisfier, chose valuation for the variables, Falsifier for the odd variables (quantified with a ∀) and Satisfier for the even ones (quantified with a ∃). When all the variables have a valuation Satisfier wins if ψ is satisfied, otherwise, Falsifier wins.

Problem 8. 3-QBF Input: A 3-SAT quantified formula ϕ of the form ∀X 1 ∃X 2 . . . ∀X 2n-1 ∃X 2n ψ.

Output: True if and only if Satisfier has a winning strategy in the 3-QBF game on ϕ

Given a 3-QBF formula of the form defined in Problem 8, we construct a hypergraph with 10n vertices

x 1 , x 1 , . . . , x 2n , x 2n , u 1 , u 2 , . . . , u 6n .
A round in a 3-QBF formula corresponds to a step i during which Falsifier gives a valuation to X 2i-1 and then Satisfier gives a valuation to X 2i . In this reduction, any round corresponds to ten vertices and eight hyperedges. Four of the ten vertices are {x 2i-1 , x 2i-1 , x 2i , x 2i }, and the six others are u 6i-5 , u 6i-4 , u 6i-3 , u 6i-2 , u 6i-1 , u 6i . The eight hyperedges are constructed as follows:

A 2i = (x 2i , x 2i , u 6i+1 , u 6i+3 ) C + 6i = (u 6i , u 6i+1 , u 6i+3 , x 2i ) C + 6i-2 = (u 6i-2 , u 6i-1 , u 6i+1 , x 2i ) C + 6i-4 = (u 6i-4 , u 6i-3 , u 6i-1 , x 2i-1 ) B 2i-1 = (x 2i-1 , x 2i-1 , u 6i-1 ) C - 6i = (u 6i , u 6i+1 , u 6i+3 , x 2i ) C - 6i-2 = (u 6i-2 , u 6i-1 , u 6i+1 , x 2i ) C - 6i-4 = (u 6i-4 , u 6i-3 , u 6i-1 , x 2i-1 )
If some of these vertices do not exist, we still add the hyperedges, but with fewer vertices in them. For instance, A 2n = {x 2n , x 2n }. Moreover, for each clause F j = l j 1 ∨ l j 2 ∨ l j 3 ∈ ψ where the vertices l j 1 , l j 2 and l j 3 are literals either positive or negative, we add a hyperedge D j . For

k = 1, 2, 3, if l j k is a positive variable X p , then x p is in D j , if l j k is a negative one ¬X p , then x p is in D j . Moreover, If p is odd, then u 6p-1 is in D j , if p is even, then u 6p+1 is in D j .
Finally, the CNF game ϕ is reduced to the hypergraph H = (V, E) with

V = {{x i } 1≤i≤2n ∪ {x i } 1≤i≤2n ∪ {u j } 1≤j≤6n } E = {A 2i } 1≤i≤n ∪ {C + 2i } 1≤i≤3n ∪ {C - 2i } 1≤i≤3n ∪ {B 2i-1 } 1≤i≤n ∪ {D j } 1≤j≤m
With this construction, we say that Avoider and Enforcer follow a legitimate order if they claim board elements in the following order for increasing i:

Legitimate order during round i 1. Avoider starts and claims u 6i-5 .

2.

Enforcer claims u 6i-4 .

3.

Avoider claims u 6i-3 .

Enforcer claims one of x

2i-1 or x 2i-1 .

Avoider claims the remaining vertex in (x

2i-1 , x 2i-1 )
6. Enforcer claims u 6i-2 .

7.

Avoider claims u 6i-1 .

8.

Enforcer claims u 6i . 9. Avoider claims one of x 2i or x 2i .

10. Enforcer claims the remaining vertex in (x 2i , x 2i ).

Sketch of the proof

To prove that, with our construction, Avoider wins the Avoider-Enforcer game, if and only if Satisfier wins the QBF game, we first prove that this statement is true if the order of the moves is legitimate, as the moves will correspond to a valuation obtained in QBF.

To force the players to play in the legitimate order, the main idea of the construction is that players want to claim some vertices as late as possible. Therefore, we prove that it is always optimal to respect the legitimate order of the moves. We introduce the following three lemmas that will be proved in the next section.

Lemma 9. When the game is restricted to the legitimate order, Avoider has a winning strategy in the Avoider-Enforcer game on H if and only if Satisfier has a winning strategy

for the 3-QBF game on ϕ.

Lemma 10. If Enforcer has a winning strategy in H when the legitimate order is respected by the two players, then he has a winning strategy in H.

Lemma 11. If Avoider has a winning strategy in H when the legitimate order is respected by the two players, then she has a winning strategy in H.

We first admit these lemmas and we prove Theorem 2.

Proof. First, according to Lemma 7, we know that Avoider-Enforcer is in PSPACE. We now prove the PSPACE-hardness of the problem by reduction from 3-QBF.

Let ϕ be a 3-SAT quantified boolean formula of the form described in Problem 8.

Consider the hypergraph H obtained from ϕ by following the construction of Section 3.1. This construction has polynomial size. According to Lemma 9, when the order is respected, if Satisfier (Falsifier resp.) has a winning strategy in ϕ, Avoider (Enforcer resp.) has a winning strategy in H. Thus, according to Lemma 11 (Lemma 10 resp.), if Avoider (Enforcer resp.) has a winning strategy on H when the legitimate order is respected, she (he resp.) has one in general in H. Thus, Satisfier wins on ϕ if and only if, Avoider wins on H. Therefore, the

Avoider-Enforcer problem is PSPACE-complete.
As all the construction provides a hypergraph H in which all the hyperedges have of size at most six, the Avoider-Enforcer problem is PSPACE-complete even restricted to hypergraphs in which all the hyperedges have size at most six.

Game in legitimate order

In this section, we suppose that both players follow a legitimate order of moves.

If the order of moves is legitimate, the only choices available for Avoider and Enforcer are on the vertices x i and x i . For each 1 ≤ i ≤ 2n, Avoider claims one of x i , x i and Enforcer the other. Therefore, if both Avoider and Enforcer play one vertex in {x i , x i }, we define the underlying valuation given to ψ as the following one:

X i = T rue if
) for l k ∈ F j , where x(l j k ) = x p if l j k = X p and x(l j k ) = x p if l j k = ¬X p . If this
is the case, then this means that the formula ψ is not satisfied by the underlying valuation because the clause F j has all its literals assigned to False. On the contrary, if the formula ψ is satisfied by the underlying valuation, then, for all clause F j , at least one of the literals in it is assigned to True and so Enforcer played at least once in each hyperedge D j .

Therefore, Avoider won the game on H if and only if ψ is satisfied.

Suppose Satisfier has a winning strategy S on ϕ. We define a strategy for Avoider as follows: Whenever Avoider has to play a vertex x 2k or x 2k , Avoider considers the underlying valuation given to the X i s with i < 2k. Then, if Satisfier had put X 2k to True, she claims x 2k . Otherwise, she claims x 2k . With this strategy, at the end of the game, the underlying valuation of the variables of H will the same as the valuation given by the game that Satisfier played on ϕ. Since Satisfier has a winning strategy on ϕ, the underlying valuation satisfies ψ and so Avoider wins the game.

Similarly, if Falsifier has a winning strategy, Enforcer can follow the strategy in such a way that at the end the valuation of variables in the game played by Falsifier correspond to the underlying valuation in H. Since Falsifier wins on ϕ, Enforcer wins the game on H.

Proofs of Lemma 10 and Lemma 11

The first part of our constructions showed that, if the legitimate order is respected, Avoider wins if and only if Satisfier wins the 3-QBF game. We now prove that, if a player has a winning strategy when the order is respected, he has one even if his opponent does not respect the order. We introduce here different sets of variables. These sets will be the main tools of the proofs of Lemma 10 and Lemma 11.

For i = 1 to 4n, we define the set of vertices S i as S 4n = {u 6n , x 2n , x 2n } and for i < 4n:

if i = 4k, S i = {u 6k , x 2k , x 2k , u 6k+1 } ∪ S i+1 if i = 4k -1, S i = {u 6k-2 , u 6k-1 } ∪ S i+1 if i = 4k -2, S i = {x 2k-1 , x 2k-1 } ∪ S i+1 if i = 4k -3, S i = {u 6k-4 , u 6k-3 } ∪ S i+1

Proof of Lemma 10

We now prove Lemma 10

Proof. Suppose Enforcer has a winning strategy when the legitimate order is respected.

Consider a strategy for Enforcer in which he plays according to the legitimate order until Avoider does not. If Avoider respects the order until all the vertices are played, by assumption, Enforcer wins. Otherwise, the proof of the following claim provides a winning strategy for Enforcer.

Claim 13. If, during the game, Avoider plays in a set S i in which Enforcer has not played yet, then, after this move, Enforcer has a strategy to win the game.

Proof. The proof is by induction on i.

First, notice that each S i has an odd number of vertices and, as the total number of vertices in H is 10n, there is also an odd number of vertices outside S i . Therefore, if Avoider plays first in an S i , Enforcer answers by playing an arbitrary vertex that is not in S i and considers an arbitrary pairing outside S i , which exists as there is an even number of vertices outside S i after his move. This way, Avoider has to be the next player to play in S i .

Base cases:

Case

Proof of Lemma 11

In this section, we prove that if Avoider has a winning strategy when the legitimate order is respected, she also has one if Enforcer does not respect the order. The main idea of the strategy is to respect the order, and if Enforcer does not respect the order, Avoider has a pairing strategy to force Enforcer to claim a vertex in some pair (x i , x i ), or the odd u j that follows them. By construction, any hyperedge containing a vertex x i or x i also contains the next odd vertex u j in the legitimate order, and this will prove that whenever Enforcer does not respect the order, it benefits Avoider. We now will prove Lemma 11.

Proof. Suppose Avoider has a winning strategy when the legitimate order is respected. We now describe a winning strategy for Avoider in the general case.

While Enforcer respects the legitimate order, Avoider also respects it. Suppose that at some moment of the game, Enforcer does not respect the legitimate order. Denote by y A the vertex he would have played according to the legitimate order, and by y E the vertex he has claimed instead. If y A is a vertex x 2i or x 2i , Avoider pairs it with u 6i+1 and continues as if Enforcer had to play u 6i+2 . If this is the case, consider y A = u 6i+2 . Note that, according to Lemma 5, we can suppose that y E is not a vertex u j with j odd. Indeed, for each vertex u 2i+1 , the hyperedges that contain the previous vertex in the legitimate order (if this vertex is a vertex x j or x j this is true for either of them) also contain u 2i+1 . As any hyperedge containing x 2i or x 2i also contains u 6i+1 which is the next vertex Avoider should have played according to the legitimate order, it benefits her if Enforcer finally claims u 6i+1 instead of x 2i or x 2i according to Lemma 5.

Denote by k the smallest integer such that y E / ∈ S k , and by k the largest integer such that y A ∈ S k . We consider k = 4n + 1 if y E ∈ S 4n , with S 4n+1 = ∅. Note that all the vertices outside S k have already been played or are paired, and that S k \ S k is then the set of vertices perturbed by the move of Enforcer. As all the sets S i have an odd number of vertices, we know that the number of remaining vertices outside S k is odd, as an even number of moves have been played in it. By assumption, Avoider was following a winning strategy for the legitimate order. She can then consider an arbitrary sequence of moves for Enforcer following the legitimate order and her answers according to her strategy until all the vertices in S k \ S k are played. According to these moves, we will denote by x E j the vertex among (x j , x j ) claimed by Enforcer and by x A j the vertex played by Avoider.

Avoider claims y A , the vertex that Enforcer should have claimed according to the legitimate order, and will consider one strategy in S k and another one outside S k :

In H \S k , she plays according to a pairing strategy, that is presented in the next paragraph.

In S k , Avoider considers the strategy she would have played if all the vertices outside S k were played according to the legitimate order, with the vertices x E j claimed by Enforcer and the vertices x A j claimed by Avoider.

The pairing we define is the following one:

(u 6i-4 , x A 2i-1 ), (u 6i-3 , u 6i-6 ), (x E 2i-1 , u 6i-1 ), (u 6i-2 , x A 2i ), (u 6i+1 , x E 2i
). This pairing concerns all the vertices that have to be played after y A in the legitimate order that are not in S k , and we consider only pairs containing at least one vertex outside S k . Note that, by construction, exactly one vertex of this pairing is already played, and exactly one paired with a vertex in S k . Therefore, to make the pairing contain only vertices not played and outside S k , some modifications are done. These modifications are presented in Figure 1. By applying Lemma 6, Avoider can ensure that Enforcer plays at least one in each of these pairs.

yA changes u6i-4 u6i-3 ←→ x A 2i-1 x2i-1 or x2i-1 x * 2i-1 ←→ u6i-1 u6i-2 u6i-1 ←→ x A 2i u6i u6i+3 ←→ x A 2i yE changes u6i-4 no changes x2i-1 or x2i-1 x * 2i-1 ←→ u6i-4 u6i-2 no changes u6i no changes x2i or x2i x * 2i ←→ u6i+1, u6i-2 ←→ u6i
Figure 1 Changes of the matching. x * j refers to the variable in {x k , x k } that has not been played, arrows represent new pairs of vertices in the matching.

Claim 14. The pairing strategy ensures that Enforcer plays at least once in each hyperedge

A i , B i or C i containing all their vertices in S k and at least one outside S k .

Proof. First, if the hyperedge contains no vertex whose pairing has been modified because of their belonging to y A or y E , it contains two paired vertices. We show in bold text the paired vertices:

A 2i = (x A 2i , x E 2i , u 6i+1 , u 6i+3 ) C A 6i = (u 6i , u 6i+1 , u 6i+3 , x A 2i ) C E 6i = (u 6i , u 6i+1 , u 6i+3 , x E 2i ) C A 6i-2 = (u 6i-2 , u 6i-1 , u 6i+1 , x A 2i ) C E 6i-2 = (u 6i-2 , u 6i-1 , u 6i+1 , x E 2i ) B 2i-1 = (x A 2i-1 , x E 2i-1 , u 6i-1 ) C A 6i-4 = (u 6i-4 , u 6i-3 , u 6i-1 , x A 2i-1 ) C E 6i-4 = (u 6i-4 , u 6i-3 , u 6i-1 , x E 2i-1 )
For the first hyperedges of the matching, there are two paired vertices.

Recall first that if Enforcer was supposed to play in {x 2i , x 2i }, Avoider pairs this vertex with u 6i+1 and considers y A = u 6i+2 . The only one hyperedge among the A i , B i and C i that was concerned with this change is A 2i , in which two vertices are now paired. In any other case, the following vertices are paired:

If y A = u 6i-4 , only the hyperedges C E 6i-4 and C A 6i-4 are concerned by the changes. In the former x E 2i-1 is paired with u 6i-1 , in the latter x A 2i-1 is paired with u 6i-3 .

If y A ∈ {x 2i-1 , x 2i-1 }, the only hyperedges concerned by the change is B 2i-1 . In it, the other vertex in {x 2i-1 , x 2i-1 } is paired with u 6i-1

If y A = u 6i-2 , only the hyperedges C E 6i-2 and C A 6i-2 are concerned by the changes. In the former x E 2i is paired with u 6i+1 , in the latter x A 2i is paired with u 6i-1 .

If y A = u 6i , only the hyperedges C E 6i and C A 6i are concerned by the changes. In the former

x E 2i is paired with u 6i+1 , in the latter x A 2i is paired with u 6i+3 .

For the last hyperedges that contain vertices of the matching, the following happens:

If If y E = x 2i or x 2i , the pairing stops at u 6i+1 . The three hyperedges that contain vertices inside S k and outside S k are C + 6i , C - 6i and A 2i . As the second vertex in {x 2i , x 2i } is paired with u 6i+1 , either Enforcer has claimed both x 2i and x 2i , and any of these three hyperedges contains at least one of them; or Enforcer has claimed u 6i+1 which is in these three hyperedges.

y E = u 6i-4 ,
If the pairing stops because it goes until the end (i.e. k = 4n + 1), one vertex is not paired. According to Lemma 6, as Enforcer plays the last move in H, Avoider can force him to play it and still play once in each pair of the pairing.

Finally, in any hyperedge A i , B i or C i containing at least one vertex of the matching, Enforcer has played at least one vertex. Now, we can prove that the strategy we defined for Avoider is a winning strategy. In all the hyperedges A i , B i or C i , Enforcer played at least once. Indeed, if Enforcer has respected the order until he plays in one of these hyperedges, there is nothing to do. Otherwise, by Claim 14, Avoider can force Enforcer to play in it as this hyperedge is considered in a set of hyperedges in which Enforcer has not respected the order, and thus contains two paired vertices.

In the hyperedges D j , as the strategy in the legitimate order is a winning strategy, it forces at least one vertex x i or x i to be claimed by Enforcer in D j (since all the vertices u k of odd indices are played by Avoider in the legitimate order). Then, by construction, if when this vertex has to be claimed the order was respected, Enforcer has played it. If the order was not respected, then Avoider has paired this vertex with the next vertex u k of odd index, forcing Enforcer to play one of them. In both cases, Enforcer has played in D j .

Uniform hypergraphs and applications

The construction provided in Section 3.1 provided a hypergraph in which any hyperedge have size at most six. We prove here that the PSPACE-hardness can be generalized to uniform hypergraphs.

From 6-hypergraphs to 6-uniform hypergraphs

A hypergraph H = (V, E) is a k-hypergraph if
Proof. Let H = (V, E) be a k-hypergraph. Let m = min e∈E |e|.
We define H = (V , E ) as follows. We start from V = V . We add two vertices {a 1 , a 2 } in V . For each hyperedge e ∈ E, we add hyperedges in E as follows:

If |e| > m, we add a copy of e in E .

If |e| = m, we add two hyperedges e 1 = e ∪ {a 1 } and e 2 = e ∪ {a 2 } in E .

We have

|V | = |V | + 2, |E | ≤ 2|E| and min e∈E |e| = m + 1.
Now, if Avoider (Enforcer resp.) had a winning strategy S in E, we can define a strategy

S in E as follows:

If the opponent plays a vertex in V , or if it is the first move of the player, play as in S.

If the opponent plays a vertex in {a 1 , a 2 }, or if there is no vertex in V available, play an available vertex in {a 1 , a 2 }.

Following this strategy, Avoider (Enforcer resp.) has played exactly the same vertices in H as he (she resp.) would have played in H according to S with, in addition, exactly one of

{a 1 , a 2 }.
Therefore, if Avoider had a winning strategy in H, then for each e ∈ E, there exists one vertex v ∈ e, that Enforcer has played. Let e ∈ E be a hyperedge. If e is a copy of some hyperedge e ∈ E, then Enforcer has played in it, as he would have played in e according to S.

If e is a hyperedge e 1 or e 2 created from a hyperedge e ∈ E, as Enforcer would have played in e according to S, he has played the same vertex in e .

If Enforcer had a winning strategy in H, following this strategy, there exists a hyperedge Then, she has claimed a 1 and all the vertices of e, so she has filled up the edge e 1 . Therefore, this strategy is a winning strategy for Enforcer.

Avoider-Avoider games

We prove Corollary 4, i.e. that Avoider-Avoider games are PSPACE-complete, even restricted to 7-uniform hypergraphs.

Proof. Consider the construction provided in the proof of Corollary 16. Consider H the hypergraph obtained by adding a vertex v 0 in H and adding it in all the hyperedges of H.

Note that, as any hyperedge of H has size six, any hyperedge of H have size exactly seven.

According to Lemma 5 (note that the result also apply to Avoider-Avoider games), both players have an optimal strategy in which v 0 will be played last, and as the graph has an odd number of vertices, the first player will play it. has played all the v j s adjacent to them. As Anti-Staller has played one of them, and all its neighbors, this vertex is not dominated. Therefore, Anti-Dominator has won.

In Figure 2 we provide an example of reduction. Note that the construction provided is exactly the same as the one used to prove the PSPACE-completeness in Maker-Breaker in [START_REF] Duchene | Maker-Breaker domination game[END_REF].

v 1 v 2 v 3 v 4 v 1 A v 2 A v 1 B v 2 B v 1 C v 2 C u 1 u 2 u 3 u 4 A B C Figure 2
Reduction from Avoider-Enforcer game to Avoider-Enforcer domination game.

Remark 19. Up to add all the edges between the v i s, the game is still PSPACE-complete on split graphs.

A.2 Avoider-Enforcer vertex H-Game

The vertex H-Game has been introduced by Kronenberg, Mond and Naor in [START_REF] Kronenberg | h-games played on vertex sets of random graphs[END_REF] We first need to define some graphs and operations that will be helpful to describe the graphs of this section:

We will denote by I k the graph being an independent set of size k, i.e. containing k vertices and no edge.

If G and H are two graphs, we denote by G H their join, i.e. if G = (V G , E G ) and

H = (V H , E H ), we have G H = (V, E) with V = V G ∪ V H and E = E G ∪ E H ∪ {(v G , v H )|v G ∈ V G , v H ∈ V H }.
If G and H are two graphs, we denote by G H their strong product, i.e

. if G = (V G , E G ) and H = (V H , E H ), we have G H = (V, E) with V = {x u,v |u ∈ V G , v ∈ V H } and E = {(x u1,v1 , x u2,v2 )| (u 1 = u 2 or (u 1 , u 2 ) ∈ E G ) and (v 1 = v 2 or (v 1 , v 2 ) ∈ E H )}.
Remark that for any graph G, G P 2 (where P 2 design the path of length 2) is obtained by taking two copies of G and connecting each vertex to its copy and its copy's neighbors.

We prove here that determining the winner of the Avoider- Let H = (V , E ) be a 6-uniform hypergraph. Let H 0 be the strong product H 0 P 2 .

We build G = (V, E) an instance of the Avoider-Enforcer vertex H-Game as follows:

Step 1: For any vertex v i ∈ V , we add a vertex v i ∈ V .

Step 2: For any hyperedge C ∈ E , we add 2(k -6) vertices v C 1 , . . . , v C 2(k-6) (note that if k = 6, no vertex is added during this step).

Step As there are no edges between the v i s, they must all be on the same side of the join, and therefore, they are all connected to a same vertex. By construction, this is only the case if these six vertices are in a same hyperedge of H which contradicts that S was a winning strategy for Avoider in H , as these six vertices would then form a hyperedge.

Suppose now that H 0 has no edges and has k ≥ 6 vertices.

This means that H can be written Proof. Let S be a winning strategy for Enforcer in H . We consider a strategy S for Bob in G as follows:

I k I k for k, k ≥ 6 (note
If Alice claims a vertex v i , he answers with the vertex v j that corresponds to the vertex v j that Enforcer would have claimed in response to v i in S .

In H C 0 , as it is a strong product H 0 P 2 , Bob considers the pairing between any vertex and its copy in the strong product. If Alice plays in one pair of the pairing, he plays the second vertex of the pair.

For any edge C ∈ H , Bob pairs the vertices v C j for 1 ≤ j ≤ 2k -6. If Alice claims one of them, he claims one of them too.

If at a certain moment of the game, it is Bob's turn and the remaining vertices are all in some H C 0 or vertices v C j s, he applies the pairing strategy, so that Alice plays once in any pair of the matching by Lemma 6.

Consider the graph at the end of the game. As S was a winning strategy for Enforcer in

e

  ∈ E in which Avoider has claimed all the vertices. If |e| ≥ m + 1, Avoider has also played all the vertices of e ∈ E , so Enforcer has won. If |e| = m, as the strategy S forces Avoider to play at least one of {a 1 , a 2 }, suppose without loss of generality that she has claimed a 1 .

Finally, H has the same outcome as H and min e∈E |e| = m + 1 . 16 .

 116 Corollary Avoider-Enforcer is PSPACE-complete even restricted to 6-uniform hypergraphs Proof. The construction provided in the proof of Theorem 2 builds a 6-hypergraphs in which all hyperedges have size at least two. Therefore, by applying Lemma 15 four times, with m = 2, 3, 4, 5, we obtain a hypergraph having at most eight more vertices and eight times more hyperedges. Thus, this construction is still polynomial and the hypergraph obtained is 6-uniform.

  that H is a complete bipartite graph). Once again, consider two vertices v C and v C for C = C in H 1 . As they cannot be adjacent, they must be both in I k or both in I k . Thus, v C and v C have min(k, k ) ≥ 6 common neighbors. This implies that, if C = C , at least one of their common neighbor is not a vertex v i created during Step 1, otherwise Alice would have played six vertices in the same hyperedge of H . This is not possible by construction. So once again,H 1 cannot contain v C and v C created from different hyperedges C and C in H . Now, ifAlice has played all the vertices of H 1 , by construction as |H 1 | = k + k , and as her pairing strategy ensures her to play k -6 vertices created during step 2 and k created during step 3, necessarily, she has played six vertices v i creating during step 1. As there are no edges between these six vertices, they must all be in the same independent set I k or I k . Thus, they have a common neighbor. This common neighbor must then be a vertex v C creating during step 3 as only them are connected to the v i s. Finally, these six vertices corresponds to six vertices v i s that are in the same hyperedge C of H . Once again, this contradicts the fact that S was a winning strategy for Avoider in H . Claim 23. If Enforcer has a winning strategy S in H , Bob has a winning strategy in G.

  Alice has a strategy which forces Bob to claim at least one vertex in each pair (a i , b i ).

	6. Let H = (V, E) be a hypergraph. Suppose that Alice plays last in H, i.e. if
	the game is played until all the vertices have been claimed, Alice will claim the last one. Let
	n
	(a 1 , b 1 ), . . . , (a n , b n ) be pairwise disjoint pairs of vertices, and let v ∈	{a i , b i }.
	i=1

  Avoider has claimed x i and Enforcer has claimed x i F alse if Avoider has claimed x i and Enforcer has claimed x i Proof. Consider a game played on H for which both Avoider and Enforcer respected the legitimate order through the whole game. Claim 12. Avoider won the game on H if and only if the formula ψ is satisfied by the underlying valuation of the X i s.Proof. Since the legitimate order is respected, Enforcer claimed all the vertices u 2i and thus played at least once in all the hyperedges C + 2i and C - 2i . Moreover, for each pair of variables (x i , x i ), Enforcer claimed one of the vertices of the pair, and so he has claimed at least one vertex in all the hyperedges A i and B i . Thus, the only hyperedges that could possibly be fully played by Avoider are the hyperedges D j .

	We now prove Lemma 9

Since, in the legitimate order, Avoider claimed all the vertices u 2i+1 , a hyperedge D j corresponding to a clause F j is fully played by Avoider if and only if she played on all the vertices x(l j k

  i = 4n: If Avoider plays first is S 4n , by pairing the two other vertices in S 4n , by using Lemma 6, Enforcer can force Avoider to play another vertex in S At least one of {u 6k , x 2k , x 2k } is available. Enforcer claims it. Avoider has to claim the third vertex in this quadruple, otherwise, she plays first in S i+1 and loses by induction, and necessarily one of the three vertices she has claimed is u 6k+1 . Enforcer claims u 6k+2 .Avoider either plays first in S i+2 and loses by induction hypothesis, or claims u 6k+3 . At this moment, Avoider has played on the vertices u 6k+1 and u 6k+3 , and two of the vertices of {u 6k , x 2k , x 2k }. So she has completed one of the hyperedgesC + 6k = (u 6k , u 6k+1 , u 6k+3 , x 2k ), C - 6k = (u 6k , u 6k+1 , u 6k+3 , x 2k ) or A 2k = (x 2k , x 2k , u 6k+1 , u 6k+3 ). Case i =4k -1: Avoider has claimed u 6k-2 and u 6k-1 . Enforcer claims u 6k . Avoider has to play on vertex in {x 2k , x 2k , u 6k+1 }, (otherwise she plays first in S i+2 and loses by induction). Enforcer claims either x 2k or x 2k , as at least one of them is available. If Avoider plays a vertex in S i+2 she loses by induction. So she has to play the last vertex available in S i \ S i+1 . With this strategy, Avoider has necessarily claimed u 6k+1 and one of x 2k and x Case i = 4k -2: Avoider has claimed x 2k-1 and x 2k-1 . Enforcer claims u 6k-2 . Either Avoider plays first in S i+2 and loses by induction, or she claims u 6k-1 , the last available vertex in S i+1 and loses by having played all the vertices in B 2k-1 = (x 2k-1 , x 2k-1 , u 6k-1 ). Case i = 4k -3: Avoider has claimed u 6k-4 and u 6k-3 . Enforcer claims x 2k-1 . Avoider has to claim x 2k-1 , otherwise she plays first in S i+2 and loses by induction. Then Enforcer claims u 6k-2 . If Avoider plays in S i+3 she loses by induction. The last vertex available in S i \ S i+3 is u 6k-1 , and if Avoider claims it, she loses by playing all the vertices Avoider has to play in a set S i in which Enforcer has already played. Therefore, she has to respect the order of the moves. The only moment when she can change this order is by claiming u 6k+1 instead of one of the vertices x 2k , x 2k . But if she does so, Enforcer can claim one of them, for instance x 2k , and Avoider will be forced to claim x 2k . If this happens, everything happens as if Avoider has claimed x 2k first and u 6k+1 after. Since these moves could have occurred in the legitimate order, the strategy can then continue as if the order has been respected.

	C -6k-4 = (u 6k-4 , u 6k-3 , u 6k-1 , x 2k-1 ).
	By applying this induction, at any moment of the game, if Avoider plays first in a set S i ,
	she looses.
	Finally, if Enforcer has played according to the legitimate order, at any moment of the
	game,

4n . Hence, as (u 6n , x 2n ), (u 6n , x 2n ) and (x 2n , x 2n ) are three hyperedges, Avoider will claim the two vertices of one of them and thus lose.

Case i = 4n -1: As shown previously, Enforcer has a strategy such that Avoider is the next player to play in S 4n-1 . If Avoider has played at least one of her two first moves in S 4n , she has lost by the case i = 4n. Otherwise, she has claimed exactly u 6n-2 and u 6n-1 . In this case, Enforcer claims u 6n and pairs x 2n and x 2n and by Lemma 6 he forces Avoider to claim all the vertices of C + 6n-2 or C - 6n-2 .

Induction steps: Suppose that the first time Avoider does not respect the order of the move, she plays in a set S i for i ≤ 4n -2. If the second move of Avoider in S i is in S i+1 , Enforcer wins by induction hypothesis. Thus, we can suppose that Avoider has claimed two vertices in S i \ S i+1 . Moreover, as Enforcer has arbitrarily paired the vertices outside S i , we describe here the strategy in S i , and Enforcer plays according to the pairing outside S i .

This strategy ensures that the moves in S i alternate between both players.

Case i = 4k: Avoider has played twice in {u 6k , x 2k , x 2k , u 6k+1 }. 2k . Thus, she has played all the vertices of either

C + 6k-2 = (u 6k-2 , u 6k-1 , u 6k+1 , x 2k ) or C - 6k-2 = (u 6k-2 , u 6k-1 , u 6k+1 , x 2k ).

To conclude, if Enforcer has a winning strategy when the legitimate order is respected, Enforcer has a winning strategy in H even without this restriction.

  the pairing stops at u 6i-3 . The only two hyperedges that contain at least one vertex in S k and one vertex outside S k are C + 6i-4 and C - 6i-4 , in which Enforcer has claimed y E .Ify E = x 2i-1 or x 2i-1 ,the pairing stops after the second vertex in {x 2i-1 , x 2i-1 }. The only one hyperedge containing at least one vertex in S k and one outside S k is B 2i-1 , in which Enforcer has already claimed y E .

If y E = u 6i-2 , the pairing stops at u 6i-1 . The only two hyperedges that contain at least one vertex in S k and one vertex outside S k are C + 6i-2 and C - 6i-2 , in which Enforcer has claimed y E .

If y E = u 6i , the pairing stops at u 6i+1 . The three hyperedges that contain both vertices in S k and vertices outside S k are C + 6i , C - 6i and A 2i . In C + 6i , C - 6i , Enforcer has claimed y E , and in A 2i , Enforcer will play one of x E 2i or u 6i+1 as these two vertices are paired together.

  any hyperedge e ∈ E has size at most k. It is said to be k-uniform if any hyperedge e ∈ E has size exactly k.

	Lemma 15. Let H = (V, E) be a k-hypergraph. Let m = min e∈E	|e|. If m < k, there exists
	a k-hypergraph H = (V , E ) where min e∈E	|e| = m + 1, having |E | ≤ 2|E| and |V | ≤ |V | + 2
	such that Avoider has a winning strategy in the Avoider-Enforcer game on H if and only if
	she has one in H .

  Therefore, the second player cannot fill up a hyperedge and plays as Enforcer would in the Avoider-Enforcer game. By applying the same strategy as in Avoider-Enforcer, if Avoider wins in Avoider-Enforcer, the game ends by a draw, otherwise the second player wins. If a player plays a vertex v k C for k ∈ {1, 2}, he claims the vertex v k C for k = k ∈ {1, 2}. Now if Avoider had a winning strategy in H, by applying the strategy S , for any vertex v i C , Anti-Staller has not played all the v j s adjacent to it. Therefore, Anti-Dominator has claimed one of them and all the v i C s are dominated. Moreover, all the vertex u j s are in at least one edge C of H, and thus v j is dominated by Anti-Dominator, as she has played one

	Avoidance games are PSPACE-Complete
	of (v 1 C , v 2 C ). Finally, Anti-Dominator has dominated the graph and Anti-Staller has won.
	Reciprocally, if Enforcer had a winning strategy in H, by applying the strategy S ,
	Anti-Dominator knows that there exists a pair of vertices (v 1 C , v 2 C ), such that Anti-Staller

  on random graphs. It is presented in several conventions, but we will focus here on the Avoider-Enforcer one. The game is played as follows:Let H be a graph. Avoider and Enforcer play on the vertex set of another graph G.Alternately, Avoider and Enforcer claim an unclaimed vertex of G. Avoider wins if the set of vertices she has claimed do not contain H as a subgraph (not necessarily induced). Otherwise,

	Enforcer wins.
	Problem 20. Avoider-Enforcer vertex H-Game
	Input: A graph G
	Output: True if and only if Avoider wins the Avoider-Enforcer vertex H-Game played on G.

  Enforcer vertex H-Game is a PSPACE-complete problem for several graphs H . Let H 0 be a graph containing at least one edge or at least 6 vertices, and let k ≥ 6. Consider H = I k H 0 . The Avoider-Enforcer vertex H-game problem is PSPACE-complete.

	Theorem 21.

Note that complete bipartite graphs K n,m , with n, m ≥ 6, are of this type. Indeed,

K n,m = I k H 0 for H 0 = I m and k = n.

Proof. First, the Avoider-Enforcer vertex H-game is in PSPACE. Indeed, as it is a positional game, if G = (V, E) is a graph, the game ends after at most |V | moves. After that, determining whether a graph H is a subgraph of a graph G can be done in polynomial space.

We do our reduction from Avoider-Enforcer on 6-uniform hypergraphs (proven to be PSPACE-complete in

Corollary 16)

. Let H 0 be a graph containing at least one edge or at least 6 vertices, and let k ≥ 6. Let H = I k H 0 . To avoid confusion while describing the strategies in the two games, we will call the players of the Avoider-Enforcer vertex H-Game Alice and Bob, with Alice avoiding creating a subgraph H and Bob forcing her to create one.

  She starts by claiming the vertex v i , corresponding to the vertex v i that Avoider would have claimed in H according to S . If Bob claims a vertex v i , she answers with the vertex v j corresponding to the vertex v j that Avoider would have claimed by S in H if Enforcer has claimed v i . At the end of the game, by the matching strategy, for each hyperedge C in H , Alice will have played exactly a copy of H 0 in each H C 0 , exactly k -6 vertices among the v C j for 1 ≤ j ≤ 2(k -6), and the vertices v i corresponding to the v i that Avoider would have played according to S in H . Now, consider any copy H 1 of H in G. Suppose that Alice has played all the vertices of H 1 . Suppose that H 0 has at least one edge. We first prove that H 1 cannot contain two vertices v C and v C for C = C that have been created by the Steps 2 or Step 3 of our construction. Suppose it does. Consider a decomposition of H 1 = I k H 1 0 . By construction, the v C s and the v C s are not adjacent. Therefore, as these two components are fully connected one to the other, they must either be both in I k or both in H 1 0 . Let e = (u 1 , u 2 ) be an edge of H 1 0 . v C and v C cannot be both adjacent to u 1 , otherwise, by construction, we would have C = C . Therefore, as only vertices created during Step 1 can be adjacent to both v C and v C , any vertex in I k must be a vertex v i . Which is not possible otherwise, Alice would have play k ≥ 6 vertices v i adjacent to a same v C , which means that, according to S she would have played k ≥ 6 vertices in the same hyperedge in H , which contradicts the fact that S was a winning strategy for Avoider in H . Now, as all the vertices of H 1 are either v i s or were created by considering the same hyperedge C, and |H 1 | = |H 0 | + k, by the pairing, we know that exactly 6 of them are v i s.

	In H C 0 , as it is a strong product H 0 P 2 , Alice considers the pairing between any vertex
	of H 0 and its copy in the strong product. If Bob plays in one pair of this pairing, she
	claims the second vertex of this pair.
	For any hyperedge C in H , Alice considers the set of vertices v C

3:

For any hyperedge C ∈ E , we add a copy H C 0 of the graph H 0 in G, and we connect any vertex of H C 0 to all the vertices v i such that v i ∈ C and to all the vertices v C j for 1 ≤ j ≤ 2k -6.

Claim 22. If Avoider has a winning strategy in H , Alice has a winning strategy in G.

Proof. Suppose Avoider has a winning strategy S in H . We define Alice's strategy S in G as follows: j for 1 ≤ j ≤ 2k -6. If

Bob claims one of them, she also claims one. As there is an even number of them, this is always possible.

Avoidance games are PSPACE-Complete

  H , there exists a hyperedge C ∈ H in which Avoider has claimed the six vertices. Up to a renaming of the vertices, denote by v 1 , . . . , v 6 be these six vertices. Alice has then claimed v 1 , . . . , v 6 in G. According to the pairing strategy, Bob knows that Alice will play exactly on k -6 vertices from the v C j , denote them v 7 , . . . , v k , and exactly one copy H 1 of H 0 from the vertices of H C 0 . Now, by construction, the vertices v 1 , . . . v k are a stable set and all the edges exist between any v i (1 ≤ i ≤ k) and any vertex v of H 1 . Thus, the subgraph formed by these vertices, which were all played by Alice, is isomorphic to I k H 0 = H. Thus, Bob has won. Finally, Alice has a winning strategy in the Avoider-Enforcer vertex H-Game played on G if and only if Avoider has one in the Avoider-Enforcer game played on H , and determining the winner of the Avoider-Enforcer vertex H-Game is PSPACE-complete.

Acknowledgements

We want to thank Eric Duchêne, Marianne Fortin, Aline Parreau and the anonymous referees for their help in the writing of this article

Funding Valentin Gledel: supported by the Kempe Foundation Grant No. JCK-2022.1 (Sweden).

Nacim Oijid: supported by the ANR project P-GASE (ANR-21-CE48-0001-01)

A Particular Avoider-Enforcer games

Several games have been proven to be PSPACE-complete in the Maker-Breaker convention, thanks to the proofs of Schaefer or of Rahman and Watson. Due to the similarities between the two conventions, some reductions may be adapted to prove that these games are PSPACEcomplete in the Avoider-Enforcer convention. In particular, we prove in this section that the domination game and the vertex H-Game are PSPACE-complete in Avoider-Enforcer convention.

A.1 Avoider-Enforcer domination game.

The Maker-Breaker domination game was introduced by Duchêne et al. in 2020 [START_REF] Duchene | Maker-Breaker domination game[END_REF] and follows the study of domination games on graphs, which were investigated since 2002 [START_REF] Noga Alon | Game domination number[END_REF][START_REF] Brešar | Domination game and an imagination strategy[END_REF].

In Let H = (V H , E H ) be a hypergraph. Without loss of a generality, we can suppose that each vertex is in at least one hyperedge, otherwise the vertices in no hyperedge will be played first according to Lemma 5, and we can just remove them, up to change the first player to go. We construct the following graph G = (V, E) as follows:

For each vertex u i in V H , we add a vertex v i in V .

For each hyperedge C in E H , we add two vertices

Note that the graph created here is bipartite Suppose Avoider (Enforcer resp.) has a winning strategy S in H. We define a strategy S for Anti-Staller (Anti-Dominator resp.) in G as follows.

If Avoider (Enforcer resp.) plays the first move in H, he claims first a vertex v i such that u i is the first vertex claimed in S.

If the opponent claims a vertex v i , he claims a vertex v j such that u j is the answer to the vertex u i in S.


Frédéric Didier
email: frederic.didier@epfl.ch

Yann Laigle-Chapuy
email: yann.laigle-chapuy@inria.fr

Attacking

Attacking the combination generator

Keywords: Stream cipher, combination generator, Boolean functions, low weight multiples, Walsh transform

come

Introduction

The combination generator is, together with the filter generator, one of the simplest and most analyzed construction of stream ciphers. It uses as an internal state many linear feedback shift registers (LFSRs). We will write m for their total size in bits. These registers are filtered using a n-variable balanced Boolean function f (from F n 2 into F 2 ) to produce the keystream (z t ) t≥0 . The inputs of this function are taken from some bits in the LFSRs internal states. We will write x t for the n-bit vector corresponding to the inputs of f at time t. Notice that we will always write such vector of bits in bold. Our goal here is to find the key (that is the initial state of all the LFSRs) knowing the keystream sequence (z t ) t≥0 and all the components of the combination generator.

The classical way to attack such a system is to use a correlation attack [Sie85] or one of its variants called fast correlation attacks [MS88,CT00,JJ00]. The idea is to exploit the existence of a statistical dependence between the keystream and one of the constituent LFSR. For example, if we write x = (u, v) where u corresponds to the bits taken from the first LFSR, such a dependence exists if for some linear function ℓ,

Pr[f (u, v) = ℓ(u)] = 1/2 .
One can then perform an exhaustive search on the initial state of the first LFSR (or any other targeted LFSR) and try to detect a bias. In order to ensure that there is no such bias (or a really low one) f is usually chosen with a high nonlinearity and a low autocorrelation.

In the fast correlation attacks, one sees the search of the initial state as a decoding problem of the linear code generated by the target LFSR and the linear function ℓ. Then, instead of an exhaustive search, it is possible to avoid examining all possible initializations of the target LFSR by using some efficient error-correcting techniques. Usually the attack becomes faster but requires a larger amount of keystream.

This paper presents a new attack on the combination generator. At first sight, it may not seems that new because we use only classical tools, namely low weight multiples, vectorial correlation and Walsh transform. But in our knowledge, they are used in an original way and we add some interesting insights. Moreover, this attack is not based on any particular weakness of the filtering function like for correlation attacks. Actually, we can even attack a system where we do not know the filtering function used! To simplify our analysis we only assume that f has a good autocorrelation. However choosing a filtering function without this property will open the door to the correlation attacks described above.

The paper is organized as follows. We begin by explaining the attack principle in the next section. Then, in Section 3, we detail the algorithm and the complexity of the different steps involved. We give in Section 4 the actual time complexity of our implementation on an example combination generator. We finally conclude in the last section.

Attack principle

We describe here an attack on the combination generator based on the theorem given at the end of this section. What we actually show is how to find the initial state of some of the LFSR composing the system. This is certainly enough to say that the system is insecure and recovering the rest of the initial state require usually less work. The best method for this task is more dependent on the actual system we are working on and we will give in Section 4 an example of how we can actually do it.

So, suppose we are given a combination generator and we are able to observe a large amount of keystream bits, the z t 's. We denote by x t the input of the filtering function for this observed system at time t, that is we have z t = f (x t ). We split the LFSRs involved into two groups and do an exhaustive search on the initial states of the first LFSRs. For a given value I of this partial initial state, we write y t for the hypothetical first part of the filtering function input at time t. That is, the part we can compute given I. We also need one or more common weight 4 multiples 1 + X t1 + X t2 + X t3 of the feedback polynomials of the LFSRs in the second group. We then compute the ratio P I of times t such that z t + z t+t1 + z t+t2 + z t+t3 = 0 amongst all the t's such that

y t + y t+t1 + y t+t2 + y t+t3 = 0 .
Remark that the number of such time instants at our disposal is directly linked to the amount of keystream we know. Now, how can we distinguish the real partial initial state from the others?

-If I is the actual first part of the initial state, then we know we look only at times t such that x t + x t+t1 + x t+t2 + x t+t3 = 0. This is because we are working with a multiple of the other LFSRs feedback polynomials. Then, it is reasonable to assume that the ratio P I is an estimate of the probability Pr(f (u

1 ) + f (u 2 ) + f (u 3 ) + f (u 4 ) = 0 | i u i = 0).
Here the u i are vectors in F n 2 uniformly distributed amongst the one having the required property. -If I is not the actual first part of the initial state, even in the worst case where only the initial state of one LFSR was not guessed correctly, it is reasonable to assume that the sum x t + x t+t1 + x t+t2 + x t+t3 is different from 0 roughly half of the time. For theses points, we then have an estimate for one of the probabilities Pr(f (u

1 ) + f (u 2 ) + f (u 3 ) + f (u 4 ) = 0 | i u i = u) where u = 0.
Hopefully for us, the two cases are distinguishable thanks to the following result taken almost directly from [Did07] and already present in the work of Sabine Leveiller [Lev04].

Theorem 1. Let f be a n-variable balanced Boolean function, and let u 1 , u 2 , u 3 , u 4 be 4 uniformly distributed n bits vector such that u 1 + u 2 + u 3 + u 4 = u. Let P u := Pr(f (u 1 ) + f (u 2 ) + f (u 3 ) + f (u 4 ) = 0), then we have

P 0 ≥ 1 2 + 1 2 n+1 and min u =0 (P 0 -P u ) ≥ 1 2 n+1 1 - ∆ f 2 n 2
where ∆ f is the maximum of the autocorrelation coefficients of f and is usually small compared to 2 n . Proof. see Appendix.

We will assume in the rest of this paper that the filtering function has a good autocorrelation property which result in a difference between these probabilities of 1 2 n+1 . This is a reasonable hypothesis because it is the case for the function usually used in this settings [GK03]. In particular, it is a needed property to resist against correlation attacks.

We describe here our attack in details and hence need some more notations. Since we split the LFSRs in two groups, we will write m = m 1 + m 2 where m 1 is the total size in bits of the LFSRs in the first group. That is the one we do an exhaustive search on. Similarly, we write n = n 1 + n 2 for the inputs bit of the filtering function f . Remark that in practice, n is kept small compared to m for efficiency issues. Our result is summarized in this theorem:

Theorem 2. Our attack recovers m 1 bits of the initial states in complexity

O(m 1 2 n1 2 m1 ). It requires O(2 m 2 3
+ m 1 2 2n+n1+1 ) consecutive bits of keystream and a memory of O(2 m1 ). If the memory requirement is too big, some tradeoff exists until a complexity of O(m 1 2 2n+n1 2 m1 ) and a memory of O(m 1 2 2n+n1 ). This attack also require a precomputation phase of complexity and memory in O(2 m 2 3 ).

Computing weight 4 multiples

We need to compute one or a few weight 4 common multiples of the second group of LFSRs. We show here that this precomputation phase can be dealt with a complexity and memory around O(2 m 2 3 ). What we need is only a few multiple of degree as small as possible. If we look at LFSRs of total size m 2 , it is well known that the expected number of weight 4 multiples of degree D is heuristically approximated by 1 2 m 2 D 3 6 considering that for D large enough the values of the polynomials of weight 4 and degree at most D are uniformly distributed.

There are many algorithms to compute low weight multiples whose complexity depends on the parameters D which in our case is around 2 m 2 3 . One can use the algorithm in [CJM02] but for weight 4 multiples, the most efficient is the one of [DLC07]. It's especially adapted here, as we need to find a simultanous multiple of many polynomials.

Its complexity is in O(D) times the complexity to compute discrete logarithms in the multiplicative group

F * 2 l 1 ו • •×F * 2 l k
where the l i are the respective length of each LFSR. This task is particularly easy since using Pohlig-Hellman algorithm it can be splited into k discrete logarithms computation in each of the finite field multiplicative groups involved.

Amount of keystream needed

We prove here the following lemma Lemma 1. We need to consider around N := m 1 2 2n+n1+1 degree 4 equations to identify the correct partial initial state. This translates to O(2

m 2 3 + m 1 2 2n+n1+1 ) consecutive keystream bits needed.
Given the results in Section 2, mainly Theorem 1, we need to distinguish in the worst case between two binomial distributions, one of parameter 1 2 + 1 2 n+1

and one of parameter at most 1 2 + 1 2 n+2 . However, for most of the wrong partial initial states, we will just observe a law of parameter 1 2 , so the bias we need to detect is in practice close to 1 2 n+1 . A classical results from statistics tell us that using S samples, we have an error probability of roughly 2 -S 2 2n+1 . We thus need at least 2 2n+1 samples to be able to distinguish the two distributions. But this is not sufficient in our case. Recall that we are doing an exhaustive search on 2 m1 possible states, so the average number of wrong states passing the statistical test will be 2 m1 2 -S 2 2n+1 . We thus need a number of samples equal to at least m 1 2 2n+1 to obtain only a few possible candidates for the real initial states. Notice that with this number of samples, the probability to miss the initial states is of O(2 -m1 ) which is really small.

What is the amount of keystream needed to get that many samples? For one sample, we will need to consider 2 n1 degree 4 equations since this is the expected number for y t + y t+t1 + y t+t2 + y t+t3 to be equal to 0. The average degree of the lowest weight 4 multiples is O(2 m 2 3 ) (see previous subsection). By shifting this multiple x times, we get x degree 4 equation for O(2 m 2 3 + x) consecutive keystream bits. Hence, the required amount of keystream is O(2

m 2 3 + m 1 2 2n+n1+1 ).
We assumed here that we use only one weight 4 multiples. If we use many, it is actually possible to need less keystream at the expense of more precomputation. This gain is difficult to analyze as it really depend on the used LFSRs, but may definitely be useful in practice. However, it will not change the overall asymptotic keystream needed.

Performing the attack efficiently

We show in this subsection how to find the initial states in O(m 1 2 n1 2 m1 ) instead of O(N 2 m1 ) with a straightforward implementation. Notice that this is a huge gain since in our case m 1 2 n1 ≪ N . On the memory side, we need 2 m1 integer in the second case compared to N bits in the first one. If this is a problem, we can actually trade memory for time and be anywhere between those two algorithms.

In order to perform our attack, we have to compute many quantities involving time positions of the form (t, t+t 2 , t+t 2 , t+t 3 ). Since we may use many multiples, let just assign an index i to such 4-tuple. We will then write z(i) for the sum of the z t for the 4 time positions number i and y(i) in the same way.

Computing the probability estimate for a given partial initial state is roughly the same as computing the number of indices i such that y(i) = 0 and z(i) = 0. Actually to get the true probability, we also need to know how many indices are such that y(i) = 0 and z(i) = 1 but this will not change our discussion or the final complexity. So let restrict ourselves on the N ′ indices i such that z(i) = 0.

If we do this independently for each of the 2 m1 partial initial states, the complexity is then in N ′ 2 m1 which is pretty large. In order to improve on this complexity, let us start by assuming that out of the m 1 bits, only one is used as an input for the filtering function f , that is we assume the y t to be scalar. Remark now that any linear combination of bits from the internal states of some LFSRs can be expressed as a linear expression of the initial state of theses LFSRs. This is the case for the y(i). We can then define a binary linear code of generator matrix G of size m 1 × N ′ such that for a given partial initial state u the i-th element of uG is precisely y(i). The number we try to compute for a given initial state u is then just N ′ minus the Hamming weight of uG.

Is there a way to compute the Hamming weight of each codeword in a code of length N ′ and dimension m 1 faster than 2 m1 N ′ ? The answer is yes, thanks to the Walsh transform we can do it in O(m 1 2 m1 ) which in our case is a lot better since m 1 ≪ N ′ . The Walsh transform w of a function w :

F m1 2 → Z can be computed in O(m 1 2 m1
) and is such that

w(u) = v w(v)(-1) v.u .
If w(v) is equal to the number of columns in G equal to v, w(u) is exactly twice the Hamming weight of uG minus N .

Now, what to do when the y t are not scalar ? we can use this nice formula :

#{i, y(i) = 0} = y∈F n 1 2 #{i, y(i).y = 0} -2 n1-1 2 n1 .
This simply comes from the fact that when y(i) is 0 it contributes to 2 n1 in the sum whereas any other y(i) contributes only 2 n1-1 . Each cardinality in the sum can be computed using a Walsh transform, but since Walsh transform is linear, we better compute directly the Walsh transform of the function

w(v) = #{(i, y), y.(G 1 (i), . . . , G n1 (i)) = v}
where G j (i) is the i-th columns of the matrix of the linear code corresponding to the input bit j of the filtering function.

Finally, the time-memory tradeoff mentioned in the first paragraph directly follows from a time memory tradeoff in the implementation of the Walsh transform.

Attack Example

We give in this section an example of how to use our result to mount an attack on a given combination generator.

The following timings were obtained on an Intel Core2 Quad CPU Q9550 at 2.83GHz, using only one core and no more than 2GB of memory. We used a combination generator based on three LFSRs of size 29, 31 and 37 respectively. The feedback polynomials are dense in order not to have artificially easy to find low weight multiples. The filtering function f is a 9-variable Boolean function, with 3 inputs from each LFSR. It was chosen to be still balanced even if we fixed Table 2. Comparison of the different parts of the online attacks the input bits from any of the constituent LFSR in order to avoid traditional correlation attack , i.e. the function is 3-resilient.

In the attack referred below as Attack 1, we retrieve the initialization of the LFSR of size 29, 31 and 37 in this order. We thus have in a first step the following parameters :

m 1 = 29; m 2 = 31 + 37 = 68; n 1 = 3; n 2 = 6.
As stated in Lemma 1, we thus need to consider approximately N = 2 26.86 multiples of P 31 × P 37 of weight 4. The maximum degree needed is slightly less than 2 25 which implies we need 3MB of keystream. Using the approach of [DLC07] for finding low weight multiples of degree less than 2 25 , the precomputation took around 13 minutes. The online time to recover the initial internal state of the first LFSR is only 51s, for a theoretical workload of approximately 2 37 . The internal state of the second LFSR is then recovered in roughly 6 minutes, using only very few keystream because we only need to consider multiples of the last feedback polynomial. Finally, the internal state of the last register is found by a different method almost instantly, because the full knowledge of 6 entries of our Boolean function amongst 9 gives us a lot of information.

In the second version of the attack , we retrieve the initialization of the LFSR of size 37, 29 and 31 in this order. We thus have in a first step the following parameters : m 1 = 37; m 2 = 31 + 29 = 60; n 1 = 3; n 2 = 6. This small difference allows us to have a lower value for m 2 , which implies that we need less keystream to perform the attack. We need to consider approximately N = 2 26.86 multiples of P 31 ×P 29 of weight 4, the precomputation is this time only 3 minutes and the maximum degree needed is approximately 2 23 , corresponding to 985KB. On the contrary, the online time to recover the initial internal state of the first LFSR is much longer. The theoretical workload is approximately 2 42 and our experiment confirms this ratio as it tooks us just more than 6 hours. The timings to recover the two other LFSR is negligible compared to the first one.

In conclusion, the Attack 1 is the best one from a complexity point of view, whereas the Attack 2 minimizes the amount of keystream needed. We summarize the timings for the two different strategies in Tables 1 and2.

Conclusion

We presented in this paper an efficient attack on the combination generator. In particular, if we look at the timings given in Section 4, we are not aware of any other attacks that can break the chosen combination generator that efficiently. Remark however that breaking the combination generator still requires an exponential number of computation. Hence, if the parameters are chosen large enough, such a system can still be secure given the actual knowledge.

An important point is that the presented attack is inherent to the construction and is not based on any particular weakness in the choice of the filtering function or in the constituent LFSRs. As such, it appears that for the same order of internal size the combination generator is a lot less secure than a single large primitive LFSR filtered by a non-linear function. This statement seems true in many ways. With a large LFSR, it is more difficult to compute any low weight multiples, it is more difficult to break the system into smaller components, and the best attacks we know are a lot less efficient.

Table 1 .

 1 Global comparison of the two attacks

		Precomputation Total online time Keystream used
	Attack 1	12min27s		7min01s	3.06MB
	Attack 2	3min02s		6h18min	985KB
		1st LFSR 2nd LFSR 3rd LFSR
		Attack 1	51s	6min10s	0s
		Attack 2 6h17min 1min27s	0s

Acknowledgment

We would like to thank Anne Canteaut and Jean-Pierre Tillich for their help and their useful comments.

⋆ This work is partially funded by CELAR/DGA.


Tuan-Linh Nguyen
email: tuan-linh.nguyen@irt-jules-verne.fr

Yvan Denis

Steven Le Corre

MULTIPHYSICS SIMULATION OF CONSOLIDATION PROCESS OF HIGH THICKNESS THERMOPLASTIC LAMINATE PARTS

Keywords: Simulation, Consolidation, Distortion, Composite, Thermoplastic, High thickness

In this project, we are interested in the manufacturing of high thickness thermoplastic laminate parts. During this consolidation step, induced stresses or deformation may occur, which can lead to the generation of defects such as delamination or shape distortions. An experiment trial and error approach on the manufacturing of such high-performance materials and thick parts is cost prohibitive and time consuming. Thus, this work aims at reducing the process development cost through the multiphysics simulation of the consolidation processes. The multiphysics model proposed here is based on a coupling approach of the transient heat transfer, crystallization kinetics and elastic models at the macroscopic scale. These simulations can allow studying the consolidation problems such as shape distortion (spring-in) at the cooling phase due to the material shrinkage. Optimal process parameters or a customized mold/part design thus can be considered to minimize the induced defects.

Introduction

Nowadays, the aeronautical industry is more and more interested in thermoplastic resin for its capabilities of welding, recycling, corrosion resistance… However, until now, the use of thermoplastic is mostly limited to relative thin parts which are not suitable for structural applications. In this project, we are interested in the manufacturing of high thickness thermoplastic laminate parts. The Automated Fiber Placement (AFP) process is a good candidate which can meet the industrial requirements: robustness, performance, production cost and rate… Nevertheless, it requires a phase of consolidation in an oven or autoclave as the in-situ consolidation is still a challenge, especially for high thickness parts. During this consolidation step, induced stresses or deformation may occur, which can lead to the generation of defects such as delamination or shape distortions. An optimization of the manufacturing strategies (like temperature and pressure cycle) or mold design is required to minimize or avoid these defects. However, an experiment trial and error approach on the manufacturing of such highperformance materials and thick parts is cost prohibitive and time consuming. Beside the thermal and kinetics analysis, mechanical modeling of composite manufacturing processes plays an important role in this case [START_REF] Baran | A review on the mechanical modeling of composite manufacturing processes[END_REF]. Thus, this work aims at reducing the process development cost through the multiphysics simulation of the consolidation process.

Shape distortion problem

Forming processes of high thickness thermoplastic laminate parts

The forming processes used in this project consist of two steps: AFP process and consolidation step. During the AFP step, thermoplastic laminate parts are draped up to 196 plies. The used tapes are made of carbon fiber and high performance semi-crystalline PAEK TP. In the second step, these parts are consolidated in a vacuum oven or in an autoclave with a given pressure/temperature cycle. Figure 1 shows a manufactured "Pylon" (U-shape) part with nearly quasi-isotropic draping scheme. The part is symmetric and the angle between the middle zone and side zones is about 80°.

Spring-in -Shape distortion problem of U-shape (angled) composite laminates

Following the mold release,3D scan measurements have been realized. Figure 2 shows the correlation between the 3D scan and the designed (nominal) geometry of the pylon part. Green color indicates where there is less difference while red/violet color indicate zones of large shape distortion. We can see that shape distortion has been observed mainly in the extremities (free edges) of parts (red/violet color). Indeed, after the consolidation, the part tends to be more bended (closed) and the angle between the middle zone and side zones is reduced. This angle deviation is commonly called "spring-in" angle. In the literature, this spring-in phenomenon of angled composite laminates has been studied in many works, both for thermosetting and thermoplastic matrices [START_REF] Albert | Spring-in and warpage of angled composite laminates[END_REF][START_REF] Salomi | Spring-in angle as molding distortion for thermoplastic matrix composite[END_REF]. This phenomenon leads to the manufacturing of non-conforming parts and thus causes problems in assembly.

An estimation of the angle deviation was derived by Radford [4] which considers both the thermal and chemical shrinkages: where ∆𝜃 and 𝜃 are the angle deviation and the nominal initial angle, ∆𝜃 𝐶𝑇𝐸 and ∆𝜃 𝐶𝑆 are the thermal and crystallization induced angle deviation, 𝛼 𝑙 and 𝛼 𝑡 are the in-plane and throughthickness coefficients of thermal expansion, 𝜑 𝑙 and 𝜑 𝑡 are the in-plane and through-thickness coefficients of crystallization shrinkage. This formula provides a quick estimation of shape distortion. In this case, it overestimates to spring-in angle with respect to 3D scan results. Moreover, it does not consider many process parameters such as: the contact mold/parts, the thickness of part, consolidation cycle, material behavior… A numerical tool and especially finite element (FEM) models are required to be able to predict more precisely the spring-in behavior.

∆𝜃 = ∆𝜃 𝐶𝑇𝐸 + ∆𝜃 𝐶𝑆 = 𝜃 ( (𝛼 𝑙 -𝛼 𝑡 )∆𝑇 1+𝛼 𝑡 ∆𝑇 ) + 𝜃 ( 𝜑 𝑙 -𝜑 𝑡 1+𝜑 𝑡 ) (1)
In what follows, a multiphysics FEM approach will be presented. Furthermore, it is addressed for high thickness laminates.

Multiphysics model: coupled heat transfer, crystallization and mechanical models 3.1 Main modelling assumptions

• This work focuses on the consolidation step after AFP step of the forming processes. It is assumed that the parts before the consolidation step are perfectly draped which means: no gap or overlap of AFP, no delamination between layers and no deviation of fibers orientation. No shape distortion or thickness variation is considered after the AFP step. Moreover, the model is developed to predict the distortion after the mold release step. Further steps such as machining where additional distortion is likely to happen are not considered here.

• As the studied parts present many plies (up to 196 plies), a homogenized macroscopic 3D model is proposed in this work where effective properties are used. Indeed, the draping scheme of AFP process leads to a quasi-isotropic planar orientation. Subsequently, the composite part can be considered as a homogeneous transversely isotropic material (where transverse direction along the thickness direction) in this approach.

Composites Meet Sustainability -Proceedings of the 20 th European Conference on Composite Materials, ECCM20. 26-30 June, 2022, Lausanne, Switzerland

Multiphysics model

The multiphysics model proposed here is thus based on a coupling approach of the transient heat transfer, crystallization kinetics and thermo-elastic models at the macroscopic scale. In a previous study, thermal and thermal-crystallization simulations were carried out to study the influence of thermal contact resistance and mold geometry on thick composite laminates consolidation. The readers can refer to this article [START_REF] Denis | Thick thermoplastic composite laminate consolidation: experimental observations and numerical approaches[END_REF] for the details of thermal and crystallization models. In the present work, by considering the computed temperature and crystallization fields, a coupled mechanical model based on a simple thermo-elastic approach is introduced. This model aims at providing the evolution of shape distortion during the consolidation process and mold release step.

Let us recall here the corresponding numerical modules used for different physical phenomena occurred during the consolidation of thick laminates.

• Heat transfer: heat transfer module was developed in the FreeFem++ library [START_REF] Hecht | New development in freefem++[END_REF].

FreeFem++ makes it possible to properly consider thermal contact resistance (TCR) by simultaneously solving the transient heat transfer both in the mold and in the part, thus introducing a strong coupling between domains. This heat transfer module allows to simulate the temperature gradient (particularly in the thickness direction for high thickness laminate parts).

• Crystallization kinetics: Based on the temperature result, a coupled thermo-kinetics module was also fully developed in the FreeFEM++ library. It consists of using the classical Nakamura kinetics [START_REF] Levy | Robust Numerical Resolution of Nakamura Crystallization Kinetics[END_REF] to simulate the evolution of the crystallization rate.

• Mechanics: The results of temperature and crystallization rate are then transferred to a thermo-elastic model in the Abaqus © (Dassault System) software. A numerical chain has been developed between the FreeFEM++ library and Abaqus. The proposed coupling is an iterative coupling as the data such as meshes, results are transferred at each increment (time step). The impact of thermal and chemical (crystallization) shrinkage is thus updated during the consolidation step.

Figure 3 shows the flow chart of this approach. During the consolidation step, the material evolves between different states: viscous, rubbery and glassy state in function of the temperature and crystallization rate. The material input must be considered with the phase change. Moreover, the material is not isotropic but transversely isotropic. In this work, thermal and crystallization properties were used such as the coefficient of thermal expansion (CTE), specific heat capacity or temperature dependent elastic properties. All of them account for the composite anisotropy, based on the transversely isotropic model.

Figure 3. Flow chart of iterative coupling

The study and results presented below essentially target the cooling phase of the consolidation step. For these simulations, the crystallization peak temperature is considered as the stress-free temperature (SFT) which corresponds to the temperature that the stresses begin to develop. SFT means that above this point, it is assumed that no induced stress is generated as the material is in the viscous state. Thus, the contact of the part/mold is assumed perfect before that temperature. The material is first cooled down from above the resin fusion temperature (Tf). Then the cooling phase consists of a crystallization plateau (Tc) in order to maximize the crystallization rate. This temperature was chosen in function of the cooling rate regarding to the crystallization kinetics. A second plateau at lower temperature is imposed to homogenize the temperature through the part then part is cooled down to ambient temperature (Ta) at a constant rate. A constant pressure is applied on the part. As mentioned, input data for transversely isotropic material are required such as the thermal properties, crystallization kinetics of composites material, the coefficient of thermal expansion (CTE) at glassy and rubbery state, thermal dependent elastic properties. For the mold, isotropic properties are considered. As a transversely isotropic material is considered, Abaqus ORIENT subroutine is used to define the material local coordinate in Abaqus.

Numerical model set-up for the consolidation of U shape (pylon) part

Results and discussions

Figure 6. shows the results of the temperature and crystallization state at the beginning of the crystallization process. In our case, during the cooling phase, the chamber temperature of autoclave decreases. As the part is thick and there is inertia of mold, the mold is cooled more slowly which creates a gradient of temperature through the thickness of the part. It therefore causes a gradient of crystallization rate (α) through the thickness as well. At the end of the cooling step, due to the shrinkages, the part deforms and tends to be more bended. However, it is constrained by the presence of the mold. The part is thus detached a little from its contact with the mold. Figure 7 shows the displacement field of part and mold at the end of consolidation step (view cut at the middle of part). As we can see with a zoom at the corner (Figure 7 right), a contact loss is observed between the part and the mold. The angle deviation happens at the step of mold release. Figure 8 shows the displacement field (U) of the part with respect to the initial position at that moment (after mold release step). Indeed, the spring back is caused by the relaxation of the elastic stress. The value of part displacement is maximum at the extremities of the U-shape part. It is in accordance with the experimental results.

Figure 8. Simulated displacement field of part after mold release step

In our simulation, if the material is fed with isotropic material properties, the deviation is nearly none. It illustrates the origin of spring-in phenomena which is caused by the anisotropic properties.

Composites Meet Sustainability -Proceedings of the 20 th European Conference on Composite Materials, ECCM20. 26-30 June, 2022, Lausanne, Switzerland

Conclusion

This work aims at reducing the process development cost through the multiphysics simulation of the consolidation processes to avoid the costly trail-error approach. The multiphysics model proposed here is based on a coupling approach of the transient heat transfer, crystallization kinetics and elastic models at the macroscopic scale. This model can provide the evolution of shape distortion and induced stresses both during the consolidation process and mold release steps. These simulations can allow studying the consolidation problems such as loss of contact between tool and part due to the part shrinkage and its consequence on the heat transfer.

Optimal process parameters or a customized mold/part design thus can be considered to minimize the induced defects, such as how to minimize the peak of induced stresses.

Several extensions to this work have been identified. Simulations at the plies scale could give further information about the stress field, such as interlaminar stresses. A proper material characterization of orthotropic properties in the rubbery state is also of paramount importance. Viscoelastic models can also be considered in function of the its impact for a better correlation.

Figure 1 .

 1 Figure 1. Manufactured "Pylon" part

Figure 2 .

 2 Figure 2. 3D scan result and correlation of shape with respect to designed nominal 'Pylon" part

Figure 4 (

 4 Figure 4 (left) shows the full 3D CAD model of the studied pylon (red) part and mold. The part is composed of different zones with variable thicknesses and corresponding nominal angles. In this paper, a representative model is proposed (cf. Fig. 4 on the right) where only a section of the full pylon (colored in white) is considered. This allows to accelerate the computational time and the use of finer meshes.

Figure 4 .Figure 5 .

 45 Figure 4. Full CAD (left) and representative model (right)

Figure 5 .

 5 Figure 5. Cooling phase of the used consolidation cycle

Figure 6 .

 6 Figure 6. Simulated temperature field (left) and crystallization field (right) at the crystallization temperature during cooling phase

Figure 7 .

 7 Figure 7. Contact loss between part and mold at the corner due to shrinkages (before mold release)

  Composites Meet Sustainability -Proceedings of the 20 th European Conference on Composite Materials, ECCM20. 26-30 June, 2022, Lausanne, Switzerland

  Composites Meet Sustainability -Proceedings of the 20 th European Conference on Composite Materials, ECCM20. 26-30 June, 2022, Lausanne, Switzerland

  Composites Meet Sustainability -Proceedings of the 20 th European Conference on Composite Materials, ECCM20. 26-30 June, 2022, Lausanne, Switzerland

  Proceedings of the 20 th European Conference on Composite Materials, ECCM20. 26-30 June, 2022, Lausanne, Switzerland

Composites Meet Sustainability -

  Proceedings of the 20 th European Conference on Composite Materials, ECCM20. 26-30 June, 2022, Lausanne, Switzerland

Composites Meet Sustainability -

436/716 ©2022 Nguyen et al. doi:10.5075/epfl-298799_978-2-9701614-0-0 published under CC BY-NC 4.0 license ToC

437/716 ©2022 Nguyen et al. doi:10.5075/epfl-298799_978-2-9701614-0-0 published under CC BY-NC 4.0 license ToC

438/716 ©2022 Nguyen et al. doi:10.5075/epfl-298799_978-2-9701614-0-0 published under CC BY-NC 4.0 license ToC

439/716 ©2022 Nguyen et al. doi:10.5075/epfl-298799_978-2-9701614-0-0 published under CC BY-NC 4.0 license ToC

440/716 ©2022 Nguyen et al. doi:10.5075/epfl-298799_978-2-9701614-0-0 published under CC BY-NC 4.0 license ToC

441/716 ©2022 Nguyen et al. doi:10.5075/epfl-298799_978-2-9701614-0-0 published under CC BY-NC 4.0 license ToC

442/716 ©2022 Nguyen et al. doi:10.5075/epfl-298799_978-2-9701614-0-0 published under CC BY-NC 4.0 license ToC

443/716 ©2022 Nguyen et al. doi:10.5075/epfl-298799_978-2-9701614-0-0 published under CC BY-NC 4.0 license ToC

Acknowledgements

This study is part of the MATCH project managed by IRT Jules Verne (French Institute in Research and Technology in Advanced Manufacturing Technologies for Composite, Metallic and Hybrid Structures). The authors wish to associate the industrial and academic partners of this project; Respectively AIRBUS, LOIRETECH, DAHER, LS2N, ENSAM and LTeN laboratory. The authors would like to thank F. Guermeur and A. Levy for their participation on the building of numerical models.