F Mayr
email: mayr@ort.edu.uyyovine@ort.edu.uy

S Yovine

F Pan

N Basset

T Dang

TOWARDS EFFICIENT ACTIVE LEARNING OF PDFA A PREPRINT

Keywords: Active learning, PDFA, Quantization

We propose a new active learning algorithm for PDFA based on three main aspects: a congruence over states which takes into account next-symbol probability distributions, a quantization that copes with differences in distributions, and an efficient tree-based data structure. Experiments showed significant performance gains with respect to reference implementations.

Introduction

We are interested in the problem of efficiently learning probabilistic deterministic finite automata (PDFA) in the context of the general active MAT-learning framework proposed in [START_REF] Angluin | Learning regular sets from queries and counterexamples[END_REF] where a learner and a so-called minimum adequate teacher interact by asking and responding questions, respectively. The learner's purpose is to unveil the hidden target automaton only known to the teacher. The latter allows the former to ask two kinds of questions, namely membership (MQ) and equivalence (EQ) queries.

MQ seeks to discover the automaton's outcome for a particular string. Originally, the purpose of MQ is to know whether a string belongs to the language to be learnt or, equivalently, whether it is accepted by the associated automaton. This name has been kept in later applications to other classes of automata. In [START_REF] Beimel | Learning functions represented as multiplicity automata[END_REF][START_REF] Bergadano | Learning behaviors of automata from multiplicity and equivalence queries[END_REF], the framework is used to prove learnability of multiplicity automata which compute functions mapping strings to elements of a field. In this case, the name MQ is retained even when the answer is the value of the computed function, which may not be Boolean. The same approach is followed in [START_REF] Weiss | Learning deterministic weighted automata with queries and counterexamples[END_REF] where MQ is used to refer to the function that returns the probability of the last symbol in a string.

EQ provides means for determining to what extent the hypothesis automaton produced by the learner approximates the target one. In the case of exact learning, this query checks whether they both produce the same outcome to MQ for all strings. When MQ are not binary, such as for PDFA, it could be useful to relax equality in order to learn similar hypotheses that tolerate small discrepancies. For instance, in [START_REF] Clark | PAC-learnability of probabilistic deterministic finite state automata[END_REF][START_REF] Tappler | L*-based learning of markov decision processes (extended version)[END_REF][START_REF] Weiss | Learning deterministic weighted automata with queries and counterexamples[END_REF] equality is replaced by a similarity relation. However, that similarity relation is not an equivalence as it lacks transitivity.

In the context of DFA, it is known that using appropriate data structures, such as trees, and efficiently processing counterexamples lead to significant gains in terms of computation time [START_REF] Isberner | The TTT algorithm: A redundancy-free approach to active automata learning[END_REF][START_REF] Kearns | An Introduction to Computational Learning Theory[END_REF]. To the best of our knowledge, these approaches have not yet been explored for active learning of PDFA. The algorithms proposed in [START_REF] Beimel | Learning functions represented as multiplicity automata[END_REF][START_REF] Kaznatcheev | Weighted automata are compact and actively learnable[END_REF] rely on MQ that compute the probability of a string and on an observation table to store the results. In [START_REF] Tzeng | Learning probabilistic automata and markov chains via queries[END_REF], MQ return state distributions, that is, the probability that the target probabilistic automaton enters a state after reading an input string. This requires knowing the number of states of the target in advance. These works focused on theoretical results without implementations of them being publicly available. In [START_REF] Feng | Learning-based compositional verification for synchronous probabilistic systems[END_REF], learning PDFA is a building block of an assume-guarantee framework for verification of probabilistic systems. MQ asks for the probability of accepting a string and results are stored in an observation table. However, the overall goal is not to learn a PDFA equivalent to a hidden target but only an appropriate assumption for doing a compositional proof of correctness. To achieve this, the algorithm uses an EQ that relies on language inclusion of PDFA and probabilistic model-checking. All these works rely on exact equality of MQ outcomes. To deal with noise in distributions, WL * [START_REF] Weiss | Learning deterministic weighted automata with queries and counterexamples[END_REF] proposes a non-equivalence similarity relation between probability distributions and develops an algorithm to learn similar hypotheses according to it. Note that WL * uses clustering to group responses to MQ stored in the table.

Based on these observations, we formulate a learning framework for PDFA where the teacher's answers to MQ are probability distributions over the symbols a string could be continued with. These are called next-symbol probability distributions. Besides, in the case the learner is allowed to produce hypotheses whose next-symbol probability distributions are approximations of the target ones, we propose to resort to quantization as an abstraction which allows us to define a coarser equivalence relation than the latter. This ensures the learnt automaton to be equivalent to the target one modulo this relation. Finally, we propose and implement QuaNT, a learning algorithm for PDFA that uses an adaptation of the tree structure of [START_REF] Kearns | An Introduction to Computational Learning Theory[END_REF]. In order to assess its performance, we compared QuaNT to a clustering-based algorithm that uses an observation table and a tolerance-based non-equivalence similarity relation, similar to WL * . The experiments carried out showed that QuaNT was orders of magnitude more efficient.

The paper is organized as follows. Section 2 gives core definitions and results of interest. Section 3 presents our PDFA learning algorithm QuaNT. Section 4 discusses experimental results. Section 5 summarizes the contributions.

PDFA

Let Σ be a finite alphabet and Σ $ to be the set Σ ∪ {$}, where $ is a special terminal symbol not in Σ. ∆(Σ $ ) is probability simplex over Σ $ . A PDFA A over Σ is a tuple (Q, q in , π, τ ), where Q is a finite set of states, q in ∈ Q is an initial state, π : Q → ∆(Σ $ ) associates a probability distribution over Σ $ to each state, and τ : Q × Σ → Q is the transition (total) function. Fig. 1(a-b) depicts an example. Let P q be the probability distribution over Σ * , such that P q = P (s|q) is the probability of s ∈ Σ * from state q ∈ Q, defined as:

P (λ|q) = π(q)($), λ is the empty string, P (σs|q) = π(q)(σ) • P (s|τ (q, σ)), σ ∈ Σ, s ∈ Σ * A PDFA A computes a function f A from Σ * to [0, 1]
. For any string s ∈ Σ * , f A (s) = P qin (s). For instance, the PDFA in Fig. 1 maps the empty string λ to 0 and every string a n , n ≥ 1, to 0.5 n . We define τ * (q, s) to be the natural extension of τ to strings, that is, the state reached by A when going through s starting at state q: τ * (q, λ) = q τ * (q, σs) = τ * (τ (q, σ), s)

Similarly, we define π * (s|q) to be the probability distribution of the state reached by A when going through s from state q:

π * (s|q) = π(τ * (q, s))

We denote by τ * (s) and π * (s) the state reached when going through s from the initial state q in and the associated distribution, respectively.

State equivalence

We define the relation ≡ as follows: for every q, q ∈ Q, q ≡ q if for every s ∈≡, π * (s|q) = π * (s|q ). Clearly, ≡ is an equivalence relation between states. Proposition 1.

∀q 1 ≡ q 2 ∈ Q, 1) π(q 1 ) = π(q 2 ), and 2) ∀σ ∈ Σ, τ (q 1 , σ) ≡ τ (q 2 , σ). That is, ≡ is a congruence. It follows that ≡ induces a quotient PDFA A/ ≡ = (Q/ ≡ , [q in ] , π/ ≡ , τ / ≡ ),
where Q/ ≡ is the set of equivalence classes, [q] ∈ Q/ ≡ denotes the class of q ∈ Q, and for any q ∈ Q, the probability distribution is π/ ≡ ([q]) = π(q), and the transition function is τ / ≡ ([q] , σ) = [τ (q, σ)] for any σ ∈ Σ.1 Proposition 2. For every PDFA A, A/ ≡ computes the same function as A.

Therefore, ≡ can be extended to PDFA. For every PDFA A and B, A ≡ B if their respective initial states q A in and q B in are equivalent, that is,

q A in ≡ q B in . Corollary 1. A ≡ B implies f A = f B .
The converse does not hold in general.

Minimality

A PDFA is minimal if any other PDFA that computes the same function has no less states [START_REF] Beimel | Learning functions represented as multiplicity automata[END_REF]. The simple PDFA in Fig. 1 is minimal since clearly the function cannot be computed by a PDFA with a single state. Based on ≡ we define a weaker notion of minimality as follows. A PDFA A is said to be weakly minimal if for every q, q ∈ Q, q ≡ q .By definition, for every PDFA A, A/ ≡ is weakly minimal. Proposition 3. Every minimal PDFA A is also weakly minimal. The converse does not hold in general.

An example of Proposition 3 is the PDFA in Fig. 1. However, the converse is not true, that is, there are weakly minimal PDFA which are not minimal. Consider for instance PDFA A and B in Fig. 2. We have that f B ((ab

) n+1 ) = (0.1 • 0.2)(0.2 • 0.1) n • 0.3 = (0.1 • 0.2) n+1 • 0.3 = f A ((ab) n+1
), for n ≥ 0. For any other string s = (ab) n+1 , f A (s) = f B (s) = 0. Hence, A and B compute the same function. Moreover, they are both weakly minimal because π * (λ|q) = π * (λ|q ) for every pair of states q, q ∈ Q, for each one of the automata, respectively. But B is certainly not minimal because it has more states than A. This example also shows that f A = f B does not entail A ≡ B.

