Alberto Dennunzio
email: dennunzio@disco.unimib.it

Enrico Formenti
email: enrico.formenti@unice.fr

Luca Manzoni
email: luca.manzoni@disco.unimib.it

Antonio Enrico Porreca
email: antonio.porreca@lis-lab.fr

Complexity of the dynamics of reaction systems

Keywords: reaction systems, computational complexity, natural computing, discrete dynamical systems

à la diffusion 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

Reaction systems (RS) are a computational model of natural computing recently introduced by Ehrenfeucht and Rozenberg [START_REF] Ehrenfeucht | Reaction systems[END_REF] which is inspired by chemical reactions (for recent results and an up-to-date bibliography on RS see [START_REF] Azimi | Complexity of model checking for reaction systems[END_REF][START_REF] Nobile | Efficient simulation of reaction systems on Graphics Processing Units[END_REF][START_REF] Corolli | An excursion in reaction systems: From computer science to biology[END_REF][START_REF] Azimi | Reaction system models for the heat shock response[END_REF][START_REF] Barbuti | Investigating dynamic causalities in reaction systems[END_REF], while for other models of natural computing see for instance [START_REF] Cattaneo | Non-uniform cellular automata[END_REF][START_REF] Dennunzio | From one-dimensional to two-dimensional cellular automata[END_REF][START_REF] Acerbi | Shifting and lifting of cellular automata[END_REF][START_REF] Dennunzio | Stable dynamics of sand automata[END_REF][START_REF] Cattaneo | A full cellular automaton to simulate predator-prey systems[END_REF][START_REF] Dennunzio | Periodic orbits and dynamical complexity in cellular automata[END_REF][START_REF] Acerbi | Surjective multidimensional cellular automata are non-wandering: A combinatorial proof[END_REF][START_REF] Dennunzio | Local rule distributions, language complexity and non-uniform cellular automata[END_REF][START_REF] Dennunzio | On the dynamical behaviour of linear higher-order cellular automata and its decidability[END_REF]). Roughly speaking, a RS is made of a finite set of entities (molecules of substances) and a finite set of rules (reactions). Entities are used as reactants, inhibitors, and products of a reaction. If, among a current set of entities (state), the reactants of a given reaction are available and there are no inhibitors, then that reaction takes place, i.e., the products of the considered reaction are generated. The collection of the products of all enabled reactions give the new state of the system. In fact, this framework therefore captures the fundamental mechanisms of facilitation and inhibition on which biochemical reactions are based. Further, the functioning of the model undergoes two important principles, namely, the threshold assumption and the non-permanency assumption. The first one means that if a resource is available then there is always a sufficient amount of it for all the reactions which can take place. In other terms, reactions needing the same resource do not come into conflict. This principle essentially defines RS as a qualitative model (i.e., only the presence or absence of a substance is measured). The latter assumption imposes that an entity will disappear from the current state of the system if no enabled reaction will have produced it.

Thus, RS are very different from the standard frameworks for biomodelling such as, for instance, ordinary differential equations and continuous stochastic process. However, it has been recently shown that they are able to capture the main quantitative characteristics of the ODE-based model for biochemical processes. In [START_REF] Azimi | Reaction system models for the heat shock response[END_REF], for instance, they show how to build a RS reproducing the quantitative behavior of the ODE model for the molecular heat shock response. Another important aspect in the RS framework is that, differently than in the traditional models, one is able to follow the cause-effect relations between reactions, allowing for instance to understand what led a reaction to take place.

As consequence of these facts and the capability of RS to capture the main mechanisms of biochemical reactions, the interest and use of RS to study practical problems concerning biological and/or chemical processes has grown since their introduction. Some biological uses were first detailed in [START_REF] Corolli | An excursion in reaction systems: From computer science to biology[END_REF]. Successively the study of the cell heat-shock response was carried on in [START_REF] Azimi | Reaction system models for the heat shock response[END_REF]. Recently, RS has been used to simulate a complex real-world biological model [START_REF] Nobile | Efficient simulation of reaction systems on Graphics Processing Units[END_REF], namely, the ErbB model described in [START_REF] Helikar | A comprehensive, multi-scale dynamical model of ErbB receptor signal transduction in human mammary epithelial cells[END_REF]. Finally, a model of the gene regulatory network of the Yeast-Cell cycle was detailed in [START_REF] Barbuti | Simulating gene regulatory networks using reaction systems[END_REF].

The study of the dynamical properties of the model at hand is a central question in the context of modelling. When considering RS as a model, this question might seem trivial at a first glance. Indeed, RS are finite systems and, as such, their dynamics is ultimately periodic. However, in practical applications this information is pointless and a more detailed analysis is expected. For example, in the context of genetic modelling, the number of attractors can be associated with cell differentiation [START_REF] Shmulevich | From Boolean to probabilistic Boolean networks as models of genetic regulatory networks[END_REF], the period of attractors may represent the period of life process (respiration, circadian cycle, etc.), the size of the basin of attraction can be associated with the robustness in complex biological systems [START_REF] Kitano | Biological robustness[END_REF]. The analysis can be pushed even further considering limited resources [START_REF] Ehrenfeucht | Functions defined by reaction systems[END_REF][START_REF] Dennunzio | Reachability in resource-bounded reaction systems[END_REF].

In [START_REF] Ehrenfeucht | Combinatorics of life and death for reaction systems[END_REF], they considered some particular state as a death state (the empty set in this case) and computed the probability of a system reaching the death state. The study of dynamic causality relations was also explored in [START_REF] Barbuti | Investigating dynamic causalities in reaction systems[END_REF][START_REF] Barbuti | Specialized predictor for reaction systems with context properties[END_REF]. Other studies focused on the complexity of deciding if any given RS exhibits a certain dynamical behaviour as, for instance, the appearance of a specific product during the evolution [START_REF] Salomaa | Minimal and almost minimal reaction systems[END_REF][START_REF] Salomaa | Functional constructions between reaction systems and propositional logic[END_REF].

This paper pursues the seminal results in [START_REF] Ehrenfeucht | Reaction systems[END_REF][START_REF] Salomaa | Minimal and almost minimal reaction systems[END_REF][START_REF] Salomaa | Functional constructions between reaction systems and propositional logic[END_REF][START_REF] Formenti | On the complexity of occurrence and convergence problems in reaction systems[END_REF][START_REF] Dennunzio | Ancestors, descendants, and gardens of eden in reaction systems[END_REF][START_REF] Dennunzio | Reaction systems and extremal combinatorics properties[END_REF][START_REF] Azimi | Complexity of model checking for reaction systems[END_REF] about the dynamical behavior of RS. The purpose is to cover a broad range of questions involving cycles, attractors and reachability, providing in this way a reference list for them. Several results are stated in a form which is as wide as possible (including constraints as "at least" and "at most") in order to answer the different variants/formulations of a same problem which arise in practical situations. Remark that similar problems are studied also in the context of other models used for applications, as, for instance, Boolean Automata Networks and Cellular Automata [START_REF] Sutner | On the computational complexity of finite cellular automata[END_REF][START_REF] Dennunzio | Computational complexity of finite asynchronous cellular automata[END_REF][START_REF] Dennunzio | Computing issues of asynchronous CA[END_REF][START_REF] Dennunzio | m-asynchronous cellular automata: from fairness to quasi-fairness[END_REF].

The first group of results concern the complexity of the decision problems about various forms of reachability under the action of a RS. We provide the complexity of establishing if

• a state T leads to a state U in at most k steps (P-complete, Theorem 4)

• a state T leads to a state U (PSPACE-complete, Theorem 18)

• a state T leads to a cycle of length at most after at most k steps (P-complete, Theorem 6) or after at least k steps (PSPACE-complete, Theorem 21)

• there exists a state T leading to a cycle of length at most after at least k steps (NP-complete, Theorem 11),

• a state T leads to a cycle of length at least after at least k steps (PSPACE-complete, Theorem 21) or if such a state exists (PSPACE-complete, Theorem 20),

• a state T is reachable from some other state in k steps (NP-complete, Theorem 10).

• a state T is periodic of period at most and reachable from some other ultimately periodic state having a pre-period of length at least k (NP-complete, Theorem 9)

As to problems involving cycles, we deal with the complexity of determining if

• a state T belongs to a cycle of length at most (P-complete, Theorem 5)

• there exists a cycle of length at most (NP-complete in both the versions with "for each " in the statement and with given as input, Theorems 7 and 8)

• there exists a cycle of length at least (PSPACE-complete, Theorem 19)

• the given RS consists of cycles possibly all of length 1 (coNP-complete, Theorems 12 and 13)

Concerning the attractors, we study the complexity of deciding if • there exists a global attractor cycle of length at most /at least (PSPACE-complete, Theorem 22) Some proofs of our results exploit the idea that RS can be used to evaluate Boolean formulae [START_REF] Ehrenfeucht | Reaction systems[END_REF] and are based on reductions from problems over the latter. Other ones consist of reductions from different halting problems over deterministic Turing machines with bounded tape. Indeed, as described in Section 3, the computations of such machines can be simulated by suitable RS. Finally, direct reductions from the problems considered in this paper allow to prove the remaining results.

The paper is structured as follows. Section 2 provides the basic notions on RS and Section 3 illustrates the construction of a RS simulating a Turing machine with bounded tape. The results regarding reachability issues, cycles and attractors appear in the three Sections 4, 5, and 6, depending on the complexity degree of the involved problems. Indeed, this allows a certain uniformity of proof techniques and to factor some parts or ideas. Section 7 provides a recap of the results and discusses possible future developments.

Basic notions

This section provides all the basic concepts about RS and those notions about dynamical systems which will be considered in the paper. Notations are taken from [START_REF] Ehrenfeucht | Reaction systems[END_REF].

Let S be a finite set and let its elements be called entities. Denote by 2 S the power set of S.

Definition 1.

A reaction a over S is a triple (R a , I a , P a ), where R a , I a and P a are subsets of S called the set of reactants, the set of inhibitors, and the of products, respectively. The collection of all reactions over S is denoted by rac(S).

