Roman Matkovskyy
email: roman.matkovskyy@rennes-sb.com

Akanksha Jalan
email: akanksha.jalan@rennes-sb.com

Michael Dowling

From Financial Markets to Bitcoin Markets: A Fresh Look at the Contagion Effect

Keywords: Financial markets, Bitcoin, Contagion, Regime Switching Skew-normal Model (RSSN) JEL classification: E31, E44, G12, G15, C34, C11 financial markets, Bitcoin, contagion, regime switching skew-normal model (RSSN)

de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

On October 11, 2018, a downturn in equity markets seemingly caused Bitcoin prices to plummet by about 7%. Correspondingly, the Bloomberg Galaxy Crypto Index, Ether, and Litecoin decreased by about 10%, 11%, and 13%, respectively. Similarly, the stock market downturn in February 2018 was also publicly believed to have led to a drop in cryptocurrency markets. In light of these occurrences, this paper aims to investigate the spillover effects between equity and cryptocurrency markets.

In this article, we study both the presence of contagion effect and the medium of shock-transmission from equity to cryptocurrency markets. This is important in terms of understanding the impact volatility in traditional equity markets has on other financial markets that could potentially share a part of their investor base. It can also better explain Bitcoin price volatility, something that has puzzled both investors and academics. Substantial literature that examines the factors driving Bitcoin prices and explaining the volatility therein exists. Matkovskyy (2019) showed that centralized Bitcoin market returns have higher tail dependence. However, volatility results appear contrary to the established leverage theory that postulates that market drops cause volatility. [START_REF] Bariviera | Some stylized facts of the Bitcoin market[END_REF] found the standard deviation for Bitcoin prices is 10 times higher than for the euro and the British pound. [START_REF] Baek | Bitcoins as an investment or speculative vehicle? A first look[END_REF] noted most Bitcoin volatility is internally driven (by Bitcoin buyers and sellers), rather than externally motivated. Moreover, [START_REF] Dyhrberg | Bitcoin, gold and the dollar-A GARCH volatility analysis[END_REF] discovered Bitcoin prices are significantly affected by the federal funds rate, endowing them with currency-like characteristics.

Giudici and Abu-Hashish's (2019) research, which examined the spillover effects between different cryptocurrency and between crypto and traditional markets using an extended vector autoregressive model, is the closest to our present study. They found that although bitcoin prices from different exchanges are highly interrelated, they are unrelated to traditional market prices. Koutmos (2018) also conducted a similar investigation. Ciaian et al. (2018) showed that gold prices, exchange rates (USD/EUR and CNY/USD), and the 10-year Treasury constant maturity rate affect Bitcoin prices in both the short and long runs. [START_REF] Corbet | Cryptocurrencies as a financial asset: a systematic analysis[END_REF] analyzed the interdependence between crypto prices with other financial assets, such as gold, bonds, and stocks, and they found that cryptocurrencies are rather independent of movements in prices of traditional financial assets; this gives them a diversification quality. In a similar spirit, [START_REF] Corbet | Exploring the dynamic relationships between cryptocurrencies and other financial assets[END_REF] documented the relative isolation of cryptocurrencies from other financial and economic assets.

Our contribution both differs from and builds on these prior investigations because we examine the presence of contagion effect and the manner of shock transmissions from conventional financial markets to cryptocurrency markets. To the best of our knowledge, ours is the first paper that directly studies this phenomenon. We employ a new regime switching skew-normal model of asset returns developed by [START_REF] Chan | A regime swiching skew-normal model of contagion[END_REF]. Contagion is analyzed through channels of co-moments of correlation and co-skewness in two different regimes: at the time of Bitcoin price growth and at a price decrease. These periods coincide with the periods before and after the launch of Bitcoin futures.

Changes in market behavior following the introduction of a new financial instrument, such as futures, is well-documented in literature. Köchling et al. (2018) recognized that with the introduction of Bitcoin futures, Bitcoin markets transitioned from a bullish to bearish phase. For the same reason, we apply structural break tests using two regimes, bullish and bearish times, in Bitcoin markets to better understand investor behavior in the expectation that investor risk preferences may not remain the same during these times.

Results indicate increased contagion effects from financial to Bitcoin markets, especially from the high-tech industry, both in terms of correlation and co-skewness of market returns, starting December 18, 2017. This might indicate higher integration of Bitcoin markets into traditional financial systems. This is in contrast to the findings by [START_REF] Bouri | On the return-volatility relationship in the Bitcoin market around the price crash of 2013[END_REF]), Corbet, et al. (2018), and Giudici and Abu-Hashish (2019), who found no interdependence between Bitcoin and mainstream financial market returns. We attribute our results to increased efficiency in the Bitcoin markets following the launch of Bitcoin futures. First, futures provide the necessary institutional and legal framework for institutions to participate, and this is directly linked to market efficiency (Köchling et al., 2018). Second, futures create opportunities to hedge and speculate in Bitcoin; this is in conjunction with other instruments available in traditional financial markets and results in higher correlation.

Our results also indicate that risk-averse investors tend to shy away from risky Bitcoin markets during crisis periods and lean towards less volatile and more established financial markets, especially NASDAQ and NIKKEI. Our results not only contribute to a better understanding of the Bitcoin markets but also stress the need for a joint analysis of contagion and structural breaks in a multivariate setting.

The remainder of the paper proceeds as follows. Section 2 describes the data and methodology. In section 3, we discuss the empirical results, and in section 4 we offer our conclusions. The online appendix includes supplementary material.

Data and Model Set-up

The data set covers the daily close prices of Bitcoin denominated in the euro, U.S. dollar, British pound, and Japanese yen in the main centralized Bitcoin markets hosted by GDAX, Bitmap, and BTCBOX. For mainstream financial markets, we selected five equity market indices: two USD-denominated and one from each of the three other Bitcoin-denominated currency prices. These markets are NASDAQ100, S&P500, Euronext100, FTSE100, and Nikkei225. Price data ranges from April 27, 2015 to October 25, 2018 (Figure A1 and A2 in the online appendix). Daily percentage returns were computed as the difference of the natural logarithms of the daily price indices multiplied by 100.

To analyze contagion effects between financial and Bitcoin markets, a regime switching skew-normal model of asset returns was employed. It is an unrestricted model that allows us to analyze both linear and non-linear contagion between the two markets and also structural breaks in the moment of these markets across selected regimes [START_REF] Chan | A regime swiching skew-normal model of contagion[END_REF].

Two regimes are distinguished: an increase in Bitcoin prices in different markets until December 17, 2017, st = 0; and a decrease therein after December18, 2017, st = 1 (see Figure A1 in the online appendix). This coincides with the launch of the Bitcoin futures on December 17, 2017.

We believe that the regime switching skew-normal model is quite suitable for the purpose at hand because (a) it allows for the correlation and co-skewness contagion parameters to vary in different regimes, and (b) structural breaks in the mean, variance, and skewness are introduced that are potentially useful in cases of asymmetry and heavy tails.

The model is specified as follows (see [START_REF] Chan | A regime swiching skew-normal model of contagion[END_REF] for technical details):

= + Ω + , (1)
~ 0, Σ , (2)
~ 1 , 1 > , = 1, … , , (3)
The dynamics of correlation and co-skewness coefficients during the second regime is contagion, while changes in the parameters of moments of the mean, variance, and skewness values are considered to be structural breaks [START_REF] Chan | A regime swiching skew-normal model of contagion[END_REF].

Correlation tests contagion between the selected markets based on an increase in the correlation coefficients as in Forbes and Rigobon (2002). The probability of correlation contagion between the selected markets is therefore:

Pr \ + , F -\ + , FH > 0| , ] ^ . (7)
The co-skewness contagion test

J + , F ≠ J + , FH , ) ≠ (8)
tests for changes in the asymmetric dependence of returns i and j in regime ! = 0 compared with regime ! = 1.

The rationale for structural breaks in the mean for asset market i during ! = 1 compared to ! = 0 is based on a reduction in the mean values in periods of financial crisis vis-à-vis non-crisis periods, owing to an expected reduction in returns with the probability:

Pr + , F -+ , FH < 0| , ] ^ . ( 9
)
The test for structural breaks in the variance of the returns of market i follows the idea that the variance of returns will increase during crisis periods (i.e., Σ ++, F ≠ Σ ++, FH ). The probability is calculated similarly as in Eq. ( 7) and Eq. ( 9).

The structural break tests in skewness of returns i in regime ! = 1 compared to regime ! = 0 is based on the Savage-Dickey density ratio. The joint contagion and structural breaks across all the selected markets are also presented.

We compared crucial values from our empirical tests to those in [START_REF] Chan | A regime swiching skew-normal model of contagion[END_REF] for better understanding of contagion dynamics (Table A1 in the online appendix). Co-skewness and structural breaks in skewness can be used to analyze patterns in investor behavior because, generally, risk-averse investors prefer positive values of both skewness and coskewness.

Empirical Results

Table A2 (see the online appendix) provides general statistics under both regimes. Skewness and kurtosis values for Bitcoin and financial markets justify the use of the regime switching skew-normal model (i.e., non-normality in the returns in each market in both periods).

The contagion test results are provided in Tables A3a to A3e (in the online appendix).

Contagion is calculated with respect to equity markets as the source of shocks. The correlations in our contagion tests and mean and variance in structural breaks are probability based. Co-skewness, correlation, and co-skewness in contagion tests and skewness, mean, variance, and skewness in structural breaks are based on the log of the Bayesian factors (see Table A1 in the online appendix for crucial values).

Contagion tests indicate that during periods of crisis in Bitcoin markets, the probability of contagion from the NASDAQ to the selected Bitcoin markets is significantly high (all values of correlation contagion tests are above 0.64 [Table A3a]). This is not unexpected given the scale and scope of the NASDAQ. The correlation channel of contagion also dominates for the NIKKEI225-JPY Bitcoin market (correlation contagion tests = 0.7

[Table A3e]), the FTSE100-JPY Bitcoin market (correlation contagion tests = 0.68 [Table A3d]), and Euronext100-JPY Bitcoin market (correlation contagion tests = 0.84 [Table A3c]).

This might mean these markets became more correlated as Bitcoin prices fell after December 18, 2018. The lowest probability of contagion via correlation is observed for the S&P500, NIKKEI225, and Euro/USD/GBP markets. The probability of contagion happening jointly via the correlation channels is equal to zero for all the markets.