Similarity of distributions

The equivalence defined above is not robust in the sense that two states whose probability distributions differ very slightly are not equivalent. Consider the PDFA A ε (c) in Fig. 1, where ε ∈ (0, 0.5]. It maps every string a n , n ≥ 1, to (0.5 -ε) n-1 (0.5 + ε). This PDFA is not equivalent to PDFA A in Fig. 1. However, f Aε tends to f A as ε tends to 0. Moreover, π(q 1 ) tends to π(q 1 ). Previous works have addressed this issue by introducing a tolerance parameter t. In [START_REF] Weiss | Learning deterministic weighted automata with queries and counterexamples[END_REF], states are compared using the probability of the last symbol of a non-empty string defined as:

π q (sσ) = π * (s|q)(σ) where σ ∈ Σ $ , s ∈ Σ * , q ∈ Q (1)
It is said that q, q are t-equal,

for t ∈ [0, 1], denoted q ≈ t q , if L ∞ (π q , π q ) ≤ t where L ∞ (v, v ) = max x |v(x) - v (x)|. PDFA A and B are t-equal, denoted A ≈ t B, if q A in ≈ t q B
in . However, this approach does not lead to an equivalence relation between states. That is why, to cope with small perturbations in probabilities while preserving equivalence between states, we propose to resort to a quantization defined over π * as follows.

Let κ ∈ N, κ ≥ 1, be a quantization parameter. For n ∈ N, 0 ≤ n < κ -1, we define I n κ to be the left-closed right-open interval nκ -1 , (n + 1)κ -1 , and for n = κ -1, the closed interval nκ -1 , 1 . Now, for every real number x ∈ [0, 1], we define x κ = I n κ such that x ∈ I n κ . For instance, for κ = 2, we have the quantization [0, 0.5), [0.5, 1]. Two numbers x, y ∈ R are κ-equivalent, denoted x = κ y if x κ = y κ . This definition extends naturally to ∆(Σ $ ). We denote ∆(Σ $ ) κ the partition of ∆(Σ $ ) induced by κ. For δ ∈ ∆(Σ $ ), δ κ is called the quantization vector of δ. For example, (0.1, 0.3, 0.6) 2 = (I 0 2 , I 0 2 , I 1 2 ). Being = κ an equivalence relation, we can define a quantized version of ≡ as follows: q ≡ κ q if for every s ∈ Σ * , π * (s|q) = κ π * (s|q ). This induces a unique quotient over states Q/ ≡κ . Moreover, ≡ κ can be extended to PDFA: for every PDFA A and B, A ≡ κ B if q A in ≡ κ q B in . This allows extending the notion of weakly minimality defined over ≡ to ≡ κ : A is said to be κ-weakly minimal if for every q, q ∈ Q, q ≡ κ q . However, unlike ≡, its quantized version ≡ κ does not induce a unique quotient PDFA because π/ ≡κ ([q] κ ) can be any distribution in π(q) κ . Therefore, we define

A/ ≡κ = {B | A ≡ κ B ∧ |Q A / ≡κ | = |Q B |}
, that is, the set of κ-weakly minimal PDFA which are κ-equivalent to A.

To illustrate quantization, consider the PDFA A (a) and A ε (c) in Fig. 1. Suppose ε ∈ (0, 0.1). For κ = 5, we have the quantization [0, 0.2), . . . , [0.8, 1]. Then, π(q 1 )(a) 5 = I 2 5 = [0.4, 0.6) = π(q 1 )(a) 5 , since 0.4 < 0.5 -ε < 0.5, and π(q 1 )($) 5 = I 2 5 = [0.4, 0.6) = π(q 1 )($) 5 , since 0.5 < 0.5 + ε < 0.6. Thus, we have that q i ≡ 5 q i . Hence, A ≡ 5 A ε . Proposition 4. For every q, q , if q ≡ κ q then q ≈ κ -1 q .

PDFA Learning: QuaNT

QuaNT is a learning algorithm that constructs a PDFA by interacting with a teacher which makes use of oracles MQ QuaNT and EQ QuaNT . It has three major differences with WL * . First, MQ QuaNT returns the next-symbol probability simplex of a string, that is MQ QuaNT (s) = π * (s) for s ∈ Σ * ; while MQ WL * (s) returns π qin (s), where π is defined in [START_REF] Angluin | Learning regular sets from queries and counterexamples[END_REF]. Second, it relies on quantization rather than on tolerance for comparing probability distributions. Since our quantization method induces a congruence, there is no need for clustering states. Third, along the lines of [START_REF] Kearns | An Introduction to Computational Learning Theory[END_REF] and [START_REF] Isberner | The TTT algorithm: A redundancy-free approach to active automata learning[END_REF] algorithms, QuaNT builds a classification tree instead of a table. Similarly to these algorithms, tree leafs are PDFA states identified by so-called access strings and inner nodes are distinguishing suffixes. Nevertheless, in QuaNT the tree is not binary but n-ary, where n is the number of different classes which ∆(Σ $ ) is partitioned into, and tree arcs and leafs are labelled with elements of ∆(Σ $ ) κ and ∆(Σ $ ), respectively. N-ary classification tree Given s ∈ Σ * , we denote [s] κ the class of the state reached by traversing s in the target PDFA A, i.e., [τ * (s)] κ . Hereinafter, we omit the quantization parameter κ when clear from context. The tree T Acc,Dis maintains a set Acc of access strings and a set Dis of distinguishing strings where for every pair of distinct strings s, s ∈ Acc: [START_REF] Angluin | Learning regular sets from queries and counterexamples[END_REF] [s] = [s ], (that is, τ * (s) ≡ κ τ * (s )), and (2) ∃d ∈ Dis s.t. π * (sd) = κ π * (s d). The distinguishing string that labels the root of the tree is always λ which is also an access string, so that the initial state of the PDFA can be accessed. Proposition 5. The number of leaves of T is at most |Q/ ≡κ |. Fig. 3 (left) shows an example of n-ary classification tree. The quantization parameter is κ = 10. Tree leafs correspond to the states of the PDFA shown on the right, identified with their associated access strings: Acc = {λ, 0, 1, 10}. Every leaf is labeled with a vector corresponding to the probability distribution of the state, where the first element is the probability of $, the second element is the probability of 0, and the last element is the probability of 1. For example: π(q λ ) = (0, 0.5, 0.5). Tree arcs are labeled with quantization vectors. To simplify the visualization, only partition indexes are shown. For instance, (0, 5, 5) corresponds to the quantization vector (I 0 10 , I 5 10 , I 5 10 ). The root λ of the tree has an arc for each one of the classes in which quantization partitions the set of probability distributions of the states of the PDFA. In the example, there are three, namely quantization vectors (0, 5, 5), [START_REF] Angluin | Learning regular sets from queries and counterexamples[END_REF][START_REF] De La Higuera | Grammatical Inference: Learning Automata and Grammars[END_REF][START_REF] Bergadano | Learning behaviors of automata from multiplicity and equivalence queries[END_REF], and (1, 3, 6), corresponding to distributions (0, 0.5, 0.5), (0.1, 0.6, 0.3), and (0.1, 0.3, 0.6), respectively. The tree explains that states q λ and q 1 are not equivalent, i.e., [λ] = q λ ≡ q 1 = [1], because π * (λ|q λ ) = π(q λ ) = π(q 1 ) = π * (λ|q 1 ), and they are distinguished by λ ∈ Dis. They are also not equivalent to q 0 and q 10 for the same reason. These two states, which have the same probability distribution, are indeed distinguished by the string 1 ∈ Dis because π * (1|q 0 ) = π(q 10 ) = π(q 1 ) = π * (1|q 10 ).

Finding the class of a state (sifting) Given a string s ∈ Acc, the tree allows to efficiently determine its class To this end, we define the sifting operation as follows. Sift starts at the root of T . Let d ∈ Dis be the distinguishing string at the current node of the tree. In this case, we perform a membership query to get MQ QuaNT (s d) and then we descend to the subtree labeled with such quantization vector. Sift continues in this manner until a leaf s ∈ Acc is reached, in which case, [s] = [s ]. If there is no arc labeled with the same quantization vector, we have discovered a new class and must update the tree (sift-update) by adding s to Acc with probability MQ QuaNT (s ) and a new arc (d, MQ QuaNT (s d) , s ). Sifting can be efficiently implemented because the number of membership queries is bounded by the depth of T , and finding quantization vectors and asking membership queries can be cached to minimize the number of vector comparisons and queries to the target system, respectively.

Building a tentative hypothesis A Given a tree T , it is easy to construct A using sift. Each state of A is uniquely identified with an access string in Acc. For each state q s , s ∈ Acc, and symbol σ ∈ Σ, τ (q s , σ) = q s , where s = sift(sσ), and π(q s ) is the probability distribution associated with the leaf node s. In the case that sift generates an update, the building process is restarted. Because of Prop. 5, this eventually terminates. Moreover, by construction, A is a PDFA.