Definition 2. A reaction system A is a pair (S, A) where S is a finite set, called the background set, and A ⊆ rac(S). Every subset of the background set of A is said to be a state.

Remark that R and I are allowed to be empty as in the original definition of RS from [START_REF] Ehrenfeucht | Reaction systems[END_REF]. Another option, not used here, is to assume the non emptiness of these two sets, as done later in [START_REF] Ehrenfeucht | Combinatorics of life and death for reaction systems[END_REF][START_REF] Ehrenfeucht | Functions defined by reaction systems[END_REF], for instance. We want to stress that the essence of our results does not change at all in the non emptiness setting, while our choice allows a more elegant formulation of the results.

For any state T ⊆ S and any reaction a ∈ rac(S), a is said to be enabled in T if R a ⊆ T and I a ∩ T = ∅. The result function res a : 2 S → 2 S of a is defined as

∀T ⊆ S, res a (T ) = P a if a is enabled in T ∅ otherwise.
The definition of res a naturally extends to sets of reactions. Indeed, given a set of reaction B ⊆ rac(S), define res B : 2 S → 2 S as res B (T ) = a∈B res a (T ) for every T ⊆ S. The result function res A of a RS A = (S, A) is res A . In this way, the discrete dynamical system with the set of states 2 S and the next state map res A is associated with the RS A = (S, A). The following is an example of a simple RS which is able to simulate a NAND gate.

Example 3 (NAND gate).

To implement a NAND gate using a RS we use S = {0 a , 1 a , 0 b , 1 b , 0 out , 1 out } as background set. The first four elements represent the two inputs (denoted by the subscripts a and b), the last two, on the other hand, denote the two possible outputs. The reactions used to model a NAND gate are the following:

({0 a , 0 b }, ∅, {1 out }), ({0 a , 1 b }, ∅, {1 out }), ({1 a , 0 b }, ∅, {1 out })
, and ({1 a , 1 b }, ∅, {0 out }). Similarly to NAND gates, others gates can be simulated and it is possible to build circuits with gates of limited fan-in using only a number of entities and reactions that is linear in the size of the modelled circuit. , q 2 } of M where each tape symbol is subscripted with its own position, while the current state of M is subscripted with the position of the head. The square represents the blank symbol.

We now proceed by recalling the necessary definitions of the dynamical properties investigated in this work.

Let A = (S, A) be a RS. For any given state T ⊆ S, the dynamical evolution or dynamics of A starting from T is the sequence (T, res A (T ), res 2 A (T ), . . .) of states visited by the system starting from T , i.e., the sequence in which for every i ∈ the i-th element is res i A (T ). We say that T leads to a state U in t steps if U = res t A (T ). In that case, T is said to be a t-ancestor of U. We simply say that T leads to U if T leads to a state U in t steps, for some t ∈ . Since 2 S is finite, any of the above sequences is ultimately periodic, i.e., there exist two integers h ∈ and k > 0 such that res h+k A (T ) = res h A (T ). Notice that, since res A is a function, this also implies that for all i ≥ 0, res h+k+i A (T ) = res h+i A (T ). The smallest values of h and k for which this condition holds are called preperiod and period of T , respectively. If h = 0, T is a periodic point and the set {T, res A (T ), . . . , res k-1 A (T )} is said to be a cycle (of length k). We say that a periodic point T is a

fixed point if k = 1.
The notion of attractor is a central concept in the study of dynamical systems. Recall that an invariant set for

A is a set of states U with res A (U) = {res A (U) : U ∈ U} = U. Remark that each invariant set of any RS consists of cycles. A local attractor in a RS is an invariant set U such that there exists T / ∈ U with res A (T ) ∈ U. Intuitively, a local attractor is a set of states U from which the dynamics never escapes and such that there exists at least one external state whose dynamics ends up in U. For example, if {T } is an invariant set (i.e., res A (T ) = T ) and there exists U = T such that res A (U) = T , then {T } is an attractor. A global attractor for an RS A is an invariant set of states U such that for all T ∈ 2 S there exists t ∈ such that res t A (T ) ∈ U. A local/global attractor U is a local/global fixed-point attractor if U = {T } and hence, necessarily, T is a fixed point. Similarly, we call a local/global attractor U a local/global attractor cycle if all the states in U belong to the same cycle. The attraction basin of a local/global attractor U is the set of all states whose dynamics ends up in U. The maximum value of all the preperiods of such states is called the diameter of U.

Simulating Turing machines with bounded tape

In this section we illustrate the simulation of Turing machines with bounded tape performed by RSs. For an introduction, basic results, and notions on Turing machines, we refer the reader to [START_REF] Hopcroft | Introduction to Automata Theory, Languages, and Computation[END_REF].

Let M be any single-tape deterministic Turing machine with tape of length m, set of states Q, tape alphabet Σ, and transition function δ

: Q × Σ → Q × Σ × {-1, 0, +1}.
The computations of M can be simulated by the reaction system M = (S, A) defined as follows.

Entities. The set of entities of M is

S = {a i : a ∈ Σ, 1 ≤ i ≤ m} ∪ {q i : q ∈ Q, 1 ≤ i ≤ m + 1}
that is, S consists of all symbols of the alphabet and all states of M , each of them indexed by every possible tape position (with the additional position m + 1 for the states, too).

The generic configuration where M is in state q ∈ Q, its tape head is located on cell i, and its tape consists of the string

x = x 1 • • • x m , is encoded as the following state T = {(x j ) j : 1 ≤ j ≤ m} ∪ {q i }
In other terms, T contains each symbol of x indexed by its position on the tape and the entity q i (state entity) storing both the current state and the head position of M (see Fig. 1).

Reactions. We are going to illustrate the elements of the set A. Each transition δ(q, a) = (q , a , d) of M , with q, q ∈ Q, a, a ∈ Σ, and d ∈ {-1, 0, 1}, gives rise to the following set of reactions:

({q i , a i }, ∅, {q i+d , a i }) for 1 ≤ i ≤ m; (1)
If the head of M is located on the cell i of the tape, then the i-th reaction simulates the action of δ, by producing the entity encoding both the new state and the new head position of M , as well as the symbol written on the tape in position i1 .

The following reactions assure that the symbols on the tape where the head is not located stay unchanged:

({a i }, {q i : q ∈ Q}, {a i }) for 1 ≤ i ≤ m; (2)
Indeed, for every i, the i-th reaction of type ( 2) is inhibited by the presence of any state with the same subscript i, to allow that only a reaction of type (1) takes place when the head of M is over the tape cell i.

Hence, the reaction system M maps the state encoding any configuration of M on input x to the state corresponding to the next configuration of M . Notice that some states of M are "malformed", as they contain zero or more than one state entity, or zero or more than one symbol making reference to a position. In this case, the behaviour of M is unrelated with the one of M .

We also stress that the reaction system M can be built from the description of M and the unary encoding of m in logarithmic space, since its reactions can be output by iteration over all tape positions 1 ≤ i ≤ m in binary notation: this number requires only O(log 2 (m)) bits to be represented, and all other quantities involved, like the size of the set of states, the alphabet, and the table representing the transition function, are constant in size.

Problems Solvable in Polynomial Time

Some interesting problems related to the dynamics of reaction systems involve their forward dynamics and for a limited amount of time (polynomial). These problems are usually efficiently solvable, although often they are among the hardest problems in P. The canonical example is "local" reachability.

Theorem 4. Given RS A = (S, A), two states T, U ⊆ S, and a unary integer k, it is P-complete to decide if T leads to U in at most k steps.

Proof. We show this result by reduction from the P-complete bounded halting problem [START_REF] Papadimitriou | Computational Complexity[END_REF] Given a deterministic Turing machine M , a string x and a unary integer k, does M accept x within k steps?

Without loss of generality, we assume that Turing machine M has a unique accepting configuration, with the tape head in the accepting state located on the first tape cell, and with an empty tape (i.e., each tape cell is blank). We can build the reaction system M simulating M with k + 1 cells of tape (the maximum amount of tape exploitable in k steps) as described in Section 3. Let T be the encoding of the initial configuration of M on input x, and let U be the encoding of the unique accepting configuration. Then, it holds that state T leads to U within k steps (the property to be decided) if and only if M accepts x within k steps.

Since the mapping (M , x, k) → (M, T, U, k) can be carried out in logarithmic space, the problem is P-hard. It also belongs to P, since the property can be checked by simulating k steps of the reaction system.

The problem of detecting the presence of "short" cycles is also P-complete. Theorem 5. Given a RS A = (S, A), a state T ⊆ S, and a unary integer ≥ 1 as input, it is P-complete to decide if T is a periodic point of period at most . Proof. We proceed by reduction from the bounded halting problem. Let M be a Turing machine having a unique accepting configuration in which the accepting state is r, the head is over the tape cell 1, and the tape is empty. Consider the reaction system simulating M from Section 3 and change it so that r 1 is added to the inhibitors of all reactions of types ( 1) and ( 2):

({q i , a i }, {r 1 }, {q i+d , a i }) for 1 ≤ i ≤ m ({a i }, {q i : q ∈ Q} ∪ {r 1 }, {a i }) for 1 ≤ i ≤ m
This means that the original reactions are now disabled if M reaches its accepting state. The reaction system M we are building is also equipped of an additional reaction, which will be instead enabled if M accepts. Let U be the state of M encoding the initial configuration of M on a given input string x. Such a reaction is:

({r 1 }, ∅, U)
Then, the state T , encoding the final configuration of M , belongs to a cycle of length at most if and only if M accepts x within -1 steps. Since the mapping (M , x, k = -1) → (M, T, ) can be computed in logarithmic space, the problem under consideration is P-hard due to the complexity of the bounded halting problem. The P upper bound also holds. Indeed, establishing whether any state T is periodic of period at most can be checked by performing a simulation of the reaction system with initial state T and testing whether the state T itself is reached within steps.

Even when we search for short cycles with a short preperiod we obtain P-completeness. Theorem 6. Given a RS A = (S, A), a state T ⊆ S, and two unary integers ≥ 1 and k as input, it is P-hard to decide if, when A starts at T , it reaches a cycle of period at most after a preperiod of length at most k.