Although our results contrast with several earlier studies that found virtually no correlation between traditional and cryptocurrency markets, we attribute them to the introduction of Bitcoin futures that seemed to improve efficiency in the Bitcoin markets. For instance, Urquhart (2016) concluded that the Bitcoin market, though currently inefficient, may be in the process of moving towards efficiency. Similarly, Köchling et al. (2018) found the introduction of Bitcoin futures makes the Bitcoin market more informationally efficient.

Hale et al. ( 2018) noted that the sharp drop in Bitcoin prices after the launch of Bitcoin futures is consistent with typical investor behavior following the introduction of futures in asset markets. Before the launch of futures, optimists bid up the price; after it, pessimists cause prices to dip through short selling. Simultaneously, spot volatility increases following the appearance of futures contracts [START_REF] Corbet | Bitcoin futures-What use are they?[END_REF].

Co-skewness contagion tests supported this hypothesis. A direct one-to-one coskewness effect was observed between the NASDAQ and USD Bitcoin markets (coefficient = -2.04 [Table A3a]) and the NIKKEI225 and GBP Bitcoin market (coefficient = -1.22 [Table A3e]) and indicate that when Bitcoin prices fall, risk-averse investors jump from Bitmap USD and GDAX GBP Bitcoin markets towards so-called safer havens: the NASDAQ100 and NIKKEI225, respectively. The rest of the co-skewness contagion tests coefficients remained insignificant.

Structural break tests indicated that the selected Bitcoin markets were individually affected by breaks in the means, with higher probability than variances (for which probability equaled 0 for all markets).

The tests revealed structural breaks in skewness for the NASDAQ100/NIKKEI225 and all selected Bitcoin markets, the Euronext100 and the euro and GBP Bitcoin markets, and the FTSE100 and euro Bitcoin market. This reinforces our view that risk-averse investors prefer the NASDAQ100 and NIKKEI225 to USD/GBP/JPY Bitcoin markets after launching Bitcoin futures. Also, these investors prefer European assets to Bitcoins traded in the euro and GDP markets.

Joint contagion and structural break tests used in this paper examined the significance of contagion and structural breaks simultaneously for each market i and jointly for the overall market. Thus, they tested for both crisis and contagion. Joint tests of the mean, variance, and skewness structural breaks for each market showed decisive evidence of structural breaks, further justifying the use of our model. Considering all m markets jointly, we found conclusive empirical evidence for structural breaks in the first to third moments after the launch of Bitcoin futures compared to the pre-launch period. These results reinforce our belief that during downturns, contagion and structural breaks should be studied jointly.

Conclusion

This paper analyzes contagion effects from five equity markets in the United States, Europe, Great Britain, and Japan to USD/EUR/GBP/JPY Bitcoin markets. To the best of our knowledge, ours is the first paper to empirically examine this issue. Given the nature of the data set, a new regime switching skew-normal model of crisis and contagion developed by [START_REF] Chan | A regime swiching skew-normal model of contagion[END_REF] was used.

Results indicated that Bitcoin return co-movements were significantly different in Bitcoin futures launch periods compared to the pre-launch period when prices were rising.

Bitcoin futures created opportunities for short selling, which resulted in a mass decline in spot demand and, consequently, a drop in Bitcoin prices. This resulted in newer opportunities to hedge and speculate in conjunction with other instruments available in other financial markets; this interdependence increased the post-launch of Bitcoin futures.

Results indicate that risk-averse investors moved from Bitmap USD and GDAX GBP Bitcoin markets towards assets listed on the NASDAQ and NIKKEI225, respectively, in periods of falling Bitcoin prices, as also from Euro/GDP Bitcoin markets to European assets.