Equivalence queries For EQ QuaNT we use an adaptation of Hopcroft-Karp where states are compared as follows: π( q) κ = π(q) κ , where q is a state of the target PDFA A and q is a state of the hypothesis PDFA A.

Processing a counterexample Let γ be a counterexample returned by EQ QuaNT , that is π * A (γ) = κ π * A (γ). Let γ i be the i-th symbol of γ, γ[i] be the prefix of γ of length i, i.e., γ[i] = γ 1 ...γ i , s i = sift(γ[i]), and s i the string associated to the state τ * A (γ[i]). Let 1 ≤ j ≤ |γ| be the first index such that s j = s j . This means that [ s j ] = [s j ] and s j-1 = s j-1 , but the states reached by A and A after traversing γ[j -1] are not equivalent since when continued with γ j they reach non-equivalent states. That is, [s j-1 ] = [γ[j -1]]. Therefore, T has to be updated by adding a new leaf node γ[j -1] representing the newly discovered class. Then, γ[j -1] is added to Acc. Now, let d ∈ Dis be the least common ancestor in T of s j and s j . Then γ j d is a distinguishing string for s j-1 and γ[j -1]. In terms of tree operations, the leaf s j-1 is replaced by an inner node γ j d and two children, namely s j-1 and γ[j -1].

Complete algorithm Algorithm 1 shows QuaNT pseudocode. The algorithm begins by executing BuildSin-gleStatePDFA which creates an initial hypothesis A, with a single state q λ with a loop for each symbol and executes

Experiment 2

In this experiment 10 random PDFA of nominal size n = 100 were generated for alphabet size m = 2, 4, 8, 16, 32. We compared QuaNT and L * p with κ = 1000 and t = κ -1 . Each algorithm was run 10 times for each PDFA. Fig. 5a shows the learning time medians for every alphabet size. As it can be seen L * p seems to be more sensitive to the growth in the alphabet size.

Experiment 3

In this experiment, we compare the algorithms for different values of tolerance and quantization parameter: κ = 10, 100, 500, 1000, 2000, 3000, with t = κ -1 . For every parameter configuration 10 random PDFA of nominal size n = 300 and alphabet size m = 2 were generated, and each algorithm was run 10 times for each PDFA. Fig. 5b shows the median learning times. As it can be seen both algorithms appear to stabilize its execution time after some parameters sizes (κ = 500, t = 1/1000).

Experiment 4

Here, QuaNT was evaluated on bigger nominal sizes n = 1000, 2000, 5000, fixing κ = 1000 and m = 2. For every parameter configuration, 10 random PDFA were generated and each algorithm was run 10 times for each PDFA. Fig. 6b shows median learning times. Clearly, QuaNT still manages to learn PDFA from systems that are intractable for L * p . Assuming a linear speedup of 0.2n from Experiment 4.1, the learning time of a PDFA of size 5000 would be almost a month for L * p .

Experiment 5

In previous experiments it is noted that nearly all states in the randomly generated PDFA have distinct next symbol distributions, that is, most states are distinguished by λ, thus producing shallow tree structures (depth 1 or 2 QuaNT maintains similar sizes to those observed in experiment 1 (Fig. 7b).

Conclusions

We defined a robust notion of similarity of states in PDFA based on a congruence over states and a quantization of their probability distributions. This induces a precisely defined inductive bias for PDFA learning as a set of quantized weakly minimal PDFA. Based on this, we developed a new PDFA active MAT-learning algorithm called QuaNT which uses an n-ary tree to efficiently learn a PDFA in the hypothesis space. In order to empirically assess the efficiency of QuaNT, we presented an adaptation of WL * , namely L * p , which works with a non-equivalence similarity relation over distributions and an observation table. Algorithms were compared on a number of randomly generated PDFA. The experiments confirmed notable execution time gains achieved by QuaNT.

Proof of Proposition 2 Clearly, for all q, q ∈ Q, if q ≡ q then P (s|q) = P (s|q ) for every s ∈ Σ * . Hence, P (s| [q in ]) = P (s|q in ).

Proof of Proposition 3 Suppose that A is not weakly minimal. Then, there are states in A which are equivalent. Thus, A/ ≡ , which computes the same function as A, has strictly less states than A, which contradicts the hypothesis.

Proof of Proposition 4 q ≡ κ q implies π * (s|q) = κ π * (s|q ) for all s ∈ Σ * . Therefore, π q (sσ) = κ π q (sσ) for all s ∈ Σ * , σ ∈ Σ $ . Then, |π q (sσ) -π q (sσ)| ≤ κ -1 for all s ∈ Σ * , σ ∈ Σ $ . Hence, q ≈ κ -1 q .

Proof of

Proof of Proposition 6

Termination First notice that all inner operations terminate. Second, when a counterexample is returned, the number of leaves of T increases by at least 1. Therefore by Proposition 5 and the fact that |Q/ ≡κ | ≤ |Q|, QuaNT terminates. Correctness When QuaNT terminates, the hypothesis A constructed is such that Q = Q/ ≡κ , π = π/ ≡κ , τ = τ / ≡κ . Therefore A ≡ κ A.

C Figures

q 0 0 q 1 0.5
a/1 a/0.5 π τ Q $ a a q 0 0 1 q 1 q 1 0.5 0.5 q 1 q 0 0 q 1 0.5 + ε a/1 a/0.5 -ε Figure 1: (a-b) PDFA over Σ = {a} with q in = q 0 . (c) PDFA A ε . q 0 0 q 1 0 q 2 0.3

  [s ]. That means either finding an access string s ∈ Acc such that [s ] = [s] or creating a new class by adding s to Acc.

Proposition 5

 5 If s, s ∈ Acc then [s] = [s ], hence |Acc| ≤ |Q/ ≡κ |.

9 Figure 2 :

 92 Figure 2: PDFA A (left) and B (right).

3 Figure 3 :

 33 Figure 3: An n-ary classification tree (left), and the corresponding PDFA (right)

Figure 4 :

 4 Figure 4: Experiment 1

Figure 5 :

 5 Figure 5: Experiments 2 and 3.

Figure 6 :

 6 Figure 6: Experiments 1 (Speedup) and 4.

  ). In order to analyze cases where states share next symbol distributions we parameterized the PDFA random generation by a number d of distributions to use. The algorithm first randomly generates a set of d distributions and then labels each state by uniformly picking one in this set. Regarding structure sizes, L * p 's observation table grows bigger than previous experiments, being negatively affected by smaller values of d. However

For this experiment, 10 random PDFA over a binary alphabet (m = 2) of nominal size n = 300 were generated for different values of d (ranging from 2 to 16). Each algorithm was run 10 times for each PDFA. For QuaNT, κ = 1000, and for L * p , t = κ -1 (Prop 4). Fig.

7a

shows learning time medians for every d value. Notably, L * p execution time still grows faster than QuaNT's. The only case where QuaNT achieves worse learning time than L * p is for d = 2. Otherwise, QuaNT significantly benefits from the increase in d.

This quotient is different from[START_REF] Thollard | Probabilistic DFA inference using Kullback-Leibler divergence and minimality[END_REF] defined by a partition resulting from merging states according to a compatibility criterion which is not an equivalence relation.

Acknowledgments Research reported in this article has been partially funded by the following grants: ANII-Agencia Nacional de Investigación e Innovación FMV 1 2019 1 155913, and the ANR-JST CREST project on Formal Analysis and Design of AI-intensive Cyber-Physical Systems (CyPhAI) funded by the French National Research Agency ANR and Japan Science and Technology Agency JST.

MQ QuaNT (λ) to get the probability distribution for the state. Then, it calls EQ QuaNT ( A, κ), which either returns ⊥ and terminates or a counterexample γ enabling the initialization of the tree. The first tree T has a root labeled with the distinguishing string λ and two children, one with the access string λ and the other with the counterexample γ. Once T is initialized, the main loop of the algorithm begins. It consists in using T to build a PDFA A, then using EQ QuaNT to compare it with the target PDFA A. If a counterexample is returned, T is updated, resulting in new states being discovered. Otherwise it means all states in Q/ ≡κ have been found which implies A ≡ κ A. Proposition 6. For any PDFA A, QuaNT terminates and computes a PDFA A ∈ A/ ≡κ .

Experiments

In this section we present the results of the experiments carried out to compare QuaNT with a clustering-based algorithm that uses an observation table and a tolerance-based non-equivalence similarity relation, similar to WL * , that we call L * p (see Appendix A). We compared the learning algorithms on randomly generated PDFA. The generation technique works in two steps. First, it constructs random DFA over Σ. Second, DFA are transformed into PDFA by assigning a probability distribution over Σ $ to every state. The first step uses the method described in [START_REF] Nicaud | Random deterministic automata[END_REF] based on results from [START_REF] Carayol | Distribution of the number of accessible states in a random deterministic automaton[END_REF]. Let n be the desired number of reachable states of a DFA, called its nominal size. The method consists in randomly generating DFA of a total of n • m • ρ -1 m possibly unreachable states, for m = |Σ|, where