Proof. This problem is P-hard by trivial reduction, since it is a generalisation of the problem of Theorem 5, the latter having the fixed value k = 0 for the preperiod. A polynomial time algorithm for this problem computes a sequence of k + steps of A starting from any initial state, and checks that a cycle is reached within the first k steps.

Problems in the Polynomial Hierarchy

A jump in complexity happens when, instead of checking a local dynamical behaviour that only involves the forward dynamics, we search for the existence of a local behaviour somewhere in the system or the property involves the backward dynamics, i.e., the preimages of a state.

While deciding if a state is part of a short cycle can be done in deterministic polynomial time, establishing the existence of such a state is NP-complete. We will see that this holds even when the length of the cycle is fixed a priori.

In the sequel, for any Boolean formula ϕ in conjunctive or disjunctive normal form and with clauses ϕ 1 , . . . , ϕ m , for each clause ϕ i we denote by pos(ϕ j ) (resp., neg(ϕ i )) the set of variables appearing in ϕ i as positive (resp., negative) literals. Theorem 7. For each integer ≥ 1, it is NP-complete, on input a RS A, to decide if A has a periodic point of period at most . Proof. We prove the NP-hardness of this problem by reduction from the Boolean satisfiability problem. For any Boolean formula ϕ = ϕ 1 ∧ • • • ∧ ϕ m in conjunctive normal form over the set of variables X = {x 1 , . . . , x n } we build a reaction system A = (S, A) with set of entities S = X ∪ Z, where Z = {♠ 0 , . . . , ♠ }. For any state T ⊆ S, the set T ∩ X encodes an assignment of ϕ in which x i has true value iff x i ∈ T ∩ X . First of all, the set A contains the following group of reactions

(neg(ϕ j ), pos(ϕ j ) ∪ Z, {♠ 0 }) for 1 ≤ j ≤ m; (3)
Thus, when the system is in a state T ⊆ X , this group of reactions produces the entity ♠ 0 (i.e., at least one among them is enabled in T ) if there exists a clause ϕ j not satisfied by the assignment encoded by T (hence ϕ itself is not satisfied). Notice that these reactions are disabled in any state T containing some ♠ t . The set A also includes the following reactions

({x i }, Z, {x i }) for 1 ≤ i ≤ n; (4)
which preserve the value of the assignment of ϕ encoded by a current state T in the next state when T ⊆ X . In this way, the reactions of type ( 3) and ( 4) ensure that res A (T ) = T for any T ⊆ X encoding an assignment satisfying ϕ, and res A (T ) = T ∪ {♠ 0 } if T ⊆ X but T codifies an assignment which does not satisfy ϕ.

The following last group of reactions constituting A creates a cycle of length + 1 formed exactly by the entities of Z

({♠ t }, {♠ s : 0 ≤ s < t}, {♠ (t+1) mod ( +1) }) for 0 ≤ t ≤ ; (5)
Indeed, it trivially holds that res A ({♠ t }) = {♠ (t+1) mod ( +1) }. Moreover, if the system is in a state T with T ∩ Z = ∅, then its next state is {♠ t+1 mod +1 }, where t = min{s : ♠ s ∈ T }. Hence, the reaction system A has both a cycle of length + 1 (namely

{♠ 0 } → • • • → {♠ } → {♠ 0 }
) and at least a fixed point, that is a cycle of length at most , if and only if the formula ϕ admits a satisfying assignment.

Since the mapping ϕ → A can be computed in polynomial time, the problem is NP-hard. The membership in NP follows by the existence of a non-deterministic algorithm guessing an initial state T and checking in polynomial time whether T is again reached within steps.

The difficulty of the problem does not increase when the length of the cycle is given in input.

Theorem 8. Given a RS A and a unary integer ≥ 1 as input, it is NP-complete to decide if A has a periodic point of period at most .

Proof. The problem is NP-hard by reduction from any of the problems of Theorem 7, which are NP-hard for every fixed ≥ 1. The same algorithm mentioned at the end of the proof of Theorem 7 proves the membership in NP, since the extra input is given in unary notation.

Checking if a state is part of a short cycle can be performed in deterministic polynomial time. However, checking if there exists another state reaching it after a certain amount of steps makes the problem NP-complete. Theorem 9. Given a RS A = (S, A), a state T ⊆ S, and two unary integers ≥ 1 and k as input, it is NP-complete to decide if T is a periodic point of period at most and there exists a state U ⊆ S leading to T with preperiod at least k.

Proof. We proceed by reduction from the Boolean satisfiability problem. For any Boolean formula ϕ = ϕ 1 ∧• • •∧ϕ m in conjunctive normal form over the set of variables X = {x 1 , . . . , x n } we build a reaction system A = (S, A) with set of entities S = X ∪ C, where C = {ϕ 1 , . . . , ϕ m }. As in the proof of Theorem 7, for any state T ⊆ S, the set T ∩ X encodes a truth assignment of ϕ. The set A contains the following two groups of reactions

{x i }, ∅, {ϕ j : x i ∈ pos(ϕ j )} for 1 ≤ i ≤ n ∅, {x i }, {ϕ j : x i ∈ neg(ϕ j )} for 1 ≤ i ≤ n
By evaluating ϕ, these reactions map a state T to the set of clauses satisfied by the assignment encoded by T ∩ X , ignoring any element of T ∩ C.

The further reaction in

A (C, X , C)
ensures that the state consisting exactly of all clauses is a fixed point, since these latter are preserved when they appear all together without any variable from X .

Then, the resulting reaction system A has a fixed point T = C, that is a cycle of length at most = 1, with a state U leading to T and having preperiod at least k = 1, if and only if U ∩ X encodes a assignment which satisfies ϕ.

Since the mapping ϕ → A is polynomial-time computable, the problem is thus NP-hard. A polynomial-time nondeterministic algorithm for the problem under consideration exists. It guesses a state U leading to T in exactly k steps, verifies if T belongs to a cycle of length at most , and checks that the set {U, res A (U), . . . , T } and the cycle only have T as a common state. Therefore, the membership in NP follows.

More in general, the problem of exploring the dynamics backwards is NP-complete.

Theorem 10. Given a RS A = (S, A), a state T ⊆ S, and a unary integer k as input, it is NP-complete to decide if T has a k-ancestor.

Proof. Perform the same reduction as in the proof of Theorem 9, except adding the entity ♥ to S and changing the reaction (C, X , C) to (C, X , C ∪ {♥}). Now the obtained reaction system has the fixed point C ∪ {♥} rather than C, and C leads to C ∪ {♥} in one step. Then, state C has T as preimage, i.e., T is a 1-ancestor of C, if and only if T ∩ X satisfies ϕ for some set T ⊆ S. Thus, the NP-hardness follows. The problem is also in NP. Indeed, once a state U ⊆ S is guessed, it can be checked in polynomial time whether res k A (U) = T . Establishing if there exists a state that leads to a short cycle after a given number of steps, i.e., a state far enough from the cycle, turns out be another NP-complete problem.

Theorem 11. Given a RS A = (S, A) and two unary integers ≥ 1 and k as input, it is NP-complete to decide if there exists a state T ⊆ S such that, when A starts in T , it reaches a cycle of length at most after a preperiod of length at least k.

Proof. The problem from Theorem 8 is a special case of the one under consideration and is obtained when k = 0. Hence, by reduction from the former problem, the one we are dealing with is NP-hard too. Its membership in NP follows by the existence of an algorithm similar to that at the end of the proof of Theorem 9, except that the state T must also be guessed, rather than being given as input.

Checking if every state of a reaction system has exactly one preimage is the same as deciding if the result function is a bijection. This problem can be shown to be coNP-complete by a variation of a proof by Ehrenfeucht and Rozenberg [START_REF] Ehrenfeucht | Reaction systems[END_REF].

Theorem 12. Given a RS A = (S, A), it is coNP-complete to decide if res A is a bijection, that is, if every state of A is periodic.

Proof. We prove coNP-hardness by reduction from the tautology problem for Boolean formulae in disjunctive normal form [START_REF] Papadimitriou | Computational Complexity[END_REF]. Given a formula ϕ = ϕ 1 ∨ . . . ∨ ϕ m over the variables X = {x 1 , . . . , x n }, we build the reaction system A = (S, A) where S = X ∪ {♥} and the reactions are

(pos(ϕ j ) ∪ {♥}, neg(ϕ j ), {♥}) for 1 ≤ j ≤ m; (6)
({x i }, ∅, {x i }) for 1 ≤ i ≤ n; (7)
As usual, for any state T , T ∩ X encodes a truth assignment of ϕ. In this way, if ♥ occurs in the current state, the reactions of type ( 6) evaluate each conjunctive clause (which is satisfied iff all positive variables are set to true and all negative ones to false) and preserve the element ♥ if the clause (and thus the whole formula) is satisfied. The reactions of type ( 7) preserve all variables in the current state. Hence, the behaviour of A is as follows. If the current state T ⊆ X , only reactions of type [START_REF] Barbuti | Specialized predictor for reaction systems with context properties[END_REF] are enabled, and thus res A (T ) = T . On the other hand, if ♥ ∈ T , we have res A (T ∪{♥}) = T ∪{♥} if at least one reaction of type ( 6) is enabled, that is, if ϕ is satisfied by the assignment encoded by T ; otherwise, it holds that res A (T ∪ {♥}) = T . As a consequence, each state of A is a fixed point, and thus a cycle, iff ϕ is a tautology; otherwise, there exists a state with two preimages, namely, a state T ⊆ X encoding a non-satisfying assignment and having both T and T ∪ {♥} as preimages.

The considered problem belongs to coNP, since there exists a non-deterministic algorithm guessing two distinct states T, U ⊆ S and checking whether res A (T ) = res A (U) in polynomial time.

The previous construction actually proves another similar result: Theorem 13. Given a RS A = (S, A), it is coNP-complete to decide if res A is the identity function, that is, if each state is a fixed point.

Establishing whether a local attractor cycle has a small attraction basin is coNP-complete. Theorem 14. Given a RS A = (S, A), a state T ⊆ S, and two unary integers ≥ 1 and d as input, it is coNP-complete to decide if T belongs to a local attractor cycle of length at most with attraction basin of diameter at most d.