Our results emphasize the need for a joint analysis of contagion and structural breaks in a multivariate framework.

  is an m-dimensional random vector, t = 1,…,T, ! ∈ {0, 1} is a regime at time t, where Pr ! = 1|! ( = ) = * + and Pr ! = 0|! ( = ) = 1 -* + , that is the probability of state 1 and state 0, respectively, that vary over time (! is generated by means of a multi-move Gibbs sampling method); mean values form an m x 1 vector; Ω is an m x m skewness-co-skewness matrix where the off-diagonal elements are the co-skewness parameters that control asymmetric dependency between the elements of the vector ; = , … , ′ is an m-dimensional random vector IID; is an m x 1 vector of innovations that is independent and identically distributed; Σ is an m x m error cross-covariance matrix, the constant term = -/2/2(Sahu et al., 2003); 1 is an m x 1 column of ones; is the identity matrix; and 1 • is a scalar indicator function that takes a value of 0 when all are less then C and 1 otherwise. The parameters are estimated by applying of the MCMC and C H , C , Σ H , Σ , ! ∈ {0, 1}. B C comes from the rewritten Eq. have the inverse-Wishard distribution with degree of freedom X Y and scale matrix Z Y :Σ ~ [ MX Y , Z Y P.

Forbes, K.J., Rigobon, R., 2002. No contagion, only interdependence: Measuring Stock market comovements. The Journal of Finance. 57, 5, 2223-2261. Giudici, P., Abu-Hashish, I., 2019


Pierre Fraigniaud

David Ilcinkas

Sergio Rajsbaum

Sébastien Tixeuil

Space lower bounds for graph exploration via reduced automata

Keywords: Graph exploration, finite automaton, robot, mobile agent

. Our main result is an application of this improvement. It concerns exploration with stop, in which one robot has to explore and stop after completing exploration. For this task, the robot is provided with a pebble, that it can use to mark nodes. We prove that exploration with stop requires Ω(log n) bits for the family of graphs with at most n nodes. On the other hand, we prove that there exists an exploration with stop algorithm using a robot with O(D log ∆) bits of memory to explore all graphs of diameter at most D and degree at most ∆.

Introduction

The problem of exploring an unknown environment occurs in a variety of situations, like robot navigation, network maintenance, resource discovery, WWW search, etc. The environment is modeled as a graph where one or more mobile agents, called robots in this paper, are trying to collectively traverse every one of its edges. There is a large body of work, that considers several variants of the problem, since at least 1951; see e.g. [START_REF] Bender | The power of a pebble: Exploring and mapping directed graphs[END_REF][START_REF] Bender | The power of team exploration: Two robots can learn unlabeled directed graphs[END_REF][START_REF] Budach | Automata and labyrinths[END_REF][START_REF] Diks | Tree Exploration with Little Memory[END_REF][START_REF] Dudek | Robotic Exploration as Graph Construction[END_REF][START_REF] Fraigniaud | Graph Exploration by a Finite Automaton[END_REF][START_REF] Rollik | Automaten in planaren graphen[END_REF][START_REF] Shannon | Presentation of a Maze-Solving Machine[END_REF] and references herein.

In this paper we are interested in exploration of undirected graphs where nodes are not uniquely labeled. Besides the theoretical interest of understanding when or at what cost such graphs can be explored, this situation can occur in practice, due to e.g. privacy concerns, limited capabilities of the robots, or simply anonymous edge intersections. We do assume that a robot can identify This work has been supported by the projects: INRIA "Grand Large", "PairAPair" of the ACI "Masses de Données", "FRAGILE" of the ACI "Sécurité et Informatique," LAFMI (Franco-Mexican lab in Computer Science), and PAPIIT-UNAM.

the edges incident to a node through unique port labels. Our main goal is to compute complexity bounds on the amount of memory needed by a set of robots as a function of the size of the graphs that they can explore.

A robot moves from one node to another along the edges. When in a node, it (deterministically) decides on the port number of an incident edge to move to the node at the other end of the corresponding edge. It is easy to see that a robot can traverse all edges of some graphs, say a cycle, but that it cannot recognize when it has visited a node twice, so it explores all the graph but never stops. Thus we consider also robots that can mark nodes; as in previous work e.g. [START_REF] Bender | The power of a pebble: Exploring and mapping directed graphs[END_REF][START_REF] Bender | The power of team exploration: Two robots can learn unlabeled directed graphs[END_REF] the robot can drop a pebble in a node and later identify it and pick it up. In this case the robot can explore a graph and stop.

Collective Exploration

A graph that a set of robots cannot explore when they all star from some given node (or set of nodes) is said to be a trap for them. The first trap for a finite state robot is generally attributed to Budach [START_REF] Budach | Automata and labyrinths[END_REF] (the trap is actually a planar graph). The trap constructed by Budach is of large size. A much smaller trap was described in [START_REF] Fraigniaud | Graph Exploration by a Finite Automaton[END_REF]: for any K-state robot, there exists a trap of at most K + 1 nodes. In [START_REF] Rollik | Automaten in planaren graphen[END_REF], Rollik proved that no finite set of finite cooperative robots, i.e., automata that exchange information only when they meet at a node, can explore all graphs. In the proof of this result, the author uses as a tool a trap for a set of q non-cooperative K-state robots. This latter trap is of size O(K O(q) ) nodes.

The size 1

Õ(K K • • • K
), with 2q + 1 levels of exponential, of the trap constructed for cooperative robots depends highly on the size of a trap for non-cooperative robots.

In this paper, we first show (cf. Theorem 1) that for any set of q noncooperative K-state robots, there exists a 3-regular graph G, and two pairs {u, u } and {v, v } of neighboring nodes, such that any robot of the set, starting from u or u , fails to traverse the edge {v, v }. The graph G has O(qK) nodes, thus improving the O(K O(q) ) bound of [START_REF] Rollik | Automaten in planaren graphen[END_REF] (cf. Corollary 1). By simply plugging this new trap for non-cooperative robots in the trap for cooperative robots by Rollik, we get a new trap of size Õ(K ), with q + 1 levels of exponential, thus smaller than the one in [START_REF] Rollik | Automaten in planaren graphen[END_REF] (cf. Corollary 2).

Exploration by a Single Robot

Theorem 1 has a significant impact on the space complexity of graph exploration by a single robot. We distinguish the two types of exploration mentioned above perpetual exploration and exploration with stop, where the robot has to stop once exploration is completed.

In acyclic graphs, exploration with stop is strictly more difficult than perpetual exploration. In particular, it is shown in [START_REF] Diks | Tree Exploration with Little Memory[END_REF] that exploration with stop in n-node bounded degree trees requires a robot with memory size Ω(log log log n), whereas perpetual exploration requires O(1) bits.

As mentioned above, when exploration with stop is required, the robot is provided with a pebble. We prove (cf. Theorem 2) that exploration with stop requires a robot with Ω(log n) bits for the family of graphs with at most n nodes. Note that, in arbitrary graphs, perpetual exploration and exploration with stop are not comparable because even if perpetual exploration is a simpler task than exploration with stop, in the latter case the robot is given a pebble. Therefore, even if the existence of a trap of at most K + 1 nodes for any K-state robot described in [START_REF] Fraigniaud | Graph Exploration by a Finite Automaton[END_REF] implies an Ω(log n) bits lower bound for the memory size of a robot that performs perpetual exploration in all graphs with at most n nodes, our Ω(log n) lower bound is not a consequence of the result in [START_REF] Fraigniaud | Graph Exploration by a Finite Automaton[END_REF].

Finally, we prove (cf. Theorem 3) that there exists an exploration with stop algorithm using a robot with O(D log ∆) bits of memory for the exploration with stop of all graphs of diameter at most D and degree at most ∆.

Preliminaries

In Section 2.1 we define formally what we mean by a robot exploring a graph. In Section 2.2 we describe the basic properties of a robot. In Section 2.3 we show how to simplify the structure of a robot, for the proofs of the following sections.

Graphs and Robots

A robot considered in this paper traverses a graph by moving from node to node along the edges of the graph. All nodes are identical and hence indistinguishable to the robot. However, each edge has two labels, each one associated to one of its two endpoints. The labels are arbitrary, except that the edges incident to a node are required to have different labels in their endpoints corresponding to the node. When a robot is in a node, it sees only the labels at the endpoints of the edges incident to the node. This allows the robot to distinguish the edges incident to the node through their unique labels, called local port numbers.

An edge may have different port numbers in its two endpoints. When a robot is in a node s and traverses an edge to get to the node t at the other end of the edge, it learns the label at t's endpoint of the edge once it enters t. The robot decides which edge to take to leave t based on this label, as well as on the other local port numbers at t (and hence the degree of t). To compute memory lower bounds, it suffices to consider graphs where both port numbers coincide, and where all nodes have the same degree. In such a graph a robot can be described by a very simple automaton, as we shall see next. Thus, the graphs considered in this paper are δ-homogeneous undirected graphs: δ-regular and edge-colored. A graph is δ-regular if each of its nodes has degree δ, and it is edge-colored if each edge is labeled with one of the integers in the set ∆ = {0, 1, . . . , δ -1} in a way that no two edges incident to the same node have the same color.

When a robot traverses a δ-homogeneous graph, each time it arrives to a node the local environment looks exactly the same as in any other node: all nodes are equal and in each node all local ports are 0, 1, . . . , δ -1. Thus, the robot decides which edge to take to exit the node based only on its current state. Formally, a δ-robot or simply robot when δ is understood, is an automaton A = (∆, S, f, s 0 ), with a finite set of states S, an initial state s 0 ∈ S, and a transition function f : S → S × ∆. For a state s ∈ S with f (s) = (s , i), denote f st (s) = s and f (s) = i. The δ-robot A moves on a δ-regular graph as follows. Initially A is placed on a node of the graph in state s 0 . If A is in a node v in state s then A moves to the node v such that the edge {v, v } is labeled f (s), and changes to state f st (s). We say that A traversed the edge {v, v }. We assume that every state s ∈ S of A is reachable from s 0 (unreachable states do not affect the behavior of A and can be ignored). In Section 4 we will consider an extended definition of a robot that can drop a pebble in a node and pick it up when it returns to the node to drop it somewhere else.

A trap for a set of δ-robots is a pair (G, U ), where G is a δ-homogeneous graph and U is a set of nodes, such that if all the robots are placed in nodes of u ∈ U , each in its initial state, then there will be an edge {v, v } that is never traversed by the robots.

Basic Properties

Consider a robot A = (∆, S, f, s 0 ). The transition function f defines a directed labeled graph G(A) = (S, F ) with node set S and arc set F , such that the arc s → t ∈ F iff f st (s) = t, and the arc has label f (s). Notice that the labeled graph G(A) together with the starting node s 0 completely determine the robot A.

Each node of G(A) has out-degree 1 because f is a function. It follows that G(A) consists of a simple, possibly empty path starting in s 0 and ending in some node s 1 , followed by a simple cycle starting and ending in s 1 . This is because we assume that A has no unreachable states and S is finite. Thus, the arc labels of the path define a path word W 0 over ∆, |W 0 | ≥ 0, and the arc labels of the cycle define a cycle word

W over ∆, |W | ≥ 1. Clearly, |W 0 W | = |S|. The footprint of A is f p(A) = W 0 W * . When A is placed on a node of a graph in state s 0 , f p(A)
is the sequence of labels of edges traversed by A. The next lemma says that once A reaches a node x of the graph in some state s that belongs to the cycle of G(A), the path that A follows in G is a closed path that includes x; moreover, A returns to x in the same state s.

Lemma 1. Consider a robot A with path and cycle words W 0 , W placed in a node of a graph G. Let x be a node reached by A after at least |W 0 | steps, and assume A is in state s at this moment. Then A will eventually be back in x in state s.

Proof. Consider the behavior of A after at least |W 0 | steps. The robot A is thus changing from state to state along the cycle of G(A). Since this cycle is finite, and G is also finite, the robot must be twice in the same node in the same state. Assume for contradiction that A is not twice in (x, s), i.e. in node x in state s. Then let x be the first node (after x) for which A is twice in the same state, s . Consider the path taken by A from the initial node to the first time it is in node x in state s , and let x 1 be the last node before entering x in state s for the first time. Suppose A is in state s 1 at this time. So A is never twice in (x 1 , s 1 ). When A eventually returns to x in s , the last node visited is x in state s . But since all the states considered in the lemma are in the cycle of G(A) (because A has taken at least |W 0 | steps), it must be that s = s 1 . Thus, f (s ) = f (s 1 ), which implies that x 1 = x (since G is homogeneous). Then A is twice in (x 1 , s 1 ), a contradiction.

Reduced Robots

A robot A is irreducible if G(A) satisfies two properties: (i) for any two consec- utive (distinct) arcs s → s 1 → s 2 , it holds f (s) = f (s 1 )
, and (ii) for the two arcs with the same end-node s → s 1 , s 2 → s 1 , it holds f (s) = f (s 2 ). We show here how to obtain an irreducible robot A = (∆, S , f , s 0 ) from a robot A. The behavior of A and of A on a graph will not be exactly the same, but will be related in the sense that the region of a graph traversed by A cannot be much larger than the region traversed by A .

Let Ḡ(A) be the undirected graph corresponding to G(A). Then, if A is irreducible and its simple cycle is of length at least 2, then Ḡ(A) is edge-colored. Roughly speaking, we want the robot to be irreducible to construct a graph based on Ḡ(A) on which the robot will be moving. Since the constructed graph must be homogeneous, Ḡ(A) must be homogeneous. Then we can place A at the beginning of the path of Ḡ(A) and it will never try to go out of Ḡ(A). To obtain an irreducible robot A from A we perform a series of reduction steps that modify its transition function and reachable states. When A, A are placed on the same node of a graph, the path traversed by A is contained in the the path traversed by A; essentially A skips some closed walks of A. These reductions are formally defined next.

A reduction step is the operation consisting of transforming a robot A = (∆, S, f, s 0 ) into another robot A = (∆, S , f , s 0 ) where one of the above properties (i) or (ii) is enforced for two arcs, each corresponding to a type-i or type-ii reduction step. The idea is to repeat type-i steps until no more are possible, and hence the robot satisfies property (i), and then if property (ii) is not satisfied, do a single type-ii step to enforce property (ii). Only type-i reductions change the path traversed by the robot.

A type-i reduction step is applicable if G(A) has two consecutive distinct arcs s → s 1 → s 2 with f (s) = f (s 1 ). First, if s = s 2 (so the cycle is of length 2 with same labels), A is obtained from A by letting f (s) = (s, i), where i = f (s); and if s 1 = s 0 then s 0 = s. For other states f = f . Otherwise, if s = s 2 , it is possible that s has 0, 1, or 2 in-neighbors. In each of these cases A is obtained from A by the following modifications. If s has 0 in-neighbors, then s = s 0 ; let s 0 = s 2 . If s has 1 in-neighbor t (t = s 1 ), with f (t) = (s, i), then let f (t) = (s 2 , i); If s = s 0 then let s 0 = s 2 . If s has 2 in-neighbors t 1 , t 2 , with f (t 1 ) = (s, i), f (t 2 ) = (s, j), then s = s 0 ; Let f (t 1 ) = (s 2 , i) and f (t 2 ) = (s 2 , j). For other states f = f . After doing these modifications, A is obtained by removing any unreachable states. Notice that for each one of the previous 3 cases at least one unreachable state is removed, namely s. Thus, at most K -1 type-i reductions are possible, starting from a K-state robot.

We will use the following properties of a type-i reduction. Since f (s) = f (s 1 ) = i, if the robot is in a node v of the graph in state s, then it moves to v , where {v, v } is colored i, changes to state s 1 , and moves back to v, in state s 2 . Thus, it is easy to check that a type-i reduction eliminates this v, v , v loop from the path traversed by the robot in the graph, and makes no other changes to the path; that is, if the path arrives to v from w and then proceeds to w after traversing the v, v , v loop, after the type-i reduction the robot will go from w to v and then directly to w . Therefore, before the reduction step, the robot explores a node at most distance 1 from the nodes explored by the robot after the reduction.

Once a type-i reduction step is not applicable in G(A), a single type-ii reduction step is used, defined as follows. Assume there are two states such that f (s) = f (s 1 ), that is, G(A) has two arcs with the same end-node s → t, s 1 → t, and f (s) = f (s 1 ); otherwise the reduction does nothing. Exactly one of s, s 1 must be in the cycle of G(A), let's say s 1 . So there is a path from t to s 1 . Notice that this path is of length at least 1 (i.e. the cycle of G(A) is of length at least 2), because otherwise t = s 1 and there is a loop from t to itself labeled f (s), and a type-i reduction is applicable.

Recall that f p(A) = W 0 W * . Let W be the longest common postfix of W 0 and W ; |W | > 0 by the type-ii assumption. We consider two cases:

|W 0 | > |W | and |W 0 | = |W |.
In the first case W is a postfix of W 0 ; let t 1 be the in-neighbor of the node just before W starts in the simple path of G(A) and let t 2 be the node just before W starts in the cycle of G(A); thus f (f st (t 1 )) = f (t 2 ) is the first letter of W . In both cases A is obtained from A by the following modifications:

If |W 0 | > |W |, let f (t 1 ) = (t 2 , f (t 1 )). If |W 0 | = |W | let s 0 = t 2 ,
and removing any unreachable states.

We use the following two properties of a type-ii reduction. A type-ii reduction does not change at all the path traversed by the robot in the graph. After a type-ii reduction is executed property (ii) is satisfied, and property (i) is not violated.

The previous arguments imply:

Lemma 2. For any robot A = (∆, S, f, s 0 ) the robot A obtained through the longest possible sequence of type-i reductions followed by a type-ii reduction is irreducible. Let k be the number of type-i reduction steps in this sequence. Then k ≤ |S| -1. Assume both start at some node of a given graph. Then any edge traversed by A is at distance at most k from some edge traversed by A .

A Trap for a Team of Non-Cooperative Robots

In this section, we focus on graph exploration by a team of non-cooperative robots.

Theorem 1. For any set A of q non-cooperative K-state robots, there exist a 3-homogeneous graph G and two pairs of neighboring nodes {u, u } and {v, v } such that (1) the edge {u, u } is labeled 0, (2) starting at u or at u , any robot in A fails to traverse the edge {v, v }, and (3) G has 10qK + O(q) nodes.

Proof. The proof is by induction on q ≥ 0. The basic step is q = 0. The corresponding graph G is displayed on Figure 1. For the induction step, assume that Theorem 1 holds for q, and let us show that it holds for q + 1. Let A be a set of q + 1 non-cooperative K-state robots, and let A ∈ A. By induction hypothesis, let G q be an n-node 3-homogeneous graph (where n is 10qK + O(q)) having two pairs of neighboring nodes {u, u } and {v, v } with the edge {u, u } labeled 0, such that, starting at u or at u , any robot in A \ {A} fails to traverse the edge {v, v }. We construct a graph G q+1 that satisfies Theorem 1 for A.

u u' v v'
Let A be an irreducible robot obtained from A as in Lemma 2. Consider its footprint f p( A) = W 0 W * , |W 0 W | ≤ K. We concentrate first our attention on A, and will come back later to the original robot A. Let us denote by p i the i-th letter in f p( A). Recall that since A is irreducible, its associated undirected graph Ḡ( A) is homogeneous.

Let us place A at node u of G q , and let us observe its behavior. Let H 1 be the graph obtained from G q by "cutting" the edge {v, v }. In H 1 , nodes v and v are both connected to a pending "half-edge." If A traverses the edge {v, v } in G q , then in H 1 it traverses one of these two half-edges, say the half-edge e pending at v. We consider two cases, depending on when A traverses e.

Case 1. If A traverses e at step i ≤ |W 0 | (so p i is the label of e), then we connect to e a path of length |W 0 | -i whose extremity is denoted by w. The edges of this path are labeled p i+1 , . . . , p |W0| . Note that since A is irreducible, two consecutive labels of this path are distinct. At w, we add a ring of length |W |. The edges of this ring are labeled p |W0|+1 , . . . , p |W0|+|W | starting and ending at w. Note that since A is irreducible, two consecutive labels of the ring are distinct, and the three labels p |W0| , p |W0|+1 , and p |W0|+|W | are pairwise distinct. To avoid parallel edges we add a ring of length 2|W | at w if |W | = 2; to avoid loops when |W | = 1, we add a ring with labels abab, where a is equal to the single letter of W , and b is different from a and from the label p i of e.

Case 2. If A traverses e at step i > |W 0 |, then it traverses e to get into some state s of the cycle in G( A); assume this is the j-th state of the cycle (recall that the cycle is assumed to start in the last state of the path of G( A)). That is, after traversing e, A would traverse edges labeled p |W0|+j , p |W0|+j+1 , . . . Let x be the node of H 1 reached by A after |W 0 | steps, let W -1 be the sequence W written in reverse order, and let A -1 be the robot that traverses edges labeled (W -1 ) * . Thus, when A -1 starts at x and A reaches x, A -1 proceeds as A, but backwards. Let A * be the robot that traverses edges labeled W * , i.e. the robot derived from A by removing states and transitions that involved W 0 .

Claim. Starting from x, A -1 eventually traverses one of the half-edges pending at v or v .

Proof. Assume for contradiction that A -1 does not traverse any of the half-edges pending at v or v . By Lemma 1, A -1 returns to x in the same state, and hence its path in H 1 is a closed path. This path traversed backwards is exactly what A * traverses from x. So A * does not traverse any of the half-edges pending at v or v . Thus, A also does not traverse them, a contradiction. By Claim 3 we can consider the state reached by A -1 after it traverses one of the pending half-edges; assume this is the k-th state of the cycle in G( A). We consider two sub-cases, depending on whether A -1 traverses the same half-edge as A, or not.

Case 2.1. The robot A -1 traverses the half-edge e pending at v (i.e., the same as A). This implies that the k-th label in W is equal to the (j -1)-th label in W , which is the label of e. We consider the section of the cycle of G( A) from the j-th state to the k-th state. The end edges of this section have the label of e. We now consider the following word: W = W (j -1)W (j)W (j + 1) . . . W (k -1)W (k)W (k +1) . . . W (j -1)W (j)W (j +1) . . . W (k -1)W (k)W (k + 1) . . . W (j -1)W (j)W (j +1) . . . W (k -1)W (k) (Note that W (j -1) = W (k) and |W | ≥ 2 × |W | + 2). The two robots A and A -1 cannot follow the same path forever after crossing edge e: otherwise, it would mean that moving them both backwards, they would also follow the same path forever (which is impossible since the two robots took different paths at node x in the past). Moreover, the two robots must separate after at most |W | steps, and since |W | ≥ 2 × |W | + 2, they must separate after at least 1 step and at most |W | -1 steps. Now, if the two robots separate from each other at some point after crossing edge e, let us consider the smallest l such that W (j + l) = W (k -1 -l), i.e. the nearest place where the two robots separate from one another. Since W (j -1) = W (k), l ≥ 1. By definition of l, we have W (j + l -1) = W (k -l). Since the considered robots are reduced, we also have W (j + l -1) = W (j + l). Still by definition of l, we get W (j + l) = W (k -1 -l). Finally, because we consider reduced robots and we have W (j + l -1) = W (k -l), we get W (j + l -1) = W (k -1 -l). Overall, this means that W (j + l -1), W (j + l), and W (k -1 -l) are pairwise disjoint. We are now ready to construct the following graph: from e, there is a chain that ends in W (j + l -1) at node w, and from this last node a circle W goes from

W (j + l) to W (k -l -1). Since W (j + l) = W (k -1 -l) (see above), |W | > 2.
When |W | > 2, we add at w a ring of length |W | labeled W , starting and ending at w, so that once A and A -1 reach w, each one traverses this ring in the opposite direction, and gets back to w in the appropriate state to proceed along the path back to the half-edge e.

Case 2.2. The robot A -1 traverses the half-edge e pending at v (i.e., not the same as A). Suppose when A -1 goes through v it is in state s. We consider again the section of the cycle of G( A) from the j-th state to the k-th state (if the section is of length 1, we extend it with W to make sure there is at least one internal node). We connect e and e by a path with the labels of this section. Thus, when A traverses the half-edge e, it follows the newly added path, and gets to v in the appropriate state, namely s, to proceed along the same path of A -1 but backwards, and return to x.

In all three cases, every node of degree 2 in the resulting graph is complemented by a pending half-edge, and every node of degree 1 is complemented by two pending half-edges. Every half-edge is labeled consistently so that the resulting graph, denoted by H 2 , is 3-homogeneous.

Finally, if A does not traverse any of the two pending half-edges, then we set H 2 = H 1 . For l = 0, 1, 2, let parity(l) be the parity of the number of pending half-edges labeled l in H 2 .

Claim. For any l, l ∈ {0, 1, 2}, parity(l) = parity(l ).

Proof. An edge of H 2 can be considered as two non-pending half-edges. For l ∈ {0, 1, 2}, let t l be the total number of half-edges of H 2 labeled l, and p l , resp. np l , be the number of pending, resp. non-pending, half-edges of H 2 labeled l. All nodes in H 2 are exactly of degree 3 and are incident to one half-edge of each label. Thus t 0 = t 1 = t 2 = |H 2 | where |H 2 | is the number of nodes of H 2 . In H 2 , if an half-edge is not pending, then it forms an edge with another non-pending edge of H 2 with the same label. Therefore, all the np l 's are even. Since t l = p l + np l , t l and p l have the same parity, and thus all the p l 's have the same parity.

The parity of the number of pending half-edges of a given label in H 2 is denoted by . If is odd, then we add to H 2 a node connected to one of the half-edges, labeled say l, and add two half-edges pending from this node, labeled l = l and l / ∈ {l, l }. As a consequence, becomes even. Now, we pair the halfedges with identical labels. For every pair but one, we connect the two half-edges of the pair by the gadget displayed in Figure 2. (It could be possible to connect the half-edges by just one edge, but the resulting graph may then not be simple). By labeling the edges of every gadget appropriately, we obtain a 3-homogeneous graph H 3 with only two pending half-edges, of the same label. Proof. By construction, A travels in G q , and outside G q it follows the trajectory defined by paths and/or the ring attached to G q at edges e and e . Therefore, A does not traverse any of the half-edges of H 2 . In particular, it does not traverse any of the two half-edges of H 3 .

We define H 4 as the graph obtained from H 3 by adding a "tower" of height K + 1 connected to the two remaining half-edges, and a gadget closing the tower (see Figure 3):

K+1 H 3 v v' 1 1
Fig. 3. The "tower" added to H3

Finally, the two internal nodes of the gadget at the top of the tower in H 4 are denoted by v 1 and v 1 (see Figure 3).

Claim. The edge {v 1 , v 1 } of H 4 is not traversed by A when starting from u.

Proof. By Claim 3, starting from u in H 4 , A does not traverse any of the two edges leading from H 3 to the tower. By Lemma 2, the trajectory of A is never at distance greater than K (where K is the number of states of A) from the trajectory of A. Thus, since the tower is of height K + 1, A never reaches the top of the tower. Therefore, A does not traverse the edge {v 1 , v 1 }.

We repeat the same construction by considering the robot A launched from u in H 4 . More precisely, we construct G q+1 from H 4 in the same way H 4 was constructed from G q . In particular, there is a tower in G q+1 , and we define the nodes v 2 and v 2 of G q+1 as the two internal nodes of the gadget at the top of this tower. By construction G q+1 is 3-homogeneous.

Claim. Any robot in A fails to traverse the edge {v 2 , v 2 } of G q+1 when starting from u or u .

Proof. By induction hypothesis, starting from u or u , a robot in A \ {A} never traverses v, v in G q and so will never traverse any of the edges added to obtain G q+1 , and hence does not traverse the edge {v 2 , v 2 } of G q+1 . From Claim 3, starting from u, A fails to traverse the edge {v 1 , v 1 } of H 4 . This edge being the one that is "opened" to construct G q+1 from H 4 , A fails to reach any of the two nodes v 2 or v 2 in G q+1 . Finally, by construction of G q+1 from H 4 , A fails to reach any of the two nodes v 2 or v 2 in G q+1 when starting from u , in the same way A fails to reach any of the two nodes w or w in H 4 when starting from u.

To complete the proof, it just remains to compute the size of G q+1 .

Claim. |G q+1 | ≤ |G q | + 10K + O(1).
Proof. We give simple upper bounds on the size of the intermediate graphs. As a direct consequence of the previous claim, |G q+1 | ≤ 10qK + O(q), which completes the proof of Theorem 1.

By simply rewriting Theorem 1, we derive a bound of the size of the smallest trap for a set of q non-cooperative K-state robots, improving the one by Rollik [START_REF] Rollik | Automaten in planaren graphen[END_REF]: Corollary 1. For any set of q non-cooperative K-state robots, there exists a trap of size O(qK).

By simply plugging this latter bound in the construction by Rollik [START_REF] Rollik | Automaten in planaren graphen[END_REF] for team of cooperative robots, we get: Corollary 2. For any set of q cooperative K-state robots, there exists a trap of size Õ(K K • • • K ), with q + 1 levels of exponential.

Bounds for Exploration With Stop

In this section, we consider the exploration with stop problem, in which a robot must traverse all edges of the graph, and eventually stop once this task has been achieved. A robot cannot solve this task in graphs with more nodes than its number of states, by Lemma 1. Thus, the robot is given pebbles that it can drop and take to/from any node in the graph. It is known that any finite robot with a finite source of pebbles cannot explore all graphs [START_REF] Rollik | Automaten in planaren graphen[END_REF]. On the other hand, it is known that a robot with unbounded memory can explore all graphs, using only one pebble [START_REF] Dudek | Robotic Exploration as Graph Construction[END_REF]. An important issue is to bound the size of the robot as a function of the size of the explored graphs. A δ-p-robot with a pebble or simply p-robot when δ is understood, is an automaton A = (∆, S, f, s 0 , s f ), with a finite set of states S, s 0 , s f ∈ S, and

f : S × {0, 1} → S × ∆ × {pick, drop}.
Every state s ∈ S has a component p(s) ∈ {0, 1} that indicates if A has the pebble, p(s) = 1, or not, p(s) = 0. For the initial state, s 0 , p(s 0 ) = 0; for the stop state, s f , p(s f ) = 1. Each node v of the graph is in some state p(v) ∈ {0, 1} that indicates if the pebble is in v, p(v) = 1, or not, p(v) = 0. The initial state of the graph satisfies: p(v) = 1 for exactly one node v. We will assume the robot is placed initially in the node with the pebble.

The movement of a δ-p-robot A on a δ-regular graph is represented by a sequence of configurations, each one consisting of the state of the robot and the state of the graph. For the initial configuration, A is placed on some node of the graph in state s 0 , and the pebble is in exactly one node. In general, if A is in a node v in state s in some configuration, we compute f (s, p(v)) = (s , i, b). In the next configuration A will be in the node v such that the edge {v, v } is colored i, in state s . Also in the next configuration: if b = drop then p(v) = 1 and p(s ) = 0, and if b = pick then p(v) = 0 and p(s ) = 1. It is assumed that b can be equal to drop only if p(s) = 1 and b can be equal to pick only if p(v) = 1.

A robot A explores with stop a graph if after starting in any node of the graph that has the pebble, it traverses all its edges and enters a stop state. A graph which A does not explore with stop is called a trap for A.

The next theorem shows that a p-robot that performs exploration with stop in all graphs of at most n nodes requires Ω(n 1/3 ) states, or equivalently Ω(log n) bits of memory.

Theorem 2. For any K-state p-robot there exists a trap of size O(K 3 ).

Proof. Let A = (∆, S, f, s 0 , s f ) be a K-state p-robot. We construct a trap of size O(K 3 ) for A. For that purpose, we consider the restriction of A to states s such that p(s) = 0 and input 0 (on nodes with no pebble). This defines a robot (with no pebble, as in Section 2.1) except that some states may be unreachable from s 0 . For every state s of this robot, we consider the robot A s that has s as initial state, and includes only reachable states from s. Let A = {A s } be the set of all these robots. Thus, |A| ≤ K.

Let G be a graph satisfying Theorem 1 for the set A. Remove edges {u, u } and {v, v } from G. Consider two copies of the resulting graph, with the four nodes of degree 2 indexed by the index of the copy, 1 and 2. These nodes are re-connected as follows. Let c be the color of the deleted edge {v, v }. Create two edges {v 1 , v 2 } and {v 1 , v 2 } with color c. The resulting graph is denoted by G 1 (see Figure 4). Consider an infinite ternary tree modified as follows. Each node is replaced by a 6-cycle. Edges of the cycles are labeled alternatively 1 and 2. Then, edges of the infinite tree are replaced by two "parallel" edges labeled 0, as depicted on Figure 5. The resulting graph is denoted by T .

u 1 u' 1 v 1 v' 1 Graph G Graph G u 2 u' 2 v 2 v' 2

XIV

The two graphs G 1 and T are composed by replacing every pair {{x, y}, {x , y }} of parallel edges in T by a copy of G 1 . More precisely, x, y, x , y are respectively connected to nodes u 1 , u 2 , u 1 , u 2 in G 1 . These new edges are labeled 0. The resulting graph is denoted by G 2 . A "meta-edge" of G 2 is defined as a copy of G 1 replacing a parallel edge of T .

By definition of G and A, the p-robot A is unable to traverse a meta-edge of G 2 without the help of the pebble2 . We now modify G 2 to obtain a graph G 3 such that the p-robot A is unable to explore G 3 , even with the pebble. G 3 contains O(K) 6-cycles of T , and thus has at most O(K 3 ) nodes. The transformation from G 2 to G 3 is technical and very similar to the transformation used in [START_REF] Fraigniaud | Graph Exploration by a Finite Automaton[END_REF] and in [START_REF] Rollik | Automaten in planaren graphen[END_REF]. Thus we only sketch the construction of G 3 , skipping technical details. Since any p-robot cannot go from a 6-cycle to another 6-node cycle of G 2 without using the pebble, we define key steps as those for which the last time the p-robot leaves a 6-cycle with the pebble, go through a meta-edge, and enters another 6cycle with the pebble. Because the number of states is finite, A will eventually be twice in the same state at these key steps, at two nodes w and w . With the same technique as in [START_REF] Fraigniaud | Graph Exploration by a Finite Automaton[END_REF], we identify the nodes w and w . This leads to the graph G 3 with the desired properties, that is G 3 has O(K) 6-cycles, and thus O(K) "parallel" edges. In each pair of "parallel" edges, there is a copy of G 1 . Since G 1 has O(K 2 ) nodes, then G 3 has O(K 3 ) nodes. Theorem 3. There exists an exploration with stop algorithm which requires O(D log ∆) bits of memory when performed in the family of graphs with diameter at most D and degree at most ∆.

Proof. We describe an algorithm called DFS-with-stop, that enables a robot to explore all graphs, with stop. Exploration is achieved by a traversal of the graph similar to DFS. Let u 0 be the initial position of the robot. The pebble is dropped at u 0 , and will remain there until exploration is completed. The exploration proceeds in a sequence of phases. At phase i ≥ 1, the robot performs a DFS at depth i. At any time during each phase the robot keeps in memory the current sequence of port numbers leading back to u 0 in the DFS tree. This takes O(i log ∆) bits of memory during phase i, in a graph of maximum degree ∆. At the beginning of Phase i, the robot sets the variable stop ← true. The robot traverses the edges incident to a node u in increasing order of their labels. When the robot leaves the current node u, and enters some node v, it proceeds as follows. If the pebble is at v, then the robot backtracks. Otherwise, if the current depth of the DFS is ≤ i -1, then the robot carries on the DFS traversal. If the current depth of the DFS is equal to i, then the robot checks whether v has already been visited or not during a previous phase. For that purpose, the robot performs an auxiliary DFS of depth i -1 from v. This again requires O(i log ∆) bits of memory for storing the sequence of port numbers leading back to v in the auxiliary DFS tree. If the robot finds the pebble during the execution of the auxiliary DFS, then v is at distance ≤ i-1 from u 0 , and thus it has already been explored during a previous phase. If the robot does not find the pebble during the execution of the auxiliary DFS from v, then it sets the variable stop ← f alse. After completion of the DFS at Phase i, the robot stops if and only if stop = true. Else, it carries on exploration, by starting Phase i + 1. Clearly, the robot stops after Phase D + 1 in a graph of diameter D. The memory requirement of this exploration algorithm is dominated by the storage of the sequences of port labels corresponding to two paths (one for the DFS, one for the auxiliary DFS). These paths are of length at most D + 1 in the family of graphs with diameter D, and thus contributes for O(D log ∆) when the degree of the graph is at most ∆.

Conclusions

We have proved that exploration with stop (using one pebble) requires Ω(log n) bits for the family of graphs with at most n nodes. In [START_REF] Fraigniaud | Graph Exploration by a Finite Automaton[END_REF], the same lower bound holds for perpetual exploration. In fact, [START_REF] Fraigniaud | Graph Exploration by a Finite Automaton[END_REF] proves that perpetual exploration requires Θ(D log ∆) for the family of graphs of diameter at most D and degree at most ∆. This latter result is obtained by proving that DFS-exploration is space-optimal. We thus ask the following question: is Ω(D log ∆) bits of memory required to explore with stop all graphs of diameter at most D and degree at most ∆?

Fig. 1 .

 1 Fig. 1. Basic step of the induction

H 2 Fig. 2 .

 22 Fig. 2. The gadget for connecting half-edges

  First, we have |H 2 | ≤ |G q | + K + O(1). Moreover, there are at most one halfedge pending from every added node in H 2 . For each pair of pending half-edges, we added four nodes, and thus |H 3 | ≤ |H 2 | + 2K + O(1). Finally, the tower has 2K + O(1) nodes and thus |H 4 | ≤ |G q | + 5K + O(1). The same procedure for the starting node u contributes to another 5K + O(1) additional nodes. The result follows.

Fig. 4 .

 4 Fig. 4. The graph G1

Fig. 5 .

 5 Fig. 5. The modified infinite tree T

The Õ notation hides logarithmic factors.

Since the {u, u } edges are "open", the proof requires to consider the last time the p-robot is in a u node; this is deferred to the full version of the paper.


Dr Pierre-André Jarrot

Edwige Tellier

Léa Plantureux

Lydie Crescence

Stéphane Robert

Corinne Chareyre

Laurent Daniel

Véronique Secq

Stephane Garcia

Francoise Dignat-George

Lea Plantureux

Stéphane Garcia

Françoise Dignat-George

Laurence Panicot-Dubois

Christophe Dubois

Gilles Kaplanski

/ Pr

Neutrophil extracellular traps are associated with the pathogenesis of diffuse alveolar hemorrhage in murine lupus

Keywords: Neutrophil extracellular traps, Deoxyribonuclease-1, Diffuse alveolar hemorrhage, Murine model, Systemic lupus erythematosus Highlights

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Diffuse alveolar hemorrhage (DAH) is defined by the presence of red blood cells originating from the lung capillaries or veins in the alveoli, often leading to acute respiratory failure, and constitutes a therapeutic emergency [START_REF] Lara | Diffuse alveolar hemorrhage[END_REF]. The prognosis is poor with a 20% mortality rate due to limited therapeutic options [START_REF] Gallagher | Pulmonary renal syndrome: a 4-year, singlecenter experience[END_REF][START_REF] Zamora | Diffuse alveolar hemorrhage and systemic lupus erythematosus. Clinical presentation, histology, survival, and outcome[END_REF]. The diagnosis is based on clinical features (haemoptysis, dyspnoea), anaemia, radiological patterns and, most importantly, examination of bronchoalveolar lavage. Although there are many underlying causes, autoimmune diseases such as systemic lupus erythematosus (SLE), antineutrophil-cytoplasmic antibody (Ab) (ANCA)-associated vasculitis and antiglomerular basement membrane Ab disease account for 35% of all causes and constitute the main aetiologies [START_REF] De Prost | Diffuse alveolar hemorrhage in immunocompetent patients: etiologies and prognosis revisited[END_REF]. Histopathologically, in addition to the presence of haemosiderin-laden macrophages and bland hemorrhage, interstitial infiltrates consisting of polymorphonuclear neutrophils (PMNs), which constitute pulmonary capillaritis and subsequent necrotizing vasculitis, are commonly observed [START_REF] Colby | Pathologic approach to pulmonary hemorrhage[END_REF]. Activated PMNs have been described to produce neutrophil extracellular traps (NETs), primarily through a cell-death process distinct from apoptosis and necrosis, termed NETosis.

NETs are composed of chromatin filaments coated with histones, proteases, granular and cytosolic proteins [START_REF] Brinkmann | Neutrophil extracellular traps in the second decade[END_REF]. Although NETs were previously described for their antibacterial properties due to the trapping and killing of extracellular pathogens in blood and tissue during infection, they have also been reported to play a detrimental role in acute lung injury, SLE and ANCA-associated vasculitis [START_REF] Porto | Neutrophil extracellular traps in pulmonary diseases: too much of a good thing?[END_REF][START_REF] Apel | The role of neutrophil extracellular traps in rheumatic diseases[END_REF]. NETs have been detected in the lungs during transfusion-related acute lung injury, an immune process related to DAH and shown to play a direct role in lung injury. In addition, treatment with deoxyribonuclease-1 (DNase-1), known to disrupt the NETs scaffold, has been shown to be beneficial in a murine model of transfusion-related acute lung injury [START_REF] Caudrillier | Platelets induce neutrophil extracellular traps in transfusion-related acute lung injury[END_REF][START_REF] Thomas | Extracellular DNA traps are associated with the pathogenesis of TRALI in humans and mice[END_REF].

In the first 15 days after intraperitoneal (IP) injection, C57BL/6 mice with pristane-induced SLE develop massive DAH, which is characterized by capillaritis, hemorrhage and endothelial injury [START_REF] Chowdhary | Characterization of haemorrhagic pulmonary capillaritis: another manifestation of pristane-induced lupus[END_REF][START_REF] Satoh | Fas and Fas ligand mutations inhibit autoantibody production in pristane-induced lupus[END_REF]. Previous studies have shown that pristane can induce the recruitment of PMNs into the peritoneal cavity with the subsequent development of chronic peritonitis [START_REF] Zhuang | Pathogenesis of diffuse alveolar hemorrhage in murine lupus[END_REF][START_REF] Herman | Cell death and cytokine production induced by autoimmunogenic hydrocarbon oils[END_REF][START_REF] Lee | IL-1alpha modulates neutrophil recruitment in chronic inflammation induced by hydrocarbon oil[END_REF]. Although PMN recruitment has also been reported in the lungs of animals with pristane-induced DAH, their role in the pathogenesis of DAH is unclear.

The present study was carried out to determine whether NETs were formed in the lungs of mice with pristane-induced DAH and contributed to lung injury. Such NETs could be a potential therapeutic target using recombinant human DNase-1 (Rh-DNase-1), also known as dornase alpha (Pulmozyme®), a well-known mucolytic drug commonly used in patients with cystic fibrosis [START_REF] Yang | Dornase alfa for cystic fibrosis[END_REF].

Material and methods

Mice

Wild-type C57BL/6 JRj (B6) mice were purchased from Elevage Janvier (Le Genest-Saint-Isle, France). All experimental procedures were performed in 8-to 12-week-old male mice housed under specific pathogen-free conditions in the laboratory animal facility. All animal care and experimental procedures were performed according to European Community Guidelines (directive 2010/63/UE) and approved by the Marseille Ethics Committee #14 (protocol number: 2015113014168292-V4 #2934).

Isolation of mouse PMNs

PMNs were isolated from the bone marrow of B6 mice as described previously using PE (phycoerythrin)-coupled magnetic microbeads and PE anti-Ly6G Ab (3 µg/mL; Miltenyi Biotec, Paris, France) [START_REF] Swamydas | Isolation of mouse neutrophils[END_REF]. Briefly, the bone marrow was flushed out of the tibia and femur using phosphate-buffered calcium-free saline (PBS-/-) (Thermofischer, Villebon sur Yvette, France) supplemented with 0.5% bovine serum albumin (BSA) and EDTA (2 mM) (Sigma-Aldrich, Saint-Quentin-Fallavier, France), passed through a 70-µm cell trainer to obtain a single cell solution and centrifuged at 300g for 8 min. The pellet was resuspended in PBS-/-, 0.5% BSA and 2 mM EDTA, stained with PE anti-Ly6G Ab for 10 min in the dark at 4°C and completed with anti-PE microbeads for 15 min in the dark at 4°C. Positive immune-magnetic separation of PMNs was performed using LS columns (Miltenyi Biotec, Paris, France). Cells were then washed and resuspended in Hanks balanced salt solution containing calcium (HKS+/+) (Thermofischer, Villebon sur Yvette, France). PMN count was determined using Kova slides (Jeulin, Evreux, France) and viability (>90%) was assessed using the trypan blue (Sigma-Aldrich, Saint-Quentin-Fallavier, France) exclusion method. PMN purity was routinely >98%, as assessed by flow cytometry using PE anti-Ly6G Ab staining.

In vitro NETs experiments

After isolation, PMNs (5 x 10 5 ) were allowed to adhere to poly-L-lysine (Sigma-Aldrich, Saint-Quentin Fallavier, France) coated slides in a 24-well plate at 37°C and 5% CO2 for 30 min. The attached PMNs were incubated with various stimuli at 37°C, 5% CO2 for 180 min. Some experiments were performed with the addition of Rh-DNase-1 (dornase alpha; Pulmozyme ® , 2500 U/2.5 mL (1 mg/mL), purity >97%; Roche, ATC: R05C B13, Boulogne-Billancourt, France), at a concentration of 2 µg/ml for 10 min (at the end of stimulation).

Platelet activating factor (PAF; Calbiochem, Molsheim, France) at a concentration of 10 µM was used as a positive control for NETs formation [START_REF] Farley | A serpinB1 regulatory mechanism is essential for restricting neutrophil extracellular trap generation[END_REF]. Pristane was either applied directly (2 min) or as a complex with β-cyclodextrin (β-CD) (Sigma-Aldrich, Saint-Quentin Fallavier, France). All experiments were performed in HKS+/+ (without any media supplements). For formation of complexes, a 4 mM solution of β-CD was mixed with pristane (2 mM final concentration) and stirred for 4 days at room temperature, as described previously [START_REF] Janz | A new method for delivering alkanes to mammalian cells: preparation and preliminary characterization of an inclusion complex between betacyclodextrin and pristane (2,6,10,14-tetramethylpentadecane)[END_REF]. All complexes were prediluted at 1/150 in HKS+/+, which was considered as concentration 1 (C1=13.3 µM). After stimulation, the cells were fixed with 4% paraformaldehyde (Sigma-Aldrich, Saint-Quentin Fallavier, France) before washing 3 times with PBS-/-and blocked with 3% BSA for immunofluorescence (IF) staining. Cells were then incubated overnight at 4°C in the dark with an anti-murine histone 3 rabbit polyclonal Ab (citrulline residues R2, R8, R17) (H3Cit) (ab5103, 10 µg/mL) or with an anti-murine neutrophil elastase (NE) rabbit polyclonal Ab (ab21595, 25 µg/mL), both purchased from Abcam (Paris, France). After washing three times with PBS-/-, a secondary rabbit-specific polyclonal Ab conjugated with 488-Alexa Fluor Dyes (Invitrogen, Villebon sur Yvette, France) was added to cells and incubated in the dark for 1 h at 37°C. Specificity of primary Ab staining was determined with a control rabbit irrelevant Ab (Sigma-Aldrich, R9133, lot SLB7964V, Saint-Quentin Fallavier, France). DNA was stained using Hoechst 33342 (Molecular Probes, Villebon sur Yvette, France) and the cells were mounted in fluoromount-G TM medium (eBioscience SAS, Paris, France) for imaging with a Leica Microsystem DMi8 microscope (Nanterre, France).

The image files were analysed with Image J 1.49v software (National Institutes of Health, USA).

In vitro NETs formation was quantified using a modified method reported previously [START_REF] Carmona-Rivera | Induction and quantification of NETosis[END_REF].

Briefly, using the x10 objective, the percentage of PMNs releasing NETs was quantified in blinded samples by evaluating PMNs releasing DNA fibres with NE or H3Cit co-staining.

NETs percentage was calculated as follows: NETs-rate (%) = 100 x number of PMNs releasing DNA fibres with NE or H3Cit co-staining/total number of PMNs. Quantification was performed using two delimited standardised plots using at least five random microscopic fields per condition.

Pristane-induced DAH model

Mice received a single IP injection of 0.5 ml synthetic sterile-filtered liquid pristane (Sigma-Aldrich, Saint-Quentin Fallavier, France). In order to avoid any non-specific stimulation of peritoneal cells by calcium, control mice received a 0.5 mL PBS-/-IP injection [START_REF] Mangold | Phosphate buffered saline containing calcium and magnesium elicits increased secretion of interleukin-1 receptor antagonist[END_REF]. Mice were weighed every day. Their lungs and blood were harvested on day 14 for pathological investigations except for mice included in the survival assay.

Recombinant human DNase-1 inhalation therapy

All mice received the same protocol of Rh-DNase-1 (Pulmozyme ® ) inhalations (0.8 mg/inhalation, once a day until day 9, then three times a day from day 10) in a special inhalation chamber (size 7.5" L x 5.5'' W x 4'' H, 39481051; Leica, Nanterre, France) using a Stratos Pro inhaler (Invacare, Fondettes, France). Control mice received 0.9% NaCl inhalations, following the same protocol as for Rh-DNase-1 therapy.

In vivo PMN depletion

PMNs were depleted in vivo by treating mice with Ultra-LEAF ™ purified anti-mouse Ly6G Ab clone 1A8 (Biolegend, Saint Quentin en Yvelines, France) using one IP injection (170 µg/mouse) the day before and every other day after IP pristane injection, until day 14 [START_REF] Daley | Use of Ly6Gspecific monoclonal antibody to deplete neutrophils in mice[END_REF][START_REF] Bruhn | Ly6Gmediated depletion of neutrophils is dependent on macrophages[END_REF].

PMN depletion was assessed by flow cytometry after staining with anti-CD45 efluor780, anti-CD11b-APC (ebioscience™, Villebon sur Yvette, France) and anti-PE-Ly6G (Miltenyi Biotec, Paris, France).

Pathological investigations

Mice were euthanized on day 14 and their lung tissue was harvested immediately after death.

The left lobes were fixed overnight in 10% buffered formalin (Sigma-Aldrich, Saint-Quentin Fallavier, France) and embedded in paraffin. The right lobes were frozen with optimal cutting temperature (OCT) compound (Sigma-Aldrich, Saint-Quentin Fallavier, France). Paraffinembedded sections were cut into 5 µm sections and stained with haematoxylin-eosin (H&E) (Sigma-Aldrich, Saint-Quentin Fallavier, France). The extent of pulmonary hemorrhage was assessed using quantification program CaloPix ® software (TRIBVN Healthcare, Chatillon, France), which is a digital slide and management software. Two blinded pathologists assessed the extent of DAH. Total, white (no tissue) and healthy areas were defined numerically at x20 magnification. Two standardised slides of each left lung were analysed. The extent of DAH was calculated as follows: DAH (%) = 100 -(healthy area / (total -white area) x 100.

OCT-embedded frozen lung lobes were cut into 5 µm sections and fixed with acetone (10 min). After washing three times with PBS-/-, slides were blocked with 3% BSA. Sections were then incubated with 0.3 µg/mL PE-anti-Ly6G Ab (Miltenyi Biotec, Paris, France), anti-H3Cit (30 µg/mL) or anti-NE rabbit (50 µg/mL) polyclonal Ab overnight at 4°C. Sections were then washed and incubated with secondary rabbit-specific polyclonal Ab conjugated with 649-Alexa Fluor Dyes (Invitrogen, Villebon sur Yvette, France) (dark, 1 h, 37°C). DNA was stained using Hoechst 33342 (Molecular Probes, Villebon sur Yvette, France). Sections were mounted in fluoromount-G TM medium (eBioscience SAS, Paris, France) for imaging microscopy.

Quantification of NE and H3Cit fluorescence was performed at x10 magnification in one random microscopic field of each lobe per mouse, followed by binary analysis using Image J 1.49v software (NIH, 2015). PMN count was assessed in the same microscopic field as NE and H3Cit staining.

Confocal laser scanning microscopy

The same histological samples were analysed using a Zeiss ® LSM 800 confocal microscope with Airyscan technology using a x63 oil immersion objective.

Pulse-oximetry assay

Real-time SpO 2 (percentage of functional arterial haemoglobin) was measured using a MouseOx pulse-oximeter (Starr Life Sciences, Oakmont, USA).

Statistical analysis

Data are representative of at least three independent experiments. Results are reported as both individual data points, mean ± standard deviation (SD). To determine statistical significance, the 2-tailed unpaired Student's t test was used for normally distributed data. Survival rates were compared using the log-rank (Mantel-Cox) test.

GraphPad Prism 5.0 software was used for all statistical analyses. P values <0.05 were considered statistically significant.

Results

Pristane promotes NETs formation in vitro

PMNs are considered to be key players in the initiation of inflammation involved in the development of haemorrhage-induced acute lung injury. Because a single IP injection of pristane is known to induce rapid PMN recruitment in the lungs, preceding DAH by a few days [START_REF] Abraham | Neutrophils as early immunologic effectors in hemorrhage-or endotoxemia-induced acute lung injury[END_REF][START_REF] Barker | Pathogenic role of B cells in the development of diffuse alveolar hemorrhage induced by pristane[END_REF], we tested whether this hydrocarbon oil could promote NETs formation in vitro.

Because of its extreme hydrophobicity, pristane was applied to murine PMNs, either directly or complexed with β-CD. β-CD is an oligomer of D-glucose with a hydrophobic cavity and a hydrophilic surface and complexes of pristane and β-CD have been shown to be effective at delivering pristane in vitro [START_REF] Janz | A new method for delivering alkanes to mammalian cells: preparation and preliminary characterization of an inclusion complex between betacyclodextrin and pristane (2,6,10,14-tetramethylpentadecane)[END_REF]. The dose of pristane chosen in our experiments was adjusted in accordance with a previous study [START_REF] Herman | Cell death and cytokine production induced by autoimmunogenic hydrocarbon oils[END_REF]. PAF-treated PMNs were used as a positive control for NETs formation. Different concentrations of β-CD-complexed pristane were tested (C1=13.3 µM, C1/10, C2 (C1x2)) and compared with the effect of PAF. NET formation was determined by the colocalization of DNA fibres, extracellular H3Cit proteins or NE [START_REF] Papayannopoulos | Neutrophil extracellular traps in immunity and disease[END_REF].

Using fluorescence microscopy, a significant increase in NETs formation was observed after incubation of PMNs with β-CD-complexed or directly applied pristane, in comparison with PMNs incubated with a control solution (Fig. 1A-D; P<0.001).

Pristane causes NETs formation in the lungs in vivo

We used a previously established in vivo model of pristane-induced DAH, whose hemorrhage started 3 days after pristane injection, peaked at 2 weeks and then resolved by 4 weeks in 70% of mice [START_REF] Barker | Pathogenic role of B cells in the development of diffuse alveolar hemorrhage induced by pristane[END_REF]. At day 15, the airspaces of the lungs of pristane-treated mice were filled with fresh haemorrhage and were heavily infiltrated with macrophages and PMNs compared with untreated animals (Supplemental Fig. 1A-B). The release of NE, H3Cit and number of PMNs (characterized by colocalization of Ly6G and DNA staining) were quantified in the lungs.

Significantly stronger NE and H3Cit staining and a higher number of PMNs were detected in the lungs of mice with pristane-induced DAH compared with the lungs of healthy controls (HC) (Fig. 2A-D, P<0.001). In addition, using confocal fluorescence microscopy, we observed diffuse DNA structures of irregular shape, which colocalized with Ly6G (corresponding to PMN membranes) and with NE or H3Cit staining, in favour of NETs (Fig. 2E,F). In agreement with these observations, in vivo depletion of PMNs using anti-Ly6G clone 1A8 monoclonal Ab prevented the appearance of PMNs, NE and H3Cit formation in the lungs of mice with pristane-induced DAH (Fig. 3A-D, P<0.001).

Taken together, these results suggest that a single IP injection of pristane caused NETs formation in the lungs of B6 mice.

Recombinant human DNase-1 disrupts NETs formation and attenuates lung injury in a pristane-induced DAH murine model

In order to determine whether NETs could serve as a therapeutic target in pristane-induced DAH we used Rh-DNase-1, which is known to catalyse the hydrolysis of the NETs backbone structure. It was confirmed in vitro that pristane-induced NETs could be dismantled by Rh-DNase-1 (Supplemental Fig. 2, P<0.001). We then treated mice with inhalations of Rh-DNase-1, starting the day after IP pristane injection. Rh-DNase-1 treatment significantly reduced NE and H3Cit fluorescence staining in the lungs of mice with pristane-induced DAH compared with the lungs of untreated mice, and appeared comparable to the lungs of HC mice. Furthermore, a decrease in the PMN count in the lungs was observed after Rh-DNase-1 therapy (Fig. 4A-E, P<0.001).

In order to determine whether Rh-DNase-1 inhalation reduced acute hemorrhagic injury lesions, we quantified DAH lesions after H&E staining of lung sections. Rh-DNase-1 therapy significantly reduced DAH lesions compared with untreated animals (Fig. 5A-D, P<0.01).

Disruption of NETs improves the clinical status of mice with pristane-induced

DAH

Respiratory lung function was assessed in Rh-DNase-1-treated pristane-induced DAH mice.

Mice subjected to pristane-induced DAH had a significant decrease in mean arterial oxygen saturation compared to HC mice (pristane: 76.9% (± 6.9) vs. HC: 97.9% (± 0.8), P<0.001).

Rh-DNase-1 treated mice showed a significantly less important reduction in arterial oxygen saturation compared to untreated animals (Rh-DNase-1: 85.1% (± 6.9) vs. untreated: 76.9% (± 6.9); P<0.01, Fig. 5E). Although no difference in maximum weight loss was observed between the two groups, weight loss in Rh-DNase-1-treated mice was delayed compared to untreated animals (Fig. 5F, P<0.001). In addition, pristane-induced-DAH mice treated with Rh-DNase-1 inhalations had significantly decreased mortality at D30 compared with untreated animals (Rh-DNase-1: 35% vs. untreated: 63%, P<0.05, Fig. 5G). In agreement, PMN depletion using Ly6G Ab also reduced DAH lesions and improved arterial oxygen saturation in pristane-induced DAH compared to undepleted mice (Supplemental Fig. 3, P<0.05). Taken together, these results suggest that Rh-DNase-1 inhalation therapy clears NETs, attenuates pristane-induced DAH and improves clinical status in mice.

Discussion

NETs were initially described for their antibacterial properties, in which the release of chromatin associated with neutrophil granular proteins serves as an additional weapon for the innate immune system against circulating bacteria [START_REF] Brinkmann | Neutrophil extracellular traps kill bacteria[END_REF]. However, increasing evidence suggests that NETs may have a detrimental role in non-infectious diseases [START_REF] Papayannopoulos | Neutrophil extracellular traps in immunity and disease[END_REF]. More recently, NETs were shown to play a pathogenic role in transfusion-related acute lung injury, which is similar to autoimmune DAH in several ways [START_REF] Thomas | Extracellular DNA traps are associated with the pathogenesis of TRALI in humans and mice[END_REF]. Transfusion-related acute lung injury is caused by antineutrophil antibodies present in transfusion products, which induce PMN sequestration and activation in the lung capillaries, resulting in tissue injury. In a similar way, capillaritis is a hallmark of DAH and is present in 88% of patients, usually associated with fibrin thrombi and small blood vessel fibrinoid necrosis. The pathogenic mechanisms underlying DAH lesions are unclear. The present study suggests a pathogenic role of NETs in a murine model of DAH [START_REF] Park | Diffuse alveolar hemorrhage[END_REF][START_REF] Franks | Pulmonary capillaritis[END_REF].

Our pristane-induced DAH model is a limited organ disease and constitutes the first phase of pristane-induced SLE [START_REF] Chowdhary | Characterization of haemorrhagic pulmonary capillaritis: another manifestation of pristane-induced lupus[END_REF]. A recent study described morphological similarities between pristane-induced and SLE-associated DAH. However, no immune complex deposits were reported on endothelial cells or the alveolar basement membrane in the pristane model, suggesting another pathogenic mechanism. Thus a direct toxic effect of pristane could be proposed [START_REF] Chowdhary | Characterization of haemorrhagic pulmonary capillaritis: another manifestation of pristane-induced lupus[END_REF][START_REF] Zhuang | Pathogenesis of diffuse alveolar hemorrhage in murine lupus[END_REF]. Pristane is known to have adjuvant properties and is also considered to be an irritant with subsequent cell cytotoxicity leading to necrosis, suggesting a direct chemical process different from a solely autoimmune model [START_REF] Herman | Cell death and cytokine production induced by autoimmunogenic hydrocarbon oils[END_REF]. In addition, pristane-generated autoantibodies appeared 90 days after IP pristane injection making the indirect effect of pristane-induced autoantibody formation unlikely in this model [START_REF] Zhuang | Pathogenesis of diffuse alveolar hemorrhage in murine lupus[END_REF][START_REF] Freitas | Pristane-induced lupus: considerations on this experimental model[END_REF]. This does not exclude a role for pre-existing natural IgM reacting with apoptotic cells in the pathogenesis of this model [START_REF] Zhuang | Pathogenesis of diffuse alveolar hemorrhage in murine lupus[END_REF][START_REF] Freitas | Pristane-induced lupus: considerations on this experimental model[END_REF].

The role of PMNs in pristane-induced inflammation has been discussed previously. Previous studies showed that IP pristane injection induced chronic peritonitis due to PMN recruitment in the peritoneal cavity, which appeared partially dependent on IL-1α/IL-1R and CXCL5/CXCR2 signalling. Consistent with previous studies, we observed PMN recruitment in the lungs of mice with pristane-induced DAH [START_REF] Chowdhary | Characterization of haemorrhagic pulmonary capillaritis: another manifestation of pristane-induced lupus[END_REF]. Recently, a role for macrophages in the initiation of pristane-induced DAH has been reported with the presence of activated macrophage lung infiltration and a lower prevalence of DAH after macrophage (compared to PMN) depletion [START_REF] Zhuang | Pathogenesis of diffuse alveolar hemorrhage in murine lupus[END_REF]. Another study described the effective role of oxysterol-regulated transcription factor therapy in the prevention of pristane-induced DAH by repolarizing macrophages [START_REF] Han | Liver X receptor agonist therapy prevents diffuse alveolar hemorrhage in murine lupus by repolarizing macrophages[END_REF]. Without highlighting a role for macrophages, we observed less severe DAH lesions and improved clinical status after PMN depletion suggesting that PMNs may also participate in exacerbating DAH lesions.

Besides the well-known effect of pristane at inducing cell apoptosis in vitro and in vivo, our results show for the first time that pristane also promotes NETs generation in vitro [START_REF] Herman | Cell death and cytokine production induced by autoimmunogenic hydrocarbon oils[END_REF]. In accordance with 56% of previous studies, our in vitro NETs experiments were performed in the absence of exogenous serum sources since a recent study demonstrated that serum components such as BSA and foetal calf serum inhibit NETs formation. Thus the choice of media supplements greatly determines the propensity to form NETs [START_REF] Neubert | Serum and serum albumin inhibit in vitro formation of neutrophil extracellular traps (NETs)[END_REF]. We then observed NETs in the lungs of pristane-induced DAH. NETs have been previously reported in the lungs of infectious and noninfectious-related acute lung injury in mice by confocal or electron microscopy, but they remain difficult to characterise in vivo due to their structural fragility and tissue biopsy preparation methods [START_REF] Porto | Neutrophil extracellular traps in pulmonary diseases: too much of a good thing?[END_REF][START_REF] Thomas | Extracellular DNA traps are associated with the pathogenesis of TRALI in humans and mice[END_REF][START_REF] Onouchi | Visualization of neutrophil extracellular traps and fibrin meshwork in human fibrinopurulent inflammatory lesions: II. Ultrastructural study[END_REF]. In our model, we demonstrated the presence of NETs by showing widespread DNA backbone structures with co-localization of NE and CitH3, in close association with PMN membranes, as revealed by IF staining. Indeed, during NETosis, NE is rapidly translocated from azurophil granules into the nucleus where it proteolitically processes histones to disrupt chromatin packaging and is then released into the extracellular space, some portions remaining bound to the PMN plasma membrane [START_REF] Papayannopoulos | Neutrophil extracellular traps in immunity and disease[END_REF].

Histone citrullination catalysed by peptidylarginine deiminase-4, an enzyme prominently found in granulocytes, has also been shown to be a crucial step for PMN chromatin decondensation leading to NETs formation [START_REF] Claushuis | Role of peptidylarginine deiminase 4 in neutrophil extracellular trap formation and host defense during Klebsiella pneumoniae-induced pneumonia-derived sepsis[END_REF]. Because reactive oxygen species generation actively participates in NETosis, we considered that pristane triggered PMN activation ultimately leads to NETs generation [START_REF] Kienhofer | Experimental lupus is aggravated in mouse strains with impaired induction of neutrophil extracellular traps[END_REF]. Interestingly, a recent mass spectrometry study reported four characteristic peaks of pristane in the lungs and bone marrow of mice during pristane-induced DAH, suggesting wide dispersion of pristane after IP injection [START_REF] Zhuang | Pathogenesis of diffuse alveolar hemorrhage in murine lupus[END_REF].

Together, these results indicate that the pristane-induced DAH model can be considered as a pulmonary model of NETosis. Furthermore, by disrupting the NETs scaffold using Rh-DNase-1 we demonstrated a pathogenic role of NETs in this DAH model. Targeting NETs was effective at clearing the pulmonary NETs component, with a subsequent reduction in histopathological lung injury.

Moreover, the clinical status of the mice improved, with a remarkable increase in arterial oxygen saturation and reduced mortality. Rh-DNase-1 is a well-known mucolytic therapy widely used in cystic fibrosis. Rh-DNase acts via disruption of extracellular DNA which interferes with mucociliary clearance, thereby reducing the rate of infectious respiratory exacerbations [START_REF] Yang | Dornase alfa for cystic fibrosis[END_REF]. Interestingly, as mentioned by the Food and Drug Administration, side effects are rare, moderate and transient. A recent Cochrane database review reported an increased risk of rash (RR=2.40 [95%CI: 1.16-4.99]), voice alteration (RR=1.34 [95%CI: 0.64-2.78) and, to a lesser extent, cough and conjunctivitis. To date, no severe adverse events have been described [START_REF] Yang | Dornase alfa for cystic fibrosis[END_REF]. Recently, a pilot study was conducted using adjuvant inhalation of Rh-DNase-1 for the treatment of acquired ventilator-associated infection in preterm infants. This treatment was safe and effective and led to arterial oxygenation improvement [START_REF] Scala | Pilot study of dornase alfa (Pulmozyme) therapy for acquired ventilator-associated infection in preterm infants[END_REF].

Following animal studies of transfusion-related acute lung injury, infectious acute lung injury or primary graft dysfunction after lung transplantation, our study is the first to demonstrate the beneficial effect of intrapulmonary Rh-DNase-1-induced NETs disruption during pristaneinduced DAH [START_REF] Thomas | Extracellular DNA traps are associated with the pathogenesis of TRALI in humans and mice[END_REF][START_REF] Sercundes | Targeting neutrophils to prevent malaria-associated acute lung injury/acute respiratory distress syndrome in mice[END_REF][START_REF] Sayah | Neutrophil extracellular traps are pathogenic in primary graft dysfunction after lung transplantation[END_REF]. The strength of our study is the fact that in contrast to previous studies, which used intravenous or intranasal injections, we treated mice using aerosol inhalation of Rh-DNase-1 in order to mimic human clinical practice. Thus, our data clearly suggest that therapy disrupting the DNA scaffold in pristane-induced DAH is effective and could be interesting as adjuvant therapy in human autoimmune DAH.

Conclusion

Our data suggest a pathogenic role PMNs and NETs in lung injury during pristane-induced DAH. Targeting NETs with Rh-DNase-1 inhalations could be an interesting adjuvant therapy in human DAH.

Figure 1 .

 1 Figure 1. Pristane-induced neutrophil extracellular traps (NETs) generation in vitro.

Figure 2 .

 2 Figure 2. Neutrophil extracellular traps (NETs) formation in the lungs of mice with

Figure 3 .

 3 Figure 3. Depletion of PMNs prevents neutrophil extracellular traps (NETs) generation.

Figure 4 .

 4 Figure 4. Recombinant human DNase-1 inhalation therapy disrupts neutrophil

Figure 5 .

 5 Figure 5. Recombinant human DNase-1 inhalation therapy reduces lesions of acute lung

Figure 5 P

 5 Figure 1

Acknowledgements

This study was supported by the "Société Nationale Française de Médecine Interne" (SNFMI), "CSL Behring", "Groupe Pasteur Mutualité" (GPM) and "Bureau des PUPH de Marseille".

Funding

This research did not receive any specific grant from funding agencies in the public, commercial, or not-for-profit sectors.