and W 0 is the Lambert-W function, and then computing its accessible part by a depthfirst traversal. It is important to remark that this method does not guarantee the actual size of the accessible part to be exactly n, but to be normally distributed around n. To obtain exactly n accessible states, the method could be repeated using a rejection algorithm. However, in practice, this proved to be very inefficient, being almost impossible to generate DFA of accessible size bigger than 100 in reasonable time. All experiments threw perfect scores for all computed metrics (word error rate, normalized discounted cumulative gain, log probability error [START_REF] Weiss | Learning deterministic weighted automata with queries and counterexamples[END_REF]) for all algorithms on the same test set of strings. Therefore, the analyses of the experimental results are mainly focused on execution time and structure size. For ease of comparison, figures show trend lines.

Experiment 1

In this experiment we compared QuaNT and L * p . For this, 10 random PDFA over a binary alphabet (m = 2) of nominal sizes n = 100, 200, 300 were generated, and each algorithm was run 10 times for each PDFA. For QuaNT κ = 1000, and for L * p , t = κ -1 (Prop 4). Fig. 4a shows learning time medians for every actual size. Notably, L * p execution time grows much faster than QuaNT's. Indeed, QuaNT achieves a speedup of approximately 0.2n, reaching around 60x for the biggest PDFA (see Fig. 6a). This experiment also showed that the size of L * p 's observation table grows bigger than QuaNT's tree which partly explains the gains in execution time (Fig. 4b).

A L * p

Here we present L * p , a variant of WL * [START_REF] Weiss | Learning deterministic weighted automata with queries and counterexamples[END_REF]. Similarly, it uses an observation table O P re,Suf for storing outcomes of MQ L * p , where P re ⊂ Σ * is the set of prefixes (stored in row indices) and Suf ⊂ {$} ∪ Σ + is the set of suffixes (stored in column indices). For every p ∈ P re and s ∈ Suf , O P re,Suf [p, s] = MQ L * p (ps) = π qin (ps), where π is defined in [START_REF] Angluin | Learning regular sets from queries and counterexamples[END_REF]. Unlike WL * , P re is divided in two parts [START_REF] De La Higuera | Grammatical Inference: Learning Automata and Grammars[END_REF], namely RED which are the rows used to construct states, and BLUE which are the rows representing continuations. The algorithm ensures that for every row in RED all its continuations are in P re. L * p consists of three main steps. The first one expands O P re,Suf through the use of MQ L * p until it becomes closed and consistent. The second one constructs a hypothesis automaton using a greedy clustering technique rather than DBScan. The third one calls EQ L * p with the proposed hypothesis. For this we adapted Hopcroft-Karp algorithm for checking t-similarity. When A and A are found to be not t-similar, EQ L * p returns a counterexample which is added to RED together with all its prefixes, and all their continuations to BLUE (provided they are not already in RED). These steps are repeated as long as EQ L * p yields a counterexample, otherwise it stops and returns the last hypothesis.

B Proofs

Proof of Proposition 1 1. By hypothesis, π * (λ|q 1 ) = π * (λ|q 2 ). By definition, π * (λ|q i ) = π(q i ), i = 1, 2. Therefore, π(q 1 ) = π(q 2 ).

2. By hypothesis, ∀s ∈ Σ * , π * (σs|q 1 ) = π * (σs|q 2 ). By definition, π * (σs|q i ) = π * (s|τ (q i , σ)), i = 1, 2. Thus, ∀s ∈ Σ * , π * (s|τ (q 1 , σ)) = π * (s|τ (q 2 , σ)). Hence, τ (q 1 , σ) ≡ τ (q 2 , σ).


Cécile Rampelberg
email: cecile.rampelberg@univ-lorraine.fr

Sébastien Yves

Pierre Allain

Guillaume Geandier
email: guillaume.geandier@univ-lorraine.fr

Julien Teixeira
email: julien.teixeira@univ-lorraine.fr

Florimonde Lebel
email: florimonde.lebel@univ-lorraine.fr

Thomas Sourmail
email: thomas.sourmail@ascometal.com

Carbide-Free Bainite Transformations Above and Below Martensite Start Temperature Investigated by In-Situ High-Energy X-Ray Diffraction

Keywords: steel, bainite, carbon, synchrotron, tetragonality, multi-step

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

Carbide-Free Bainites (CFB) are multiphase microstructures obtained from austenite decomposition at low temperatures (typically between 450 °C and 300 °C) in alloyed steels which have a high potential for industrial applications [1][2][3][4][5][6]. They are made of a fine ferritic matrix with a lath morphology without carbide, retained austenite stabilized by carbon partitioning during the transformation and fresh martensite appearing during the final cooling after bainite transformation [1]. Such metastable microstructure can be obtained as the CFB transformation is displacive and incomplete [3,[7][8][9]. The high fraction of residual austenite may transform during further mechanical loading at room temperature (stress or strain induced transformation) and leads to a possible TRIP effect (TRansformation Induced Plasticity) [3,[10][11][12][START_REF] Bhadeshia | Bainite in Steels: Transformations, Microstructure and Properties[END_REF][START_REF] Tournoud | Caractérisation Multi-Échelle d'un Acier Bainitique Microallié à Effet TRIP[END_REF]. These microstructures have been investigated for over 20 years but the criterion for the incomplete transformation phenomenon remains one of the current bones of contention in the literature [START_REF] Fielding | [END_REF]. Diffusionless theories of bainite transformation assume a thermodynamic limit called the T 0 ' line (nucleation controlled) [START_REF] Bhadeshia | Bainite in Steels: Transformations, Microstructure and Properties[END_REF]16]. During the transformation, the austenite gets progressively enriched by the carbon rejected by the bainitic ferrite. In the so-called "diffusionless" approach, at a given temperature, the nucleation of new bainite units stops when the carbon concentration in austenite exceeds a critical value corresponding to the composition for which both austenite and ferrite have the same Gibbs's energy. This mechanism leads to an incomplete transformation or a stasis. The T 0 line is the locus of these critical carbon concentration in austenite as a function of the temperature. Thermodynamically, the formation of bainitic ferrite without change of carbon composition is no more possible when the T 0 temperature goes below the transformation temperature. The T 0 ' curve takes also into account of the elastic strain energy stored in ferrite (ca. 400 J.mol -1 ) in the Gibb's energy calculation [START_REF] Bhadeshia | Bainite in Steels: Transformations, Microstructure and Properties[END_REF]. Whereas diffusive theories consider a stagnant process (dissipative mobility of interfaces) during isothermal holding (growth controlled) [17]. The objective of this work is to bring new experimental evidences to feed this discussion; in particular, we will establish very precise carbon balance between phases and challenge the T 0 ' criterion.

In this work, we have studied the formation of CFB microstructures at different temperatures in isothermal conditions from a fully austenitic state by in-situ High Energy X-Ray Diffraction (HEXRD) experiments. If the transformation occurs above the martensite start temperature (M S ), the final microstructure is composed of bainite (noted B), retained austenite (noted A) and fresh martensite (noted FM). It is far more difficult to study the bainitic transformation below M S as the martensitic transformation occurs almost instantaneously, prior to the bainitic ones. The final microstructure in that case contains also tempered martensite (TM). In order to investigate how the initial austenite state affects the transformation below M S , two multistep treatments have been designed. Instead of studying the transformation after a partial martensitic transformation, such treatments investigate it after partial bainitic or bainitic/martensitic transformations.

For such transformations, in-situ HEXRD experiments allow for simultaneous measurements of phase transformation kinetics, austenite lattice parameter changes, and evolution of bainitic phase tetragonality all along an uninterrupted isothermal treatments. In addition, minor carbide precipitation processes can be identified [18]. As a consequence, rigorous carbon balance between phases can be established especially in isothermal conditions above M S . To the knowledge of the authors, this is the first time that such level of consistency is obtained between the estimation of the carbon content in austenite and the carbon kept in supersaturation in bainite [19].The microstructures after thermal treatments have also been studied by Scanning Electron Microscopy. By coupling these observations, it was possible to finely estimate the stability of retained austenite at room temperature after the different cooling schedules.

Experimental procedure

The studied industrial steel is produced by Ascometal [20] and has a base chemical composition of Fe-0.27C-1.5Mn-1.2Si-0.8Cr (wt.%). For the investigated samples are cylindrical with a size of 10 mm length and 4 mm diameter. Each sample is machined from the mid-radius of a hot-rolled steel bar (⌀ 40 mm).

The in-situ HEXRD experiments were performed on the P07 beamline at PETRA III at Deutsches Elektronen-Synchrotron (DESY), Hamburg, Germany. A synchrotron X-Ray monochromatic beam (500 x 500 µm²) with a high energy (100 keV corresponding to a wavelength λ = 0.123984 Å) was used to illuminate the sample and to work in transmission in a powder diffraction configuration. The high photon flux from the synchrotron source and the large 2D detector (Perkin-Elmer) with slow and fast acquisition mode, allow collection of Debye-Scherrer diffraction patterns at different rates (10 Hz or 0.3 Hz respectively). The sample was heated with a Bähr DIL 805 A/D dilatometer. The temperature was measured with a thermocouple welded directly on the cylindrical specimen.

In this paper, different thermal conditions were studied: conventional isothermal holdings and multistep conditions. Multi-step cooling sequences are a succession of isothermal holdings at different decreasing temperatures. All these thermal treatments started with an austenitic soaking at 3 °C/s up to 1150 °C for 3 minutes leading to a Prior Austenite Grain (PAG) size around 74 ± 42 µm close to that achieved after hot forging of relatively large components such as automotive crankshafts, wheel hubs, etc. The transition between all the isothermal temperature steps is performed at 50 °C/s. Figure 1 a) shows the temperature as a function of time schedules for isothermal conditions, with temperatures ranging between 300 °C and 475 °C and holding time is set up at 20 minutes. The investigation of bainite transformation was made below and above the M S (Martensite start temperature); as the M S of the alloy is about 350 °C (346 °C) as determined by dilatometry experiment. Using calculations of the M S in the literature as proposed by Van Bohemen [21] and Nehrenberg [22] we found 356 °C and 333 °C respectively. Those results are closed and in agreement with the one determined experimentally. Above M S and at M S , the experiments are denoted by the letter B followed by the transformation temperature. At 300 °C (below M S ), the martensite fraction prior to bainite transition was estimated by the Koistinen-Marburger relation around 61 wt.% [START_REF] Forgeoux | Application Des Structures Bainitiques Par Transformation Isotherme et d'un Traitement de Surface Adapté Aux Vis à Haute Résistance[END_REF]. The corresponding experiment will further denoted M+B300. The experiments above M S will further be denoted as BXXX (XXX = 350, 400, 450 or 475). Isothermal holdings are followed by a cooling down to room temperature.