Proof. We use a reduction from tautology similar to that introduced in the proof of Theorem 12. For any formula ϕ = ϕ 1 ∨ . . . ∨ ϕ m over the variables X = {x 1 , . . . , x n }, consider the reaction system from the aforementioned reduction. We add an extra entity ♠ to its background set and slightly change the original reactions as follows:

(pos(ϕ j ) ∪ {♥}, neg(ϕ j ) ∪ {♠}, {♥}) for 1 ≤ j ≤ m; ( 8
)
({x i , ♥}, {♠}, {x i }) for 1 ≤ i ≤ n; (9)
Furthermore, we add the two extra reactions

(∅, {♥}, {♠}) ({♠}, ∅, {♠})
producing ♠ whenever ♥ is missing, and preserving ♠, respectively. The resulting reaction system A behaves as follows. Let U ⊆ X . By evaluating ϕ on the basis the assignment encoded by U, it follows that res A (U ∪ {♥}) = U ∪ {♥} if U encodes an assignment satisfying ϕ, and res A (U ∪ {♥}) = U otherwise. Furthermore, either when ♠ belongs to the current state (which is thus either U ∪ {♠} or U ∪ {♠, ♥}), or when neither ♠ nor ♥ do (i.e., the current state is U), it holds that res The problem is in coNP since once guessed a state U it is possible to check in polynomial time if it falsifies the required property.

A (U) = res A (U ∪ {♠}) = res A (U ∪ {♠, ♥}) = {♠}.
On the other hand, deciding if a small attractor cycle has a large attraction basin is an NP-complete problem.

Theorem 15. Given a RS A = (S, A), a state T ⊆ S, and two unary integers ≥ 1 and d as input, it is NP-complete to decide if T belongs to a local attractor cycle of length at most with attraction basin of diameter at least d.

Proof. The state {♠} in the proof of Theorem 14 has an attraction basin of diameter at least 2 iff the Boolean formula ϕ is not a tautology, and the latter is the statement of a NP-complete problem (since its negation is a coNP-complete one). Indeed, the same algorithm as in the proof of Theorem 14, but with reversed acceptance and rejection, proves the membership in NP.

Establishing the existence of a small attractor cycle with a large attraction basin remains NP-complete.

Theorem 16. Given a RS A = (S, A) and two unary integers ≥ 1 and d as input, it is NP-complete to decide if there exists a local attractor cycle of length at most with attraction basin of diameter at least d.

Proof. Consider the reactions system A from the proof of Theorem 15; all of its states are either fixed points or eventually reach state {♠}. Hence, {♠} is the only state with attraction basin of diameter at least 1. Hence, asking whether there exists a fixed point (i.e., a cycle of length = 1) with an attraction basin of diameter at least d = 2 is the same as asking whether T = {♠} has this property, which is NP-complete. The problem under consideration is in NP, since a state T can be guessed before the same algorithm in the proof of Theorem 15 is used.

Differently from the previous case, the problem of establishing the existence of a small attractor cycle with a small attraction basin is higher in the polynomial hierarchy.

Theorem 17. Given a RS A = (S, A) and two unary integers ≥ 1 and d as input, it is Σ P 2 -complete to decide if there exists a local attractor cycle of length at most with attraction basin of diameter at most d.

Proof. First of all, we show the membership in Σ P 2 of the problem. There exists an alternating Turing machine able to guess a state T ⊆ S and then, by iterating the res A function, check that it belongs to a cycle of length at most . Subsequently, the machine also guesses a state U ⊆ S and checks if it reaches that cycle in d + 1 steps (this would prove that the attraction basin has diameter larger than d; if no such guess is possible, then the attraction basin has diameter at most d). If this is the case, the machine rejects, while it accepts, otherwise; the overall result of the machine is acceptance if and only if the answer to the considered problem is true. Therefore, the membership in Σ P 2 follows. We now prove the Σ P 2 -hardness of the problem by reduction from ∃∀SAT, i.e., the problem of deciding if ∃X ∀Y ϕ(X , Y ), where ϕ is a Boolean formula in disjunctive normal form with conjunctive clauses ϕ 1 , . . . , ϕ k over the variables X = {x 1 , . . . , x m } and Y = { y 1 , . . . , y n }.

For any of such formulae ϕ, define the reaction system A = (S, A) where S = X ∪ Y ∪ {♥, ♠} and A consists of the two group of reactions

(pos(ϕ j ), neg(ϕ j ), {♥})
for each clause ϕ j ;

({x i }, ∅, {x i }) for each variable x i ∈ X ; (10)
which depend on the Boolean formula, and the following further reactions

(∅, ∅, {♠}) (12)
({♥}, ∅, {♥}) (13)
({♠}, ∅, {♥}) (14)
We are going to describe the behaviour of A. First of all, consider a state of the form X 1 ∪ Y 1 for some X 1 ⊆ X and Y 1 ⊆ Y . As usual, such a state represents an assignment of ϕ, where the variables appearing in X 1 ∪ Y 1 have true value, and the missing ones have false value. A reaction of type ( 10) is then enabled if and only if the corresponding conjunctive clause ϕ j is satisfied. Furthermore, a reaction of type ( 11) is enabled for each element of X 1 , while the reaction ( 12) is always enabled. As a consequence, we have res A (X 1 ∪ Y 1 ) = X 1 ∪ {♥, ♠} if at least one clause (and thus the disjunction ϕ) is satisfied by the assignment represented by

X 1 ∪ Y 1 ; otherwise, we have res A (X 1 ∪ Y 1 ) = X 1 ∪ {♠}. Furthermore, we have res A (X 1 ∪ Y 1 ∪ {♥}) = res A (X 1 ∪ Y 1 ∪ {♠}) = res A (X 1 ∪ Y 1 ∪ {♠, ♥}) = X 1 ∪ {♠, ♥}
irrespective of whether the assignment encoded by

X 1 ∪ Y 1 satisfies ϕ.
This means that all 2 |X | states of the form X 1 ∪ {♠, ♥} for any X 1 ⊆ X are fixed points and A admits no further fixed points or cycles. Moreover, each fixed point X 1 ∪ {♠, ♥} attracts in one step all states of the forms

X 1 ∪ Y 1 ∪ {♥}, X 1 ∪ Y 1 ∪ {♠}, and X 1 ∪ Y 1 ∪ {♠, ♥} for any Y 1 ⊆ Y . On the other hand, the states of the form X 1 ∪ Y 1 reach X 1 ∪ {♠, ♥} in one step iff X 1 ∪ Y 1 satisfies ϕ,
and in two steps, otherwise.

In conclusion, there exists a fixed point (which is a cycle of length at most = 1), necessarily of the form X 1 ∪ {♠, ♥} for some X 1 ⊆ X , with an attraction basin of diameter at most d = 1 if and only if X 1 ∪ Y 1 satisfies ϕ for all Y 1 ⊆ Y . This is equivalent to ∃X ∀Y ϕ(X , Y ) being true. Since the mapping ϕ → (A, , d) can be computed in polynomial time, the problem is Σ P 2 -hard.

Problems Solvable in Polynomial Space

Removing the restrictions on the length of cycles or preperiods leads to properties involving a potentially exponential number of states, and algorithms checking these properties might need to explore all of them. Such algorithms, however, can be designed to use a polynomial amount of space, since every state contains only a polynomial amount of entities.

The canonical PSPACE-complete problem for reactions systems is reachability.

Theorem 18.

Given RS A = (S, A) and two states T, U ⊆ S, it is PSPACE-complete to decide if T leads to U.

Proof. We prove the hardness of the problem by reduction from the following PSPACE-complete problem [START_REF] Papadimitriou | Computational Complexity[END_REF]:

Given a deterministic Turing machine M , a string x and a unary integer m, does M accept x without using more than m tape cells?

As in the proof of Theorem 4, for any (M , x, m) we build a reaction system A by exploiting the construction described in Section 3 with k = m. By encoding again the initial configuration of M on input x as a state T of A and the unique accepting configuration of M as state U, we obtain the desired reduction. Indeed, if M accepts x without exceeding m tape cells, then T leads to U. Furthermore, this never happens if M rejects, or fails to halt, or moves the tape head on cell m + 1; remark that in the latter case, T does not lead to U since the reactions of type (1) are not defined for i = m + 1, and the element q m+1 disappears. The problem is in PSPACE because there exists an algorithm able to check in polynomial space whether T leads to U (such an algorithm rejects if this does not happen within 2 |S| steps, that is the number of configurations of A).

To prove the PSPACE-hardness of other problems, in this section we are going to introduce a variant of the polynomial space simulation of the Turing machine from Section 3 used in the proof of Theorem 18. Since most of the statements in the next theorems involve a quantification across every state of the reaction system, the dynamics of all the possible states will have to be considered and governed. To this extent, for any Turing machine M with state set Q where f ∈ Q is the final accepting state, tape alphabet Σ, transition function δ, any input x, and any space bound m given in unary, the new construction of the reaction system and the encoding of the configurations of M into related states is based on what follows:

1. Let T be the state of the reaction system encoding the initial configuration of M . As in the proof of Theorem 18, M accepts by ending up in a specific accepting configuration with the tape head on the first tape cell and encoded by the state U in the reaction system which will be now a fixed point; otherwise, M rejects by diverging. 2. All states of the reaction system encoding a configuration of M either lead to the fixed point U (which corresponds to the accepting configuration reached by M ) or enter a cycle. We stress that this set of states also includes the ones encoding configurations of M that are not reachable from the initial configuration.

A timer is now coupled to the encoding of configurations of M , in order to force all states of the reaction systems belonging to this set to reach T once the timer reaches an appropriate value. 3. If a state of the reaction system does not encode a valid Turing machine configuration and a valid timer, it is detected and forced to reach T . Then, its dynamics will evolve as described in statement 1.

In this way, all states lead to the fixed point U only if T itself leads to U (i.e., if M reaches the accepting configuration within the space bound m). This is accomplished by building the new reaction system M = (S, A) as follows.

Consider the background set of the reaction system from Section 3 and keep unchanged the way to encode any configuration of M into a state of reaction system state. Now, an entity is added to that background set, namely the entity which represents the "reset" to be executed in some cases from a state of M to the state T , which has well defined dynamics and encoding the initial configuration of M .

Reminding that f 1 is the entity corresponding to the accepting state f in the accepting configuration of M (with the tape head located on the first cell), we introduce the following reaction in order to force the element f 1 to constitute the fixed point U = { f 1 } when it is the only entity of the state2 :

({ f 1 }, ∅, { f 1 })
Since we are interested only in accepting computations within a given space bound m, the set of reactions A also contains the following reactions, which force a "reset" by generating the entity if the tape head reaches the (m + 1)-th cell:

({q m+1 }, { f 1 , }, { }) for q ∈ Q
In order to deal with the simulation of M by M upon reaching an accepting configuration or the situation when a reset is needed, reactions 1 and 2 from Section 3 implementing every transition δ(q, a) = (q , a , d) appear now in A with f 1 and as additional inhibitors:

({q i , a i }, { f 1 , }, {q i+d , a i }) for 1 ≤ i ≤ m ({a i }, {q i : q ∈ Q} ∪ { f 1 , }, {a i }) for 1 ≤ i ≤ m
In this way, the transition of M is not executed and the tape is not preserved, thus deleting the current configuration of the simulated Turing machine.

We now describe how is produced by a timer in order to comply with property 2 on page 11. Denote by p k the k-th prime number and define K as the smallest number such that K k=1 p k -1 is greater than the number of possible distinct configuration of M when working in space m. For each k = 1, . . . , K, let c k,0 , . . . , c k,p k -1 be further entities in the background set S of M. For each k, the following group of reactions is included in A:

({c k,t }, { f 1 , }, {c k,(t+1) mod p k }) for 0 ≤ t < p k
Each group of reactions defines a cycle of length p k . When all the reactions of all groups act together every time step of the evolution of the reaction system in which f 1 and do not appear, they give rise to a cycle of length L = K k=1 p k , since the p k 's are pairwise coprime. In this way, the dynamical evolution of M starting from any state including Y 0 = {c 1,0 , . . . , c K,0 } and containing neither f 1 nor is associated with a timer whose value at time t can be identified by Y t = {c 1,t 1 , . . . , c K,t K } where t k = t mod p k . The timer reaches its maximum value once the state of M contains Y t = {c 1,p 1 -1 , . . . , c K,p K -1 }, and the first time it happens is at time t = L -1.

In the following two steps, the entity is produced and the timer is reset to 0, the state of the reactions system M is set to C 0 = T ∪ Y 0 as desired, and the simulation of M by M restarts from the initial configuration encoded by T . This is accomplished by the following two reactions:

({c k,p k -1 : 1 ≤ k ≤ K}, { f 1 , }, { }) ({ }, { f 1 }, C 0 ) Remark that, if M works in space m, then it has |Σ| m × m × |Q| possible distinct configurations. By letting K = log 2 (|Σ| m × m × |Q|) +1, it holds that K k=1 p k -1 = L -1
is larger that the number of possible configurations of M , since p k ≥ 2 for all k. By the Prime Number Theorem [START_REF] Dudley | Elementary Number Theory[END_REF], the K-th prime is asymptotically K ln K. To find K primes, it is therefore sufficient to test the primality of the first O(K ln K) natural numbers, where each number can be tested even using a brute force algorithm. Since this value is polynomial with respect to length of the description of M and with respect to m (which is given in unary), the construction of M we are describing can be carried out in polynomial time.

In order to comply with statement 3 on page 11, the set of reactions A must also contain reactions generating each time the current state of the reaction systems fails to encode either a valid pair (timer, configuration of M ) nor it is the fixed point { f 1 }. First of all, the following reactions generate when the current state of M contains zero or more than one entity encoding the pair (state, head position of M ):

(∅, {q i : q ∈ Q, 1 ≤ i ≤ m} ∪ { f 1 , }, { }) ({q i , r j }, { f 1 , }, { }) for q, r ∈ Q and 1 ≤ i, j ≤ m
The entity must also be produced each time the state of M does not encode exactly one symbol per tape cell:

(∅, {a i : a ∈ Σ} ∪ { f 1 , }, { }) for 1 ≤ i ≤ m ({a i , b i }, { f 1 , }, { }) for a, b ∈ Σ and 1 ≤ i ≤ m
Finally, there must also be reactions in A producing when the state does not include a well-formed timer. That is, when for a single prime p k there does not appear exactly one entity of the form c k,i in the current state of M:

(∅, {c k,t : 0 ≤ t < p k } ∪ { f 1 , }, { }) for 1 ≤ k ≤ K ({c k,t , c k,s }, { f 1 , }, { }) for 1 ≤ k ≤ K and 0 ≤ t, s < p k
In this way, we have obtained a construction complying with properties 1-3 on page 11 and that can be carried out in polynomial time.

We are now able to prove that checking the existence of long cycles is PSPACE-complete.

Theorem 19. Given a RS A over a background set S and a unary integer ≥ 1 as input, it is PSPACE-complete to decide if A has a periodic point of period at least .

Proof. The problem is in PSPACE since there exists an algorithm that iterates over all the possible states of A and checks if each of them leads back to itself after at least steps (but which is necessarily not greater than 2 |S| ). This can be performed in polynomial space. We prove that the problem under consideration is PSPACE-hard by a reduction from the same problem used in the proof of Theorem 18. For any Turing machine M , any input string x, and any space bound m, consider the reaction system M from the above construction. Let = 2 and let k ≥ be the number of possible configurations for M when working in space m. By construction, it holds that if M accepts on input x, then each state of M leads to the fixed point { f 1 }, and, in particular, no cycle of length at least can be reached. Otherwise, if M rejects on input x by diverging, there is a cycle containing the state C 0 , which includes the encoding of the initial configuration of M . The length of this cycle is dictated by the time needed for the timer to generate the entity , which, by hypothesis, is greater than the number of configuration of M when working in space m, and, therefore, of k and, as a consequence, of . Hence, there is cycle of length at least if and only if M does not accept on input x working in space m. This concludes the reduction and the PSPACE-hardness of the problem under consideration follows.

Also checking whether there exists a state that is far enough from a long cycle is PSPACE-complete. Theorem 20. Given a RS A = (S, A) and two unary integers ≥ 1 and k as input, it is PSPACE-complete to decide if there exists a state T ⊆ S such that, when A starts in T , it reaches a cycle of length at least after a preperiod of length at least k.

Proof. The problem is in PSPACE since there exists a non-deterministic algorithm able to guess two states T and U and check in polynomial space that T leads to U in at least k steps, that U is in a cycle of length at least , and that U is the first state of that cycle visited by A starting from T . Since PSPACE is closed under non-determinism, it contains the problem under consideration.

Such a problem is PSPACE-hard since in the case k = 0 it is equivalent to the one from Theorem 19, which is

PSPACE-complete.
The same problem remains PSPACE-complete even when the starting state is given in input.

Theorem 21. Given a RS A = (S, A), a state T ⊆ S and two unary integers ≥ 1 and k as input, it is PSPACE-complete to decide if, when A starts at T , it reaches a cycle of length at least (resp., at most ) after a preperiod of length at least k.

Proof. The problem is in PSPACE since it is possible to check in polynomial space if each state in the dynamics of A starting from T is part of a cycle or not, thus obtaining the preperiod and period of T .

The PSPACE-hardness follows by a reduction from the same problem used in the proof of Theorem 18. For any Turing machine M , input string x, and unary space bound m, let M be the reaction system obtained by the construction presented in this section. Take T = C 0 , k = 1, and = 1. It holds that T has preperiod at least one if and only if M accepts on input x. In that case, the dynamics reaches, after at least one step, the fixed point { f 1 }, and thus T has period 1, otherwise T is part of a cycle and thus has preperiod 0. Then, the reduction is accomplished.

Problem dealt with in this paper

Complexity

-complete

Table 1: Comprehensive list of problems on the dynamics of RA and their complexity. (*)/(=): extended/same version of a result presented at either CiE 2014 [START_REF] Formenti | Fixed points and attractors of reaction systems[END_REF] or DCFS 2014 [START_REF] Formenti | Cycles and global attractors of reaction systems[END_REF].

2 Figure 1 :

 21 Figure 1: Encoding of a configurations of M as state T = {a 1 , b 2 , b 3 , a 4 , 5 , 6, q 2 } of M where each tape symbol is subscripted with its own position, while the current state of M is subscripted with the position of the head. The square represents the blank symbol.

  Hence, state {♠} has a 2-ancestor if and only if the formula has a non-satisfying assignment U. In that case, we have res 2 A (U ∪ {♥}) = res A (U) = {♠}. By letting T = {♠}, = 1, and d = 1, and since the mapping ϕ → (A, T, , d) is polynomial-time computable, we obtain the coNP-hardness of the problem.

∃∃

  periodic point of period at most (*) NP-complete T has period ≤ & ∃U reaching T in ≥ k steps (*) NP-complete ∃ periodic point with period ≤ & preperiod len. ≥ k (*) NP-complete T is global attractor of period ≤ (≥ ) (*) global fixed point attractor of period ≤ (≥ ) (*) PSPACE-complete T belongs to a cycle of period (*) ≥ PSPACE-complete res is bijective (=) coNP-complete ∃ a periodic point with period ≤ & preperiod len. ≥ k (*) NP-complete T has period ≤ P-complete T has period ≤ & preperiod ≥ k P-complete T has a k-predecessor P-complete res is the identity coNP-complete T is an attractor cycle of period ≤ & diameter ≤ d coNP-complete T is an attractor cycle of period ≤ & diameter ≥ d NP-complete ∃ an attractor cycle of period ≤ & diameter ≥ d NP-complete ∃ an attractor cycle of period ≤ & diameter ≤ d Σ P

  • a state T belongs to a local attractor cycle of length at most with attraction basin of diameter at most d/at least d (coNP-complete/NP-complete, Theorems 14 and 15)• there exists a local attractor cycle of length at most with attraction basin of diameter at least d/at most d (NP-complete/Σ P 2 -complete, Theorems 16 and 17) • a state T belongs to a global attractor cycle of length at most /at least (PSPACE-complete,Theorem 22)