Figure 1 b) shows the heat treatments corresponding to the multi-step cooling sequences discussed above. The two-step schedule consists in a first step at 400 °C during 40 seconds, followed by a second step at 300 °C during 20 minutes. During the first step, a partial bainitic transformation at 400 °C is expected (typically 30 wt.% of bainite). As the stabilization of austenite is not sufficient in such conditions, a partial martensitic transformation occurs during the transition between the steps. Finally, a bainitic transformation should occur in the untransformed austenite at 300 °C. The designed microstructure is composed of bainite, martensite and bainite at 300 °C. The experiment will be denoted B+M+B300 in the following.

The three-step cooling sequence aimed at studying the bainitic transformation at 300 °C after a well developed bainitic transformations at higher temperatures. Here, a sufficient enrichment of retained austenite is expected to avoid any martensitic transformation. It consists in a first step at 475 °C during 115 seconds then a second step and third step at 400 °C and 300 °C respectively during 20 minutes at each step. The designed microstructure is thus composed of two types of bainite and bainite at 300 °C. The experiment will be denoted B+B300 in the following. As for isothermal holdings, both multi-step conditions are followed by a final cooling to room temperature with a cooling rate of 50 °C/s. The two-dimensional X-Ray patterns obtained during experiments were integrated circularly with the PyFAI python library [START_REF] Ashiotis | [END_REF]. Sample to detector distance and detector orthogonality to the beam had been calibrated using LaB6 powder (NIST 660a). The one-dimensional diffractograms were analyzed following a Rietveld [25] refinement method using FullProf [26]. The pseudo-Voigt function was used in the Rietveld refinement to simulate diffraction peaks. In this refinement, two phases were considered: austenite with a cubic face centered structure (Fm-3m) and bainite and martensite with a body-centered tetragonal structure (I/4 mmm). The R-factor was used for each phase as the indicator of the quality of simulation [27]. During the present experiments, it was not possible to discriminate between these last two phases on the basis of diffraction patterns. The mass fraction of BCT phase thus corresponds to the sum of the bainite and martensite contribution. However, as they appear sequentially, their respective transformation kinetics can be identified uniquely by a metallurgical reasoning on the basis of existing knowledge.

It must be mentioned that the BCT structure systematically leads to a better adjustment than a BCC (Body-Centered Cubic) structure. This has already been observed in previous studies by some groups [28][29][30][31][32]. This justifies the use of a tetragonal unit cell to assess the carbon content in solid solution in bainitic ferrite (in absence of tempered martensite of course).

For all experiments, the mean austenitic grain size is 74 ± 42 µm at high temperature and are thus large compared to the studied volume (500 x 500 x 4000 µm 3 ). In the two-dimensional X-rays patterns, the Debye Scherrer rings are discontinuous and exhibit many spots shown in Figure 2 a) as a consequence. These spots affect the austenite peak shapes on the 1D diffractograms shown in Figure 2 b). It is therefore impossible to determine the evolution of the austenite phase with good accuracy from the high temperature and at the very beginning of the bainite transformation. These spots jeopardize not only the correct measurement of the phase fraction but also the austenite lattice parameters. The value becomes exploitable only after a certain amount of bainite transformation. The detection threshold makes possible to after quantification 15 wt.% of bainite transformation only. For isothermal holding above M S (350 °C and above), the bainite mass fraction increases as a function of time (above 350 °C). Bainite formation kinetics exhibit a sigmoidal curve and do not reach a full transformation. The maximum fraction of bainite formed strongly decreases with increasing isothermal temperature, this is consistent with well established incomplete transformation phenomenon in the presence of Si additions [2,33]. The higher the temperature, the lower the initial transformation rate and the lower the transformed fraction when then the plateau is reached. For the B350 experiment, the slope at the end of the treatment remains significant meaning that the transformation is not strictly finished (the stasis is probably not reached). [9] The isothermal transformation at 300 °C occurs below the M S temperature. The kinetics of M+B300 experiment presented in Figure 3 b) are thus the sum of two contributions; first, a martensitic transformation followed by a bainitic one. In order to compare the bainite transformation rate only in austenite, kinetics have been normalized to consider only the transformation of austenite remaining after the martensitic transformation (between M S and 300 °C, corresponding to a fraction of F M = 56 wt.%). Figure 3 b) shows the normalized kinetics for the different isothermal treatments as a function of time. The normalized bainite mass fraction F B is calculated as equation 1 :

Results

Kinetics of bainite and martensite transformation in isothermal conditions

(1)

where , and are respectively the total mass fraction of BCT phases (data from Figure 3), the mass fraction of martensite and austenite prior to the bainite transformation.

When comparing the normalized results, the rate of bainite transformation at 300 °C is slower than the one obtained at 350 °C [33,34]. There still a controversy about the nature of time dependent transformation observed in such alloys below M S temperature [34]. The nature of the final product is claimed to be bainitic or martensitic. Some authors as Kim et al. [35] statute that is an athermal martensitic transformation. However, some authors as Van Bohemen et al. [36] consider that the final product as bainite. In our article, the isothermal transformation below M S is also considered as a bainite transformation. Nevertheless, this bainitic nucleation is strongly affected by the prior martensitic transformation in the sense that it provides new nucleation sites for bainite, stimulating the autocatalytic nucleation processes at martensite/austenite interface as reported by Ravi et al. [37] by example. The accelerating effect of a prior martensitic transformation often observed in the literature is not put in evidence in our experiment of M+B300 [37]. The bainite fraction reached at the end of the experiment M+B300 is 77 wt.%, lower than the fraction obtained at stasis for B400. For B350, the stasis of the transformation is obviously not achieved as the slope remains significant. Nevertheless, data obtained for isothermal transformation at 300 °C (M+B300) will be used in later discussion of multi-step experiments.

When cooling the samples down to room temperature, fresh martensite (FM) can be formed if austenite is not sufficiently stabilized by carbon partitioning. Table I shows the final composition of the microstructures. The martensitic transformations during final cooling start at temperature lower than expected by the local M S temperature. Moreover, due to the possible distribution of carbon in between austenite islands, it is more difficult to detect correctly the begin of the transformation which is more sluggish in this latter case. The M S calculated using the experimental carbon content determined by HEXRD experiments have been reported now the Table I for the sake of comparison the M S temperature calculated and predicted in the last columns of Table I below were obtained using the empirical formula Van Bohemen [21] and Steven & Haynes [38]. The fraction of FM drastically increases with holding temperature, at the expense of the fraction of austenite reported in Figure 3 b). The highest value of retained austenite fraction at room temperature is obtained after a transformation in B400 in the investigated conditions. For isothermal transformations at 400 °C and below, the fresh martensite fraction formed at the end of the thermal treatment is low (close to zero wt.%). This is consistent with a greater austenite carbon enrichment at these temperatures. For isothermal transformations at 450 °C, a significant fraction of martensite forms during final cooling, consistent with a M S temperature well above room temperature (lesser austenite carbon enrichment).

Table I : Phases fractions at room temperature in isothermal conditions measured by HEXRD and the M S calculated using [21] and [38]. 4. Final microstructures are composed with bainite plates (B), retained austenite (A) and fresh martensite (FM). (M+B300 experiment was not considered in this analysis).

Isothermal

The etching is sensitive to the carbon content of the phase. The lower the carbon content, the stronger the response to etching. Bainite is thus appearing in dark contrast whereas austenite and martensite are hardly etched. Martensite shows a weak roughness and austenite remains completely smooth. At 350 °C, some transition carbides appear also in bright contrast in bainitic laths. Those observations are consistent with the HEXRD shown above and discussed later on. At the end of the first step, the mass bainite fraction is 25 wt.% and stasis is obviously not reached. During the transition between 400 °C and 300 °C, a partial martensitic transformation occurs (about 43 wt.%). The bainitic transformation restarts during the second step at 300 °C but with a lower rate than at 400 °C. The fraction transformed at 300 °C is 22 wt.%. The measured fractions of austenite, martensite and bainite along the schedule are summarized in Table II. The maximal bainite and martensite mass fraction at the end of the two-step holding is equal to 90 wt.%.