Notice that, for simplicity, the background set S and the reactions of type (1) refer to the entities q m+1 for all q ∈ Q; however, in this section the tape head, by hypothesis, does never reach the (m + 1)-th tape cell. The entities q m+1 will play a different role in Section 6.

Actually, U encodes the state of M coming immediately after the one encoding the accepting configuration of M . However, the two states coincide if one ignores the content of the tape and the direction.

Acknowledgements

Enrico Formenti acknowledges the partial support from the project PACA APEX FRI. Alberto Dennunzio and Luca Manzoni were partially supported by Fondo d'Ateneo (FA) 2016 of Università degli Studi di Milano Bicocca: "Sistemi Complessi e Incerti: teoria ed applicazioni". Antonio E. Porreca was partially supported by Fondo d'Ateneo (FA) 2015 of Università degli Studi di Milano Bicocca: "Complessità computazionale e applicazioni crittografiche di modelli di calcolo bioispirati".

All problems related to the existence of global attractors also turn out to be PSPACE-complete. Theorem 22. Given a RS A = (S, A) and a unary integer ≥ 1 as input, it is PSPACE-complete to decide:

1. If a state T ⊆ S, also given as input, belongs to a global attractor cycle of length at most (resp., at least ). 2. If there exists a global attractor cycle of length at most (resp., at least ).

Proof. All these problems are in PSPACE, since it is possible to check in polynomial space if any given state T of A belongs to a cycle of length at most (resp., at least ) and it is reachable from every other state. The existential version of the problems can be solved by iterating across all the states of A, which can also be performed in polynomial space.

The PSPACE-hardness again follows from the reduction from the same problem used in the proof of Theorem 18. For any Turing Machine M , input string x, and unary space bound m, according to the construction presented in this section, the reaction system M has a global attractor cycle, namely the fixed point { f 1 }, if and only if M accepts on input x within space m. The reduction is completed by setting = 1 and, for the first problem, T = { f 1 }.

Conclusions

This paper has tackled the study of the computational complexity of problems associated with the dynamics of RS. Table 1 provides a reference list of such problems. While these problems are mainly theoretical, their formulation takes inspiration from properties that usually have real-world significance in bio-chemical systems and can thus be useful in the study of RS-based models of real-world systems.

From a theoretical point of view, we stress that the interest of such studies is twofold. On one hand, results about RS are lower bounds for similar results of other finite discrete dynamics systems, like Boolean automata networks (BANs). In fact, RS can be considered as a constrained form of BANs, where each node in the network represents an entity and the update function encodes that at least one reaction having that entity as a product was active. In this sense, problems studied here in the context of RS cannot be simpler in the context of BANs, thus providing a lower bound on the complexity in another computational model.

On the other hand, when suitably constrained, RS are a simple model of parsimonious systems (i.e., systems which have a description exponentially shorter than the complete description of their dynamics). A natural research direction consists in trying to understand what exactly causes the complexity jumps between similar problems (cf. the last two entries of Table 1, for example).

Another aspect to study is how to constrain RS in order to be more similar to systems that are actually found in nature. While all the constructions presented here are valid in the framework of reaction systems, it is important to remember that not all of them might be found in a "natural" system. Of particular interest is to understand if the complexity results found here also hold for real-world systems or if there are some differences, and what those differences are.


Ke Hua

Yudong D Zhang
email: yudong.zhang@univ-lorraine.fr

Weimin Gan

Hongchao Kou
email: hchkou@nwpu.edu.cn

Benoit Beausir

Jinshan Li

Claude Esling

Hot deformation behavior originated from dislocation activity and β to α phase transformation in a metastable β titanium alloy

Keywords: Phase transformation (A), Electron microscopy (EBSD/TEM) (C), Microstructures (A), Dislocations (A), Titanium alloy

Introduction