Kinetics of bainite transformation in multiphased microstructures

Figure 5 c) shows the evolution of the bainite mass fraction as a function of time for the three-steps treatment B+B300 (green). During the first step at 475 °C, the bainite mass fraction follows the kinetics observed in isothermal transformation as shown in Figure 6. Figure 6 represents the kinetics of bainite/martensite transformation during B+300 experiment and isothermal transformations at 475 °C, 400 °C and 300 °C. At the end of this first step, 22 wt.% of bainite at 475 °C is formed. A change in slope is observed around 120 s, this change in slope is associated with the beginning of the second step. During the second step at 400 °C, the transformation thus continues. The kinetics are slower than the ones observed during the B400 experiment alone for the corresponding fraction of bainitic ferrite formed. However, the bainite mass fraction reached at stasis during isothermal transformation of B400 is slightly higher (around 85 wt.%) than the maximal value of bainite mass fraction at stasis after a multi-step heat treatment of B+B300 (around 80 wt.%). These experiments highlight that a bainite transformation can restart at a lower temperature if the bainite fraction is not large enough. The bainite transformation thus does not respect the additivity rule as observed by Hasan et al. [39].

The estimated fractions main phases (austenite and bainite) formed during the first step at 400 °C and bainite formed during the second step are presented in Table II. Table II : Summary of the microstructures compositions (in wt.%) before and after the bainitic transformation at 300 °C (at the end of the step, before final cooling). A = Austenite, TM = Martensite, BXXX = Bainite obtained at XXX °C.

M+B300 B+M+B300 B+B300

Figure 5 d) shows the normalized bainite kinetics in remaining austenite during M+B300 isothermal holding (blue) and during the last step at 300 °C for the B+M+B300 (purple) and B+B300 (green) conditions respectively (see Figure 1). The reference time (t = 0) is fixed here at the beginning of the 300 °C holding for the sake of comparison. The bainite kinetics show here sigmoidal (or saturating exponential) shapes with different saturation levels. In all cases, the bainite mass fractions however do not reach a plateau meaning that the transformation is not finished.

In isothermal conditions at M+B300 (after 56 wt.% of martensitic transformation), the transformation rate is higher than the kinetics during the holding at 300 °C in B+M+B300 condition (after 68 wt.% of B/M transformation). The fraction of bainite at 300 °C at the end of the steps are also very different (34 wt.% and 22 wt.% respectively). These results are surprising as the fractions of austenite at the beginning of the transformation are similar (44 and 32 wt.% respectively) as well as their local carbon content. For the 300 °C bainite transformation during the last step of the B+B300 cooling sequence, less than 1 wt.% of bainite formed, meaning that the transformation at 300 °C is completely inhibited in that case, permitting to maintain a higher fraction of retained austenite at the end of the step (19 wt.% instead of 10 wt.%). The conditions of stasis are thus very different compared to the two previous cases. Moreover, this highlights that bainite transformations do not respect the additivity rule.

Evolution of the tetragonality

The c and a lattice parameters of the BCT phase were obtained from the Rietveld refinement of insitu acquired data. This measurement is not affected by the possible mechanisms disturbing the widths of the diffractions peaks; as the tetragonality is observed solely on certain diffraction peaks. The changes in c/a ratio evolutions may be divided in two parts: at the beginning of the bainite transformation, the c/a ratio increases rapidly during the first 100 seconds. During the second stage, it decreases continuously while remaining above 1 (value corresponding to an ideal body-centered cubic structure). The lower the holding temperature, the higher the c/a ratio. For all studied isothermal holdings, the evolution of austenite lattice parameters show a sigmoidal shape. Hence, for all temperatures, an enrichment in carbon in austenite is observed during bainite formation if we neglect the transformation stresses.

Austenite lattice parameter

At low temperature (350 °C), the austenite lattice parameter does not show any saturation regime at the end of the experiment (after 20 minutes). This is consistent with the transformation kinetics observed at the same temperature. The transformation still continues during the whole experiment without reaching a real stasis.

On the contrary, for B400, B450 and B475 experiments, a stasis is observed. The higher the transformation temperature, the lower the increase in the austenite lattice parameter is at the end of the holding. The carbon enrichment of austenite at stasis decreases as the temperature increases.

A quantification of the carbon enrichment thanks to the Dyson and Holmes equation [40] will be discussed in the next section.

The evolution of austenite lattice parameters for transformations below M S are analyzed and discussed in supplementary materials (Figure S1).

Discussion

Transformations above M S

In this section, only the experiments B350 to B475 will be discussed as the microstructures along the studied isothermal holdings contain only two phases, i.e. bainite and austenite (before the final cooling during which a martensitic transformation can occur). Thanks to the measurement of the austenitic lattice parameter and the bainite tetragonality, it is possible to establish a rigorous carbon mass balance between the phases, all along the treatments. This mass balance helps characterizing, in particular, the local composition of the phases at the end of the treatment, when the transformations reach their stasis (or almost a stasis as it is the case at 350 °C). The compositions in both phases are then discussed in light of the different theories about bainitic transformations.

Finally, it will be shown that the balances also permit to provide evidence that a minor fraction of carbides also precipitates during the transformation at lower temperature. This precipitation is confirmed by a careful direct observation of the diffraction patterns and of final microstructures after etching.

For the other experiments (M+B300, B+M+B300, B+B300) multiple phases are formed which jeopardizes the establishment of this balance in a reliable way.

Evolution of the carbon content in the constituting phases (bainite and austenite)

The austenite lattice parameter can be tracked all along the treatment as shown in Figure 7 b).

Assuming the variation of the parameter is solely due to the carbon enrichment of austenite due to carbide-free bainitic reaction, and thus neglecting any evolution in the hydrostatic internal stress of the phase due to the displacive transformation, the carbon content in retained austenite can be calculated using the equation from Dyson and Holmes [40]:

(

) 2
where and are the carbon content in retained austenite and the initial carbon content of the phase before transformation (0.27 wt.%) given in wt.% respectively, and are the austenite lattice parameter of the carbon-enriched retained austenite and the austenite lattice parameter reference before bainite transformation starts given in Å respectively. This last parameter depends on the transformation temperature as shown in Figure 7 b). This procedure to evaluate the local composition in austenite is very common and has been exploited extensively in previous papers [2,41,42]. It is well established that carbon is not homogeneously distributed throughout the austenite. The films of retained austenite are often more enriched than blocky austenite. The carbon content measured by HEXRD appears to be a mean value. This has been clearly demonstrated by Pushkareva et al. on two very similar alloys and transformation conditions. The final austenite carbon content measured by HEXRD have been compared to [43] direct measurements of the carbon content in austenite by EELS (Electron Energy Loss Spectroscopy); in nano-bainitic steels, Garcia-Mateo et al. [42] using APT (Atom Probe Tomography) observed a strong dispersion in carbon content values. The austenite carbon content measured by HEXRD is a mean value taking into account the film-like austenite carbon-rich and blocky austenite carbon-poor, an closer to these last values. As done by some authors [2,44], the heterogeneity of carbon content can be estimated taking into consideration two austenite phases in the Rietveld refinement procedure. The fact the HEXRD leads to mean carbon content measurement close to the ones that could be given by EELS or by APT sustains the hypothesis that the hydrostatic stresses do not play a major role in the evolution of the lattice parameter of austenite during the bainitic transformation and do not affect in turn the measurement of carbon content. It must be mentioned that it is not the case if the bainitic transformation is preceded by a martensitic transformation, as is it the case of Q&P steels [45,46]. Figure 8 shows the evolution of the carbon content in austenite determined according to the procedure described above. As expected, the carbon content increases in all cases following sigmodal curves, i.e. with a rapid initial enrichment starting from the nominal carbon content (0.27 wt.%) then followed by a plateau. It must be emphasized that the plateau/stasis is not reached for B350 experiment. For the experiments having reached the plateau, the carbon content in austenite at the plateau decreases with temperature. This trend is consistent with the fraction of retained austenite at stasis assuming a first-order carbon balance.

(

) 3
The higher the fraction of retained austenite, the lower the enrichment is. This last equation supposes a complete partition of carbon between bainite and austenite. However, this too simple equation cannot hold. For B400 at stasis, the fraction of retained austenite is 17 wt.% meaning that the expected carbon content should be 1.76 wt.% instead of 0.89 wt.%. It thus means that a significant fraction of carbon remains in fact trapped in bainitic ferrite, which, in turn, explains the tetragonality of the ferritic lattice shown in previous Figure 7 b).

According to the Zener ordering theory [47], the carbon atoms in solid solution in a ferritic lattice tend to segregate collectively to certain octahedral sites of the BCC lattice and distort it. It is commonly admitted that a BCT structure is then obtained. The distortion of the lattice was shown to be proportional to the carbon content in solid solution. As in previous published works on bainitic and martensitic steels, the carbon content in bainite can be estimated on the basis of the tetragonality as followed [2,48-51]:

where is the concentration of carbon in wt.%.

In the literature, it is not clear if this estimation of the carbon content also encompasses carbon clusters or carbon segregated at defects, such as dislocations or bainitic lath boundaries [19,52]. Moreover, it must be mentioned that the recent works of Maugis et al. show that the distortion due to Zener's ordering could also lead to an orthorhombic lattice under a compressive stress state (tetragonal in tension) [53,54]. It could explain why an even better agreement can be obtained with an orthorhombic lattice to model diffraction peaks [28].

As a consequence, the estimated carbon content in bainite follows the trends illustrated in Figure 7 a) if Equation ( 4) applies. For the four isothermal experiments above M S , the carbon content first increases rapidly and decrease smoothly after about 100 s. The rapid increase must not be interpreted as the fraction of bainite is low and the uncertainty about the tetragonality measurement is too high. However, the trends after 100 s are more relevant. The lower the transformation temperature is, the higher the carbon content in bainite (from 0.09 wt.% at 450 °C up to 0.15 wt.% at 350 °C at the end of the experiments). These high values are consistent with the values reported in the literature in similar alloys and were used to support the diffusionless theory [28,30] of bainitic transformation. At the beginning of transformation, supersaturated bainite nucleates with a carbon content equal to the prior austenite. During the transformation process, the c/a ratio decreases by partitioning.

Carbon mass balance at the end of the isothermal holding

Table III summarizes the phase fractions and carbon contents at the end of isothermal experiments at temperatures above M S . The isothermal transformation at 300 °C (M+B300) has been discarded as it is difficult to deconvolute correctly the effect of prior martensite transformation on the carbon content in bainite. Moreover, for this particular experiment, the transformation is far from having reached a stasis. The first column contains the temperature of isothermal holding. The second and the fourth columns contain the bainite mass fraction (wt.%) and the austenite mass fraction (wt.%) determined by Rietveld refinement respectively. The third column shows the in wt.% corresponding to the carbon content in bainite obtained thanks to the tetragonality factor c/a at the end of the isothermal holding using equation 1. The last column contains the carbon deficit, ΔC, calculated as:

(5) where C 0 is the nominal carbon content in the steel grade. This function ΔC represents the carbon not found in austenite and in bainite by the independent determination of the carbon trapped in each phase. ΔC is thus thought to represent the carbon trapped in carbides.

The mathematical error in the Rietveld procedure for the determination of the phase fractions is ± 1 wt.%. On the contrary the relative error on the measurement of the austenite lattice parameter is low (2.10 -4 ). The errors made on the tetragonality are more difficult to evaluate as it could depend on the way in which the width of diffraction peaks is modeled. Moreover, the determination of C B using the tetragonality of the BCT lattice can be discussed [49]. Nevertheless, the high degree of confidence on the phase fraction and lattice parameter of austenite leads to the same conclusion that a significant part of the carbon content remains in fact trapped in bainite. The order of magnitude of the carbon content out of austenite ( ) would have given similar C B values between 0.2 wt.% and 0.1 wt.%. These values are indubitably higher than the values expected in a BCC phase after a transformation under paraequilibrium.

In the following, the values presented in Table III (carbon composition of austenite and bainite at the end of the experiments) will be discussed in light of diffusionless theory for carbide-free bainitic transformation. Finally, the very low residual fraction of carbon ΔC will be shown to be explained by the presence of carbides (precipitated carbon). In the Rietveld refinement procedure, only austenite and bainite are considered. Nevertheless, the fraction of precipitates remains very low (far below the experimental resolution) and doesn't affect the fraction measured above. The carbon contents in retained austenite at the end of studied isothermal holdings are shown in Figure 9. These values are compared with the T 0 and T 0 ' lines calculated with Thermocalc software and TCFE9 database. These lines represent the supposed thermodynamic limits for bainite nucleation assuming the equality of the Gibbs energy of BCC ferrite (representing bainite) and austenite. The T 0 ' line also takes into account an additional elastic strain energy of 400 J/mol in the ferrite in accordance with the diffusionless theory of Bhadeshia [START_REF] Bhadeshia | Bainite in Steels: Transformations, Microstructure and Properties[END_REF].

Carbon in austenite and validity of T 0 ' criterion

Experimental austenite carbon contents are close to the T 0 ' line only at the lower transformation temperatures (B400 and B350 experiments). For the latter, the transformation was shown to not have reached the stasis (transformation time is too short). The value presented here is thus low compared to the value really expected at stasis. On the contrary, at high temperatures (B450 and B475 experiments) the values are far from the T 0 ' line even if the kinetics show a clear stasis in the transformation (cf. Figure 3 a)). Such discrepancy between experiment and T 0 ' line at high temperatures has also been reported by some groups [2,8,55]. The T 0 ' criterion seems thus to be validated at low temperature but is clearly not verified at high temperatures.

Carbon supersaturation in bainite

The carbon contents in bainite obtained at the end of our isothermal experiments are represented by red squares (values found in Table III) in Figure 9.

The recent criterion assuming the equality of the Gibbs energy of a BCT phase (representing more convincingly bainite) and austenite proposed by Ranjan et al. [55] could explain why the carbon content in austenite could exceed the conventional T 0 ' line at the lower temperatures. On the contrary, at high temperatures, the new criterion cannot explain why the stasis is reached sooner than expected from the criterion.

For the sake of comparison, the values obtained on similar alloys after isothermal holdings by Pushkareva et al. [56], Garcia-Mateo et al. [29] and by Ranjan et al. [55] have been compared with our values. Pushkareva et al. [56] have measured the carbon content in bainitic laths by EELS (Electron Energy Loss Spectroscopy) whereas Garcia-Mateo et al. [29] and Ranjan et al. [55] have used APT (Atom Probe Tomography).

The lower the temperature, the higher the carbon content in bainite is. Those results are in agreement with results from the literature [29,32,[55][56][57]. Ranjan et al. [55] have explained recently this evolution by a correlation with the austenite carbon content which also increases.

As already discussed, these values are high compared to the carbon solubility in BCC phase and supports according to [55] the diffusionless theory of bainitic transformation. These results for all the isothermal experiments plead in favor of a bainite formed at low temperature following the lower bainite description of Bhadeshia [START_REF] Bhadeshia | Bainite in Steels: Transformations, Microstructure and Properties[END_REF]. Carbon remains trapped in bainite at low temperature since the diffusion of carbon is slow at low temperature. CFB obtained in isothermal conditions is thus highly supersaturated in carbon and its carbon content depends on the transformation temperature.

Carbides

The ΔC values identified in Table III represent the carbon missing in solid solution in bainite and in austenite. The values found are weak (max. 10 wt.% of the nominal carbon content) and decrease with increasing transformation temperatures. Above 400 °C, the values are negligible considering the precision of the measurement.

If solid solution is set aside, the other possible mechanisms able to trap carbon are numerous: segregations on dislocations, segregations on lath/blocks/packet boundaries, local enrichment in austenite or precipitation of carbides. In the literature, it is not well established whether the carbon segregates on defects also contributes to the obvious tetragonality observed on the bainitic phase [19,58].

The presence of carbides is the better explanation found to explain the ΔC values at low transformation temperatures (mainly at 350 °C). In fact, carbides can also be directly evidenced by SEM observations and by looking carefully at diffractograms as shown in Figure S2. of the supplementary materials. At 350°C, the transition carbides mass fraction is estimated less than 1 wt.% using a manual refinement (the uncertainty in phase fraction obtained by the Rietveld refinement is ± 1 wt.%), value that is consistent with the one obtained by the carbon mass balance. As a consequence, it is not possible to decide if the whole ΔC value can be explained by these carbides.

It must be mentioned that the steel contains around 0.1 wt.% of sulfur. As a consequence, it contains a large fraction of MnS which is well highlighted on the diffractograms in Figure S2 of the supplementary materials (cyan boxes). Even if the studied steel present a large fraction of MnS, the mean Mn composition in the matrix is not affected (no effect on Ms and T 0 lines). On the diffraction patterns , there is no overlapping peaks between MnS, transition carbides and cementite.

Transformation below M S

In this section, we discuss the outcomes of the "step treatments", which include as a last step an isothermal treatment at 300 °C, below the M S , during which a bainite transformation will take place. We compare the kinetics of the bainite transformation as a function of starting microstructure, as recalled in Table II. As shown in Figure 5, the bainite transformation kinetics at 300 °C are drastically different among the three experiments, despite a significant amount of austenite remaining to be transformed in all cases. These differences in kinetics can be interpreted qualitatively. The kinetics of M+B300 are fastest because the initial austenite fraction is the highest and because the austenite did not have time to get enriched in carbon during the martensitic transformation down to 300 °C. According to previous works [33,37], the new martensite/austenite interfaces also provide nucleation sites, which accelerate the bainite transformation.

For the experiment B+B300, the kinetics are the slowest (almost no detectable bainite transformation) because it has the lowest amount of austenite in the initial microstructure and the austenite got enriched by carbon (0.93 wt.%). The kinetics of B+M+B300 experiment are intermediate because there are more austenite remaining than to the latter experiment, it are less enriched in carbon (0.91 wt.%) and the martensite provides new nucleation sites. Accordingly, the austenite fraction at the end of the bainite transformation at 300 °C is the highest for the B+B300 treatment. Let us mention that the final carbon concentration is quasi similar among the two experiments (Table IV), showing that the final stasis is not simply related to this parameter. The previously formed microstructure modifies the carbon mass balance and therefore the final fraction of austenite. Hence, these experiments show that the overall bainite transformation is not simply linked with the temperature and the fraction of already-formed bainite (i.e. it is not additive): it depends on the already formed microstructure, which is itself dependent on the previous thermal history. This conclusion is in agreement with previous investigations by Hasan et al. [39]. The non-additivity is already highlighted above the M S temperature in Figure 6. Put together, these results are in agreement with previous studies which recently demonstrated that multi-step cooling sequences are more efficient to stabilize retained austenite at room temperature than conventional single isothermal treatments [39,59,60]. This is of both practical and industrial interest [1,4], even if its origin remains poorly understood. IV is a summary of austenite fractions and austenite carbon contents at the end of the last step at 300 °C for the B+M+B300 and B+B300 cooling sequence. As presented before, austenite mass fraction transformed depend of the schedule. A higher fraction of retained austenite is measured at the end of the B+B300 treatment. Even if, the austenite carbon content at the end of the final step is very close for both multi-step treatment. Hence, the retained austenite fraction and carbon composition depend on the transformation history. Both are the key to understand the mechanical performance of these microstructures and sustain their industrial interest [1,4].

Conclusions

Bainite transformations were investigated by in-situ High energy X-Ray diffraction above and below M S temperature. These experiments have permitted to determine with good accuracy the bainite kinetics transformation along isothermal and multi-step cooling sequences. The composition of phases are tracked using the determination of the austenite lattice parameter and the tetragonality of bainite lattice. At the end of isothermal holdings, a carbon enrichment is observed in austenite despite high carbon content trapped in bainite (in particular for low temperature conditions). The austenite carbon content at the end of the holding was compared to the displacive criterion T 0 ' line.

The experimental values are close to the T 0 ' line however this criterion is not respected for high temperature transformation. For transformations above M S , a precise carbon mass balance is proposed highlighting carbide formation at the lowest temperature. For transformations below M S , the bainite transformation is dependent on the history and previous transformations. This sensitivity has been explained in term of austenite stability and nucleation processes. The bainite transformation does not thus respect the additivity rule.

Figure 1 :

 1 Figure 1: Heat treatments schedules a) isothermal conditions b) multi-step conditions.