Hot working is an important processing procedure for metal forming and mechanical property optimization, and thus widely used for the manufacturing of metallic materials, such as steels (Eyckens et al., 2015;Fujita et al., 2018;[START_REF] Khan | A deformation mechanism based crystal plasticity model of ultrafine-grained/nanocrystalline FCC polycrystals[END_REF][START_REF] Kestens | Texture formation in metal alloys with cubic crystal structures[END_REF][START_REF] Pham | Thermally-activated constitutive model including dislocation interactions, aging and recovery for strain path dependence of solid solution strengthened alloys: Application to AA5754[END_REF][START_REF] Tasan | Strain localization and damage in dual phase steels investigated by coupled in-situ deformation experiments and crystal plasticity simulations[END_REF], Titanium alloys [START_REF] Khan | Quasi-static and dynamic loading responses and constitutive modeling of titanium alloys[END_REF][START_REF] Khan | Effect of oxygen content and microstructure on the thermo-mechanical response of three Ti-6Al-4V alloys: Experiments and modeling over a wide range of strain-rates and temperatures[END_REF][START_REF] Liu | Mechanical behavior of ultrafine-grained/nanocrystalline titanium synthesized by mechanical milling plus consolidation: Experiments, modeling and simulation[END_REF][START_REF] Mandal | Simulation of plastic deformation in Ti-5553 alloy using a self-consistent viscoplastic model[END_REF][START_REF] Meredith | Texture evolution and anisotropy in the thermo-mechanical response of UFG Ti processed via equal channel angular pressing[END_REF], Aluminum alloys [START_REF] Sidor | Evolution of recrystallization textures in particle containing Al alloys after various rolling reductions: experimental study and modeling[END_REF][START_REF] Sun | Modeling of continuous dynamic recrystallization of Al-Zn-Cu-Mg alloy during hot deformation based on the internal-state-variable (ISV) method[END_REF], and NiTi shape memory alloys [START_REF] Wang | A thermomechanically coupled finite-strain constitutive model for cyclic pseudoelasticity of polycrystalline shape memory alloys[END_REF][START_REF] Xiao | Micromechanical modeling on thermomechanical coupling of cyclically deformed superelastic NiTi shape memory alloy[END_REF]. During the process, two opposite effects -hardening from crystal defect multiplication and crystal reorientation, and softening from defect rearrangement or annihilation via recovery and recrystallizationinterweave, resulting in characteristic stress-strain behavior and microstructure evolution. Thus the mechanical responses of the alloys during thermomechanical processes have been a topic of intensive experimental and theoretical investigations for process optimization and microstructure and mechanical property improvement.

Among the metallic materials, the metastable β titanium alloys are of particular interest for structural applications in aerospace and biomedicine [START_REF] Bonisch | Giant thermal expansion and α-precipitation pathways in Ti-alloys[END_REF][START_REF] Boyer | Discontinuous yielding behavior and microstructure evolution during hot deformation of TC11 alloy[END_REF][START_REF] Lütjering | Titanium[END_REF], and hot working by rolling or forging is routinely used for their manufacturing. Thus, numerous studies have been devoted to conceiving novel thermo-mechanical processes, and to revealing the hot deformation behavior and the microstructure evolution.

So far, the investigations on hot deformation of metastable titanium alloys have been focused on deformation either in the single β phase region (>Tβ (β transus temperature)) or in the α+β two phase region (<Tβ). For the former, only the β phase is concerned. The investigations have been mainly on the effect of deformation parameters, such as deformation strain rate, on microstructure evolution by recovery and/or recrystallization and texture change of the β phase (Furuhara et al., 2007;[START_REF] Rollett | Recrystallization and related annealing phenomena[END_REF][START_REF] Kanjarla | Assessment of plastic heterogeneity in grain interaction models using crystal plasticity finite element method[END_REF][START_REF] Matsumoto | Hot forging characteristic of Ti-5Al-5V-5Mo-3Cr alloy with single metastable β microstructure[END_REF]. For the hot deformation conducted in the α+β two phase region, the initial microstructure consists of the two phases, β and α. Since the deformation temperature (usually from 873K to 1023K) is close to the processing temperature (usually from 973K to 1123K), the topic has received much attention. Many investigations have been conducted on the deformation behavior of the alloys and the effect of deformation variables on microstructure evolution and on the underlying mechanisms. It has been revealed that the hot deformation (compression) behavior of metastable β alloys in this region is always characterized first by a linear stress-strain state, then by a drastic stress drop (termed discontinuous yielding) and finally by a steady-state [START_REF] Mandal | Simulation of plastic deformation in Ti-5553 alloy using a self-consistent viscoplastic model[END_REF].

The discontinuous yielding is a typical behavior not only of metastable β titanium alloys (Jing et al., 2017;[START_REF] Jonas | Transformation softening in three titanium alloys[END_REF][START_REF] Koike | Stress-induced phase transformation during superplastic deformation in two-phase Ti-Al-Fe alloy[END_REF][START_REF] Philippart | High temperature dynamic yielding in metastable Ti-6.8Mo-4.5F-1.5[END_REF][START_REF] Srinivasan | Yield points during the high temperature deformation of Ti-15V-3Al-3Cr-3Sn alloy[END_REF] but also of zirconium alloys [START_REF] Jonas | Anneal hardening and flow softening in beta zirconium niobium alloys[END_REF]. It has been proved to be a result of the stress induced reverse phase transformation (α→β) (Jing et al., 2017;[START_REF] Jonas | Transformation softening in three titanium alloys[END_REF][START_REF] Koike | Stress-induced phase transformation during superplastic deformation in two-phase Ti-Al-Fe alloy[END_REF], or to be related to the generation of mobile dislocations at the grain boundary regions [START_REF] Philippart | High temperature dynamic yielding in metastable Ti-6.8Mo-4.5F-1.5[END_REF][START_REF] Srinivasan | Yield points during the high temperature deformation of Ti-15V-3Al-3Cr-3Sn alloy[END_REF], depending on the alloy composition. The steady-state is found to be a result of a counterbalance between work hardening and work softening.

Dislocation slip has been considered as the main deformation mechanism and the dynamic recovery is the dominant mechanism for restoration of the β phase [START_REF] Jones | Thermomechanical processing of Ti-5Al-5Mo-5V-3Cr[END_REF][START_REF] Jones | The flow behavior and microstructural evolution of Ti-5Al-5Mo-5V-3Cr during subtransus isothermal forging[END_REF][START_REF] Johnston | Dislocation velocities, dislocation densities, and plastic flow in lithium fluoride crystals[END_REF][START_REF] Pham | Thermally-activated constitutive model including dislocation interactions, aging and recovery for strain path dependence of solid solution strengthened alloys: Application to AA5754[END_REF][START_REF] Rollett | Understanding materials microstructure and behavior at the mesoscale[END_REF]. In addition to the dislocation activity, the effects of the secondary phase (α phase), especially its distribution, size and morphology, on deformation behavior have also been examined [START_REF] Jones | Thermomechanical processing of Ti-5Al-5Mo-5V-3Cr[END_REF][START_REF] Jones | The flow behavior and microstructural evolution of Ti-5Al-5Mo-5V-3Cr during subtransus isothermal forging[END_REF]Ozturk and Rollet, 2018;[START_REF] Poletti | Unified description of the softening behavior of beta-metastable and alpha+ beta titanium alloys during hot deformation[END_REF][START_REF] Warchomicka | Quantitative analysis of the microstructure of near β titanium alloy during compression tests[END_REF][START_REF] Weiss | Thermomechanical processing of beta titanium alloys-an overview[END_REF].

Despite the large amount of experimental investigations and theoretical simulations, the hot deformation of metastable β titanium alloys with an initial single β phase in the α+β two phase region has seldom been addressed. The deformation process should be more complicated as the β to α phase transformation happens naturally in this temperature region. Although the β to α phase transformation and α variant selection criteria during hot deformation have been intensively studied both experimentally [START_REF] Bohemen | Nucleation and variant selection of secondary α plates in a β Ti alloy[END_REF]Hua et al., 2018) and theoretically [START_REF] Shi | Variant selection during α precipitation in Ti-6Al-4V under the influence of local stress -A simulation study[END_REF], the influence of the transformation, especially the transformation associated lattice deformation, on the mechanical response of the alloy has not yet been reported.

Based on such an observation, we conducted the present work with an aim to correlate the microstructure evolution with the hot compression stress-strain behavior of a β quenched metastable β titanium alloy (Ti-7333) to resolve the underlying mechanisms of the hot deformation behavior of the alloy. Special efforts have been made to the contribution of the β to α phase transformation at different deformation stages. Especially, for the steady state of deformation, the results of our previous work on variant selection of intragranular α precipitates under the same hot compression condition and on the associated lattice deformation feature (Hua et al., 2018) provided a solid basis for the present work to specify the role of the phase transformation as another kind of deformation mechanism for crystal plasticity. To obtain accurate and statistical experimental evidences, in-situ and ex-situ multiscale characterization techniques have been utilized and the examinations have been made on large sample volume or areas. This study is expected to provide more information to enrich the fundamental knowledge on hot deformation of Ti alloys and to offer experimental data for theoretical simulation utilizing various mechanical models.

Experimental procedures

The material used in the present work is hot forged Ti-7Mo-3Nb-3Cr-3Al (in wt. %). Cylindrical specimens with dimensions of Φ10 x 15 mm were cut out of the forged bar and solution-treated at 1173 K (Tβ ~ 1123 K. Tβ is the β transus temperature) for 30 minutes and quenched in water to obtain a homogeneous single β phase as the initial microstructure.

The as-solution treated specimens were then subjected to unidirectional isothermal compression using a Gleeble-3500 thermo-mechanical simulator system under vacuum (to prevent oxidation of the specimen and also the parts of the deformation frame of the Gleeble system exposed to the heat). The specimens were first heated to 973 K (the compression temperature) at a rate of 25 K/s and held for 5 s to homogenize the temperature, and then they were compressed at a strain rate of 10 -3 s -1 (that corresponds to a constant cross-head speed (mm/s) in the Gleeble simulator system) to the true strains of 0.015, 0.03 and 0.35, respectively. After being strained, the specimens were immediately quenched in water to preserve the deformed microstructure. In order to reduce friction and maintain a uniform deformation, two pieces of thin tantalum sheets were placed between the specimen and the compression die. The microstructural and crystallographic features of the deformed specimen were examined by post mortem characterization techniques from the macroscopic scale to the microscopic scale to ensure a statistical relevance of the results. For the phase constituents and the morphological features, the deformed specimens were examined using a Jeol JMF6500-F SEM. For the crystallographic features, the deformed regions were analyzed using a Jeol JMF6500-F SEM equipped with an EBSD camera and the Aztec online acquisition software package (Oxford Instruments). The orientations of the fine microstructural constituents (α precipitates) were measured manually and the coarse constituents (β grains) were measured automatically by EBSD. The data were processed using Channel 5 (Oxford Instruments) and ATEX software [START_REF] Beausir | Analysis Tools for Electron and X-ray diffraction[END_REF]. The examined total area (1.7 × 3 mm 2 ) covers the whole homogeneous deformation region in the cross section of the deformed specimen. To achieve the surface quality of the specimens for SEM and SEM-EBSD measurements, the specimens were first mechanically polished and then electrolytically polished with a solution of 10% perchloric acid in methanol at 35 V for 5 s at temperatures lower than 5°C. For the fine microstructure features of the deformed specimen, the examinations were performed using a Philips CM200 TEM equipped with a LaB6 cathode, a Gatan Orius 833 CCD camera, and a homemade automatic orientation analysis software -Euclid's Phantasies (EP) (Fundenberger et al., 2003). The TEM thin foil samples were prepared first by mechanical thinning to a thickness of about 70 μm and then by electro polishing to perforation at -35°C in a solution of 5% perchloric acid in ethanol at a voltage of 35V, using a Struers Tenupol-5 twin-jet electropolisher.

The isothermal compressions were also performed in-situ under neutron diffraction measurements at 973 K to the as β quenched specimens with the dimensions of Φ5mm x 10mm, using the rotatable multifunctional (tension/compression/torsion) loading frame incorporated in the STRESS-SPEC instrument. The loading frame is also integrated with a clip-on extensometer and a home-made inductive heating system. The specimens were heated in air to 973 K at a rate of 50K/s, then isothermally compressed to a true strain of 0.35 and finally cooled with compressed air. The neutron diffraction measurements were performed using the neutron diffractometer STRESS-SPEC located at a thermal beam port of FRM-II (Garching, Germany). The Ge (311) monochromator was selected to reflect neutrons with a wavelength of 1.7076 Å. The {110}β diffraction peak (corresponding to β phase), {0002}α and {101 1}α diffraction peaks (corresponding to α phase) were recorded at the detector position of 2θ=42° with a window of 15°. The diffraction patterns were collected in-situ during the heating, isothermal compression and cooling processes each at every 20 seconds.

The {110}β pole figure of the un-deformed specimen (as-solution treated or β quenched) and the {110}β and {0002}α pole figures of the same specimen after the deformation were measured ex-situ to find out the favorable diffraction measurement geometry allowing recording the reflections of the very first precipitation of the intragranular α precipitates according to our recent work on β to α transformation under compression (Hua et al., 2018). The experimental setup is detailed in Appendix.

The gauge volume of the specimens for the pole figure measurements was Φ5 × 10 mm. The software StressTextureCalculator (STeCa) [START_REF] Randau | StressTextureCalculator: a software tool to extract texture, strain and microstructure information from area-detector measurements[END_REF] was used to extract the diffraction patterns.

Results and discussion

3.1 Initial β quenched microstructure and lattice constants of the corresponding phases at deformation temperature Fig. 1 shows the EBSD orientation micrograph of the as-solution-treated microstructure of the Ti-7333 with the corresponding correlated disorientation angle distribution. It is seen that the alloy is composed of the single β phase in a form of equiaxed grains with an average size of about 119 ± 76 μm (Fig. 1(a)). Here the standard deviation indicates the size distribution spread but not the experimental error.

The β grains are rather randomly oriented than textured, as shown by the correlated disorientation angle distribution (Fig. 1(b)). Such a microstructure is typical of solution treated or β quenched metastable β Ti alloys (Hua et al., 2017;[START_REF] Lai | ω phase acts as a switch between dislocation channeling and joint twinning-and transformation-induced plasticity in a metastable β titanium alloy[END_REF]. The initial texture is represented by the {110}β pole figure in Fig. 1(c). It is seen that the texture is globally random. The uneven distribution of the pole densities is from two factors. The first one is that the grain sizes of the β grains are large. The total number of grains in the measured volume is relatively small (less than 1500).

Thus not all the orientation space is occupied by orientations. The second is that the grain sizes are not homogeneous (with a spread of ± 76 μm). Thus the individually located higher pole densities are from large grains. According to the variant selection criteria revealed by our previous results (Hua et al., 2018), The {110}β planes that can be the Burgers orientation relationship plane for the selected intragranular α precipitates during deformation can be determined. Thus the orientation of the specimen with respect to the incident beam and the detector can be figured out, as detailed in Appendix. In Fig. 1(b), the {110}β reflection used to monitor the phase transformation for intragranular α is indicated with the black square.

At the deformation temperature (973K) that is lower than Tβ (1123K), the β to α phase transformation happened. The lattice constants of the two phases at 973K measured previously (Hua et al., 2018) are listed in Table 1. These lattice constants will be used to analyze the lattice deformation during the β to α phase transformation.

Mechanical behavior

Figure 2 shows the true stress-strain curve and the corresponding work hardening rate curve of one specimen unidirectionally compressed to the true strain of 0.35.

From the true stress-strain (σ-ε) curve (in red in Fig. 2), it is seen that, as a function of the strain, the stress starts with a linear part, corresponding to an elastic deformation, then undergoes a sudden drop from the peak, the so-called discontinuous yielding, and finally reaches a steady-state. Such a stress-strain behavior of the present alloy is typical of isothermally compressed metastable β Ti alloys [START_REF] Mandal | Simulation of plastic deformation in Ti-5553 alloy using a self-consistent viscoplastic model[END_REF]. The It is seen that when the specimen was deformed to 0.015, the β grains still retain the equiaxed shape and there is no obvious grain growth.

The average grain size is about 121 ± 66 μm (Fig. 3(a)) (as noted above, the standard deviation indicates rather the size spread than experimental error). A close examination revealed that a large amount of α phase is present along the grain boundaries of the β phase but no α phase is spotted in the β grain interiors (Fig. 3(b)).

This evidences that the grain boundary α precipitates (αGB) were already formed before the end of the Stage I deformation, but the intragranular α precipitates were not yet formed till then. According to the presence and the morphology of the grain boundary α precipitates (αGB), the β grain boundaries can be categorized into 3 types:

with continuous αGB, with discontinuous αGB and without αGB, as shown in Fig. 3(b).

Statistical analysis made on a total area of 2 × 1 mm 2 revealed that 92% of the length of the β grain boundaries is covered by α precipitates. The majority part of the boundaries are covered by continuous α (89%), whereas only a very minor portion of the β grain boundaries by discontinuous α (3%), as shown in Fig. 6. This demonstrates that before the end of the first stage of the deformation (Stage I) the β to α phase transformation happened intensively on the β grain boundaries. Almost all the boundary regions were transformed to the α phase. As the α phase is harder than the β phase, the formation of the αGB strengthens the β grain boundaries.

From the Grain Gravity Center Referenced Orientation Deviation (GGCROD) analysis result displayed in Fig.

Stage III

Fig. 7 shows the neutron diffraction intensity evolutions of the {110}β reflection from the β phase and the {0002}α reflection from the α phase during the compression.

It should be mentioned that the diffraction intensity of the α phase is from the intragranular α, as the formation of the αGB ended before the end of Stage I (at the strain of about 0.015) and no α intensity was detected during this period, as seen in Fig. 7(a). This is due to the fact that αGB is very thin and distributed along the randomly oriented and coarse β grain boundaries. Thus the amount of αGB is not sufficient to produced detectable diffraction intensity. Moreover, during the in-situ neutron diffraction measurement, the detector position was fixed, not allowing detecting all the possible reflections from the αGB. Therefore, the diffracted intensity from the αGB may be largely submerged in the background noise. The experimental setup allowing such detection is detailed in Appendix. It is seen that the intragranular α started to precipitate with detectable amount at the strain of 0.14 (corresponding to 140s of the isothermal holding and in the middle of the steady stress-strain state, Stage III). After the transformation, the intensity of the diffraction peak of the α phase presents a very slow increase till the strain of 0.2 and stays stable afterwards, meaning that the transformation started very rapidly at the beginning and finished at strains about 0.2. Correspondingly in the stress-strain curve, the stress increases very slightly at 0.14 but decreases from 0.2. The slight upturning of the stress-strain curve in Stage III is coincident with the formation of the intragranular α precipitates. In the present work we found that such slip bands go through the entire β grains (type I). It is worth mentioning that no {112}β<111 >β dislocations were evidenced in the present alloy. The absence of this type of dislocations is consistent with what reported in the literature that the {112}β<111 >β slip system in BCC crystals are more easily activated at low deformation temperatures than at high temperatures [START_REF] Rollett | Recrystallization and related annealing phenomena[END_REF]. The formation of the slip bands should be related to the temperature effect.

Obviously recovery occurred intensively with the deformation. However, no recrystallized grains were detected, suggesting that there is no occurrence of recrystallization during the present compression to the strain of 0.35. In contrast, in the type II grains no dislocation bands were found existing in the zones where the α precipitates were intensively formed, as shown in Fig. 9(b), indicating that the deformation mechanisms are different in the two types of grains. In the former the deformation is controlled by dislocation activity and in the latter the deformation is accommodated mainly by phase transformation. These results demonstrate that the steady stress-strain behavior of the alloy is rooted from the different contributions of the two types of β grains. For the type I grains, the hardening from the multiplication of the dislocations is balanced by the rearrangement of the dislocations to the soft configurations (the slip bands in the present work) through dislocation movement, as the activation energy of the dislocation slip is decreased at elevated temperatures (Gloaguen et al., 2013;Groger and Vitek, 2013). For the type II β grains, the formation of the intragranular α precipitates should strengthen the type II β grain interiors. As they form intensively around the strain of 0.14, as shown in Fig. 7, the slight hardening shown by the stress-strain curve in Fig. 2 is due to the formation of the intragranular α precipitates in the type II β grains. With the further progress of the deformation from the strain of about 0.2, a slight but obvious softening can be seen in the stress-strain curve in Fig. 2.

The softening is mainly related to the dislocation rearrangement, but not by the formed intragranular α precipitates, as they did not show any fragmentation or spheroidization until the strain of 0.35.

Conclusions

The deformation process of a metastable β titanium alloy with a β quenched Hua, K., Zhang, Y., Kou, H., Li, J., Gan, W., Fundenberger, J.J., Esling C., 2017.

Composite structure of α phase in metastable β Ti alloys induced by lattice strain during β to α phase transformation. Acta Mater. 132, 307-326. Hua, K., Zhang, Y., Gan, W., Kou, H., Li, J., Esling, C., 2018. Correlation between imposed deformation and transformation lattice strain on α variant selection in a metastable β-Ti alloy under isothermal compression. Acta Mater. 161, 150-160.

Fig. 1

 1 Fig.1 (a) SEM-EBSD Y axis inverse pole figure (IPF) micrograph of the

  work hardening rate (dσ/dε) (in blue in Fig.2) well reveals the 3 stages of the present deformation. Thus we labeled them State I (elastic deformation), II (discontinuous yielding) and III (steady-state), as indicated in Fig.2. To further reveal the origins of the three deformation stages, we will focus ourselves only on the evolution of the deformation microstructure.

Fig. 2

 2 Fig. 2 Stress-strain (σ-ε) curve (in red) of the Ti-7333 alloy compressed at 973K to

3. 3

 3 Fig. 3 and Fig. 5 display large scaled microstructures of specimens deformed to

  Fig. 4(a). Further determination using the trace analysis method[START_REF] Zhang | A method to identify dislocations in a known crystal structure by transmission electron microscopy[END_REF]

Fig. 3

 3 Fig. 3 SEM-BSE and EBSD micrographs of the Ti-7333 deformed at 973 K to the

Fig. 4

 4 Fig. 4 TEM bright field micrographs of Ti-7333 alloy after being deformed at 973 K

Fig. 5

 5 Fig. 5 SEM-BSE and EBSD micrographs of the Ti-7333 deformed at 973 K to the

Fig. 6

 6 Fig. 6 Length percentages of β grain boundaries with continuous αGB, with

Fig. 7

 7 Fig. 7 Evolution of the diffraction intensities of the {110}β reflection of the β phase

Fig. 8

 8 Fig. 8 (a) EBSD band contrast micrograph of the Ti-7333 alloy after unidirectional

Fig. 9 Table 2

 92 Fig. 9 TEM bright field micrographs of Ti-7333 alloy after being compressed at 973

  figured out. The shear plane is perpendicular to the BOR plane, and the two planes

Fig

  Fig. A1 (a) Atomic correspondences between the β and the α phase under the Burgers

Fig

  Fig. A2 (a) {110}β pole figure measured by neutron diffraction at room temperature

Table . 1

 . The lattice constants of β and α phases in Ti-7333 alloy at 973 K(Hua et al., 2018).

	Phase Lattice structure	Lattice constants
	β	BCC	a=3.2471 Å
	α	HCP	a=2.9340 Å; c=4.6795 Å

Table 3

 3 Displacement gradient tensors of two α precipitates in one example of type I β grain and that of {110}β<11 1>β slip system of one example of type II β grain expressed in the sample X-Y-Z coordinate system. The compression is along Y axis.

	Precipitates No.	Displacement gradient tensor
	A	0.0238 0.0279 0.0225 -0.0224 -0.0999 -0.0812
		0.0216 0.0962 0.0952
	B	0.0945 -0.0757 -0.0152 0.1010 -0.0989 -0.0182
		-0.0308 0.0319 0.0234
		0.0032 -0.0276 0.0211
	(01 1)β[1 1 1 ]β	0.0214 -0.1824 0.1393
		0.0275 -0.2347 0.1792
		-0.0032 0.0276 -0.0211
	(01 1)β[111]β	-0.0214 0.1824 -0.1393
		-0.0275 0.2347 -0.1792

Acknowledgements

This work was supported by the Major State Research Development Program of China under Grant Nos. 2016YFB0701303 and 2016YFB0701305, the Program de Recherche Conjoint CNRS-NSFC under the Grant No. PRC1475, and the National Natural Science Foundation of China under Grant No. 51711530151. This work is based upon experiments performed at the STRESS-SPEC instrument operated by HZG and FRM II at the Heinz Maier-Leibnitz Zentrum (MLZ), Garching, Germany. The authors gratefully acknowledge the financial support provided by HZG and FRM II to perform the neutron scattering measurements at the Heinz Maier-Leibnitz Zentrum (MLZ), Garching, Germany. Ke Hua is grateful to the China Scholarship Council for the financial support for his Ph.D study in France.

boundary regions. For the steady-state stage, the deformation behavior of the β grains is further diversified into two types, i.e., type I having their {110}β<11 1>β slip system in the favorable orientation with respect to the external compressive load and type II with their {11 2 }β<1 11 >β system in the favorable orientation. Thus for the type I β grains the deformation progresses through the formation of {110}β<1 1 1>β dislocations counter-balanced by the arrangement of the formed dislocations into slip bands, whereas for the type II β grains the deformation is realized by the intensive formation of intragranular α precipitates that is characterized by a large shear strain in {11 2 }β<1 11 >β system accompanied by some small lattice distortions. This evidenced that the phase transformation serves as another kind of deformation mechanism for crystal plasticity. The present work provides new information of orientation dependent deformation mechanisms of metastable β titanium alloys, especially on the contribution of the phase transformation to the overall deformation behavior and offers detailed experimental data that can be useful for the simulation of the mechanical behavior of metastable β titanium alloys. A2 (a). This result verified our neutron diffraction setup to detect the formation of the intragranular α precipitates and further confirmed the variant selection criteria that we worked out previously (Hua et al., 2018).

Appendix