Figure 2 :

 2 Figure 2 : 2D Image a) and 1D spectrum b) at the end of the austenitic soaking; 2D Image c) and 1D spectrum at the beginning of bainite formation.

Figure 2 c

 2 Figure2 c) shows the two-dimensional image for the isothermal experiment at 400 °C after the formation of 20 wt.% bainite. The Debye Scherrer rings are still discontinuous and some spots are present and disturb the intensity. However, the position and the intensity of the peaks become insensitive to the apparition or the disappearance of single spots. At this stage shown in Figure2 d), it was considered that the determined values are meaningful and relevant. The R factor is slightly high (around 2.0) then as the transformation continues the R factor decreases.

Figure 3 :

 3 Figure 3 : a) Bainite and martensite mass fraction as a function of time during isothermal holdings ; b) Normalized Bainite mass fraction as a function of time in austenite along isothermal holdings (The normalization procedure is explained in the text). Compared to Figure 3 a), only B300 experiment has been corrected.

Figure 3 a

 3 Figure 3 a) shows the evolution of bainite and martensite mass fraction as a function of time during isothermal holding at different transformation temperatures between 300 °C and 475 °C measured by HEXRD. The mass fractions are the direct output of the Rietveld refinement procedure based on the absorption coefficients of atoms lattices. The reference time (t = 0) was set at the end of the austenitization for all experiments. Bainite mass fractions as a function of time are shown for the duration of isothermal holding and do not include potential changes during final cooling to room temperature.

Figure 4 :

 4 Figure 4 : SEM micrographs after nital etching 2 % of the studied steel after isothermal experiments at a) 350 °C, b) 400 °C, c) 450 °C, d) 475 °C. When possible, the microstructure components are indicated by white arrows.

Figure 5 :

 5 Figure 5 : Time evolutions of temperature and bainite/martensite transformation kinetics. Pie charts illustrate the composition of microstructure at different times. a)M+B300, b) B+M+B300 and c) B+B300 experiments respectively ; d) Normalized bainite kinetics in remaining austenite during the last transformation at 300 °C for M+B300, B+M+B300 and B+B300 experiments with respectively 44 wt.%, 32 wt.% and 19 wt.% of remaining austenite.

Figure 5 a

 5 Figure 5 a), b) and c) shows the evolution of the BCT phase fraction as a function of time for the three experiments designed to study the bainite transformation below M S , i.e. with varying starting microstructures. The temperature schedules are reported for each experiment. The expected microstructure composition at the transition between isothermal steps are represented schematically to ease the understanding of the transformation sequence. Figure 5 a) recalls the results previously discussed in Figure 3 a) for the sake of comparison.

Figure 5 b

 5 Figure 5 b) shows the evolution of bainite mass fraction as a function of time for the B+M+B300 experiment. As for isothermal experiments, the reference time (t = 0) is set at the end of the austenitizing. The bainite fraction increases with time all along the two-step cooling and the bainite mass fraction exhibits a sigmoidal curve. During the first step at 400 °C, the bainite mass fraction follows the same evolution as shown previously for an isothermal transformation at the same temperature. At the end of the first step, the mass bainite fraction is 25 wt.% and stasis is obviously not reached. During the transition between 400 °C and 300 °C, a partial martensitic transformation occurs (about 43 wt.%). The bainitic transformation restarts during the second step at 300 °C but with a lower rate than at 400 °C. The fraction transformed at 300 °C is 22 wt.%. The measured fractions of austenite, martensite and bainite along the schedule are summarized in TableII. The maximal bainite and martensite mass fraction at the end of the two-step holding is equal to 90 wt.%.

Figure 6 :

 6 Figure 6 : Kinetics of bainite/martensite transformation during B+B300 experiments respectively (green), isothermal transformations at 475 °C (red), 400 °C (yellow) and 300 °C (blue).

Figure 7 :

 7 Figure 7 : a) Evolution of c/a ratio of BCT phase in isothermal conditions ; b) Evolution of the austenite lattice parameter in isothermal conditions with the the minimal austenite lattice parameter at a given temperature.

Figure 7 a

 7 Figure 7 a) shows the evolution of c/a ratio as a function of time during isothermal holdings at temperatures between 350 °C and 475 °C. The other experiments have been excluded as it is not possible to isolate convincingly the behavior of bainite and martensite if present at the same time in the microstructure.

Figure 7 b

 7 Figure 7 b) represents the austenite lattice parameters measured by HEXRD as a function of time along isothermal holdings at temperatures between 350 °C and 475 °C. The initial values differ as the lattice parameter of stress-free austenite increases with temperature due to the thermal expansion. At the onset of isothermal holding, the austenite is assumed to represent the nominal composition.

Figure 8 :

 8 Figure 8 : Carbon content in retained austenite as a function of time during the isothermal holdings between 350 °C and 450 °C, determined by the procedure detailed in the text (nominal carbon content 0.27 wt.%).

Figure 9 :

 9 Figure 9 : Carbon content in retained austenite (triangles) and in bainite (squares) for isothermal conditions (T 0 and T 0 ' lines).

Table III :

 III Phase fractions and carbon contents measured by HEXRD at the end of holdings, the estimated ΔC by a simple carbon mass balance.

	Isothermal	Bainite mass	Bainite	Austenite	Austenite	ΔC
	temperature	fraction	carbon	mass fraction	carbon
	(°C)	(wt.%) F B	content	(wt.%) F A	content
			(wt.%) C B		(wt.%) C A
	350	90	0.15	10	0.92	0.03
	400	84	0.14	16	0.89	0.01
	450	60	0.11	40	0.52	0.00
	475	35	0.09	65	0.36	0.00

Table IV :

 IV Austenite mass fractions and carbon contents measured by HEXRD at the end of the last step of multi-step cooling sequences.

	Cooling sequence Temperature (°C)	Austenite mass fraction (%)	Austenite carbon content (wt.%)
	B+M+B300	300	10	0.91
	B + B300	300	19	0.93
	Table

Acknowledgements

This work was supported by Ascometal (CREAS) Hagondange. The synchrotron experiments were realized in 2018 under the project I-20180850 EC at DESY PETRA III in Hamburg. The authors would like to thank the team of P07 line, in particular Norbert Schell and Andreas Stark. Their expertise in very was much appreciated and widely contributed to the success of the study.

Financial relationship

This work was funded by Ascometal, Swiss steel group, by the Université de Lorraine, by the CNRS (Centre de la Recherche Scientifique) and the French ANRT (Agence National de la Recherche et de la Technologie) under the CIFRE convention (2018/1307). The HEXRD experiments were conducted at DESY (PETRA III-P07 beamline) in Hamburg.

Conflicts of Interest

The authors declare that they have no conflict of interest.