Pawe L Gawrychowski

Garance Gourdel

Tatiana Starikovskaya

Teresa Anna Steiner

Compressed Consecutive Pattern Matching

Originating from the work of Navarro and Thankanchan [TCS 2016], the problem of consecutive pattern matching is a variant of the fundamental pattern matching problem, where one is given a text and a pair of patterns p 1 , p 2 , and must compute consecutive occurrences of p 1 , p 2 in the text. Assuming that the text is given as a straight-line program of size g, we develop an algorithm that computes all consecutive occurrences of p 1 , p 2 in optimal O(g

time. As a corollary, we also derive an algorithm that reports all co-occurrences separated by a distance d ∈ [a, b] in O(g + |p 1 | + |p 2 | + output) time and an algorithm that reports the top-k closest co-occurrences in O(g + |p 1 | + |p 2 | + k) time.

Introduction

In the classical pattern matching problem, one is given a pattern and a text, and must find all substrings of the text equal to the pattern. However, considering potential applications, it is advantageous to enable queries beyond simply identifying exact matches of a given pattern in the preprocessed text.

Recently, Navarro and Thankanchan [START_REF] Navarro | Reporting consecutive substring occurrences under bounded gap constraints[END_REF] suggested a generalisation of the pattern matching problem, where in addition to the pattern and the text one is given two integers a, b, and must find all pairs of consecutive occurrences of the pattern in the text separated by a distance d ∈ [a, b]. They showed that there is a O(n log n)-space index for this problem with optimal query time O(m + output), where n is the length of the text and m of the pattern.

Following their work, indexing for consecutive occurrences is receiving growing attention in the literature [START_REF] Bille | String indexing for top-k close consecutive occurrences[END_REF][START_REF] Bille | Gapped indexing for consecutive occurrences[END_REF][START_REF] Gawrychowski | Compressed indexing for consecutive occurrences[END_REF].

Bille et al. [START_REF] Bille | Gapped indexing for consecutive occurrences[END_REF] considered an even more general case of the problem, where a query consists of two different patterns p 1 , p 2 of total length m and two integers a, b, and one must find all pairs of consecutive occurrences of p 1 , p 2 in the text separated by a distance d ∈ [a, b]. For reporting the occurrences, they showed a linear-space data structure with Õ(m + n 2/3 output) query time. On the other hand, by reduction from the set intersection problem, they showed a lower bound suggesting that achieving query time better than Õ(m + √ n) for indexes of size Õ(n) is impossible, even if a = 0 is fixed.

Gawrychowski et al. [START_REF] Gawrychowski | Compressed indexing for consecutive occurrences[END_REF] showed that one can circumvent this lower bound in the case a = 0 assuming that the text is very compressible: assuming that the text is represented by a straight-line program (SLP) of size g, they showed a Õ(g 5 )-space data structure with Õ(m + output) query time, where m is the total length of the patterns.

Unfortunately, the above upper bounds, despite their theoretical interest, are still far from providing an efficient solution. Motivated by this, we study the dual variant of the problem, where one must process the text and the patterns simultaneously. Note that if the text is uncompressed and has length n, the problem can be solved by classical online pattern matching in O(n + m + output) time by keeping the most recent occurrences of p 1 and p 2 . In this work, we show that for very compressible texts which can be represented by an SLP of size g ≪ n, we get a better runtime O(g + m + output) by extending the ideas of [START_REF] Ganardi | Pattern matching on grammar-compressed strings in linear time[END_REF]:

Theorem 1.
Given a text of length n on a constant-size alphabet represented by an SLP G of size g and patterns p 1 , p 2 of total length m, all consecutive occurrences of p 1 , p 2 in the text can be found in O(g + m + output) time assuming the word-RAM model with a machine word of size w = Ω(log n).

Using similar techniques, we derive an algorithm to output all consecutive occurrences with a bounded distance between them: Corollary 2. Given a text of length n on a constant-size alphabet represented by an SLP G of size g and patterns p 1 , p 2 of total length m, all consecutive occurrences of p 1 , p 2 in the text separated by a distance d ∈ [a, b] can be found in O(g + m + output) time assuming the word-RAM model with a machine word of size w = Ω(log n).

Finally, our techniques allow to derive an efficient solution for the variant of the problem suggested by Bille et al. [START_REF] Bille | String indexing for top-k close consecutive occurrences[END_REF], where one must report the top-k consecutive occurrences of p with smallest distances between them.

Corollary 3. Given an integer k, a text of length n on a constant-size alphabet represented by an SLP G of size g and patterns p 1 , p 2 of total length m, the k closest consecutive occurrences of p 1 , p 2 in the text can be found in O(g+m+k) time assuming the word-RAM model with a machine word of size w = Ω(log n).

Technical Overview. Our algorithm builds on and extends the work by Ganardi and Gawrychowski [START_REF] Ganardi | Pattern matching on grammar-compressed strings in linear time[END_REF], who gave the first O(g + m)-time algorithm for deciding whether a pattern p occurs in a string s represented by a context-free grammar G of size g. Their algorithm relies on the fact that for any occurrence of pattern p of length at least 2 in s, there exists a production A → BC in G, such that a suffix of the extension of B is a prefix of p and and a prefix of the extension of C is a suffix of p. They show how to efficiently compute information about prefixes (resp. suffixes) of non-terminals which contain the longest possible suffix (resp. prefix) of p. This information is called boundary information and is constructed for G bottom-up, starting at the terminals. To do so efficiently, the authors give a new data structure for efficiently answering batches of substring concatenation queries. Our algorithm extends this approach to reporting consecutive occurrences of patterns p 1 and p 2 .

Similarly to above, for any consecutive occurrence of p 1 and p 2 , there exists some production A → BC, such that the first position of the occurrence of p 1 is in the extension of B, and the last position of the occurrence of p 2 is in the extension of C. However, there are different cases to consider, depending on whether the occurrences of p 1 resp. p 2 are fully in the extension of B resp. C, or whether one or both of them start in the extension of B and end in the extension of C (called a crossing occurrence). To handle the different cases, we need to compute additional information for every non-terminal, including the left-and rightmost occurrence of both patterns in the extension of any non-terminal, all crossing occurrences of both patterns, and a two-level version of the boundary information. The two-level boundary information is necessary for the case where p 2 is a crossing occurrence, and we need to find its "predecessor occurrence" of p 1 , i.e. the rightmost occurrence of p 1 starting before p 2 . We show how to compute this information efficiently for all non-terminals via a bottom-up approach. For computing all crossing occurrences, we extend the work by Ganardi and Gawrychowski [START_REF] Ganardi | Pattern matching on grammar-compressed strings in linear time[END_REF], who only showed how to answer whether or not a crossing occurrence of a pattern exists in any non-terminal. We can find all crossing occurrences in the same time complexity, even if there are many in the same non-terminal, by using periodicity arguments. Then we show how to use this information to report all co-occurrences, which requires a careful case analysis and further periodicity arguments.

Preliminaries

A string s of length |s| = n is a sequence s[0]s [START_REF] Navarro | Reporting consecutive substring occurrences under bounded gap constraints[END_REF] . . . s[n -1] of characters from a finite alphabet Σ. In this work, we assume that the size of the alphabet is constant. A substring of a string s is a pair (i, j) where 0 ≤ i ≤ j < |s| and is identified with the string s[i . . . j] = s[i] . . . s [j]. We also use the notation s[i . . . j) and s(i . . . j] which stand for the substring s[i . . . j -1] and s[i -1 . . . j] respectively. We say that a substring s[i . . . j] is fully contained in another substring s

[i ′ . . . j ′ ] if i ′ ≤ i ≤ j ≤ j ′ .
We call a substring s[0 . . . i] a prefix of s and use a simplified notation s[. . . i], and a substring s[i . . . n -1] a suffix of s denoted by s[i . . . ]. We say that x occurs in s at position i if x = s[i . . . i + |x|), alternatively we say i is an occurrence of x in s. Additionally, an occurrence i is fully included in a substring

f of s if s[i . . . i + |x|) is fully included in f .
An occurrence k 1 of p 1 together with an occurrence k 2 of p 2 form a consecutive occurrence (co-occurrence) (k 1 , k 2 ) of the strings p 1 , p 2 in a string s if there are no occurrences of p 1 in (k 1 , k 2 ] and no occurrences of p 2 in [k 1 , k 2 ). The distance k 2 -k 1 is sometimes referred to as a gap.

An integer π is a period of a string s of length n if s[i] = s[i + π] for all i = 0, . . . , n -1 -π. We say that s is periodic if its smallest period, referred to as the period of s, is at most |s|/2. We also exploit the well-known corollary of the Fine and Wilf's periodicity lemma [START_REF] Fine | Uniqueness theorems for periodic functions[END_REF]: Corollary 4. Let x, y be strings such that |x| ≤ 2|y|. If there are at least three occurrences of y in x, then all occurrences of y in x form an arithmetic progression with difference equal to the period of y. Proposition 5. Let p be an m-length string over a constant-size alphabet. Then, one can preprocess p in O(m) time to maintain the following queries in constant time: Given a substring p[i...j], find its leftmost and rightmost occurrences in p, as well as the total number of occurrences. Given two substrings p[i...j] and p[k...l], compute their longest common prefix and their longest common suffix.

Proof. We first construct the suffix tree of p in O(m) time [START_REF] Farach-Colton | On the sortingcomplexity of suffix tree construction[END_REF]. Belazzougui et al. [START_REF] Belazzougui | Weighted ancestors in suffix trees revisited[END_REF] showed that the suffix tree can be preprocessed in linear time so that, given a substring p[i...j], one can find the node u of the suffix tree labeled by p[i...j] in constant time. The leaves of the subtree of u correspond to the occurrences of p[i...j] in p. For each node, we can precompute in linear time in the size of its subtree, the leftmost and rightmost occurrences of its label. This is done by simply traversing the tree from the bottom to the top and propagating the information. We also preprocess the suffix trees in linear time so that it is possible to find the lowest common ancestor between two nodes in constant time [START_REF] Bender | The LCA problem revisited[END_REF]. Given two nodes u and v labelled by substrings p[i...j] and p[k...l], the length of the label of their common ancestor is the longest common prefix of p[i...j] and p[k...l]. Analogously, by building the suffix tree for the reverse of p, we can compute the longest common suffix of two substrings in constant time.

Corollary 6 (of Corollary 4 and Proposition 5). One can preprocess an m-length string p over a constant-size alphabet in O(m) time to maintain the following queries in constant time: Given a substring (i, j), such that j -i ≥ m/2, one can output the arithmetic progression of the occurrences of p[i...j] in p in constant time.

Grammars

Definition 1 (Straight-line program [START_REF] Kieffer | Grammar-based codes: A new class of universal lossless source codes[END_REF]). A straight-line program (SLP) is a contextfree grammar (CFG) consisting of a set of non-terminals X 1 , . . . , X q , a set of terminals, an initial symbol X q , and a set of productions, satisfying the following properties:

• A production consists of a left-hand side and a right-hand side, where the left-hand side is a non-terminal X i and the right-hand side is a sequence X j X k , where j, k < i, or a terminal;

• Every non-terminal is on the left-hand side of exactly one production.

The expansion S of a sequence of terminals and non-terminals S is the string that is obtained by iteratively replacing non-terminals by the right-hand sides in the respective productions, until only terminals remain. We say that G represents the expansion G of its initial symbol.

Definition 2 (Parse tree). The parse tree of a SLP is defined as follows:

• The root is labeled by the initial symbol;

• Each internal node is labeled by a non-terminal;

s x s y s u s v s p[m -|prefix p (s)| . . . ] p[. . . |suffix p (s)| -1]
Figure 1: A p-boundary information for a string s that is not a substring of p.

• If S is the expansion of the initial symbol, then the i th leaf of the parse tree is labeled by a terminal S[i];

• A node labeled with a non-terminal A that is associated with a production A → BC has two children labeled by B and C, respectively.

The size of a grammar is the total size of all right-hand sides of all productions. The height of a grammar is the height of the parse tree.

Boundary information

Fix a pattern p of length m. In this section, we remind the notion of the p-boundary information for a string s, introduced by Ganardi and Gawrychowski [START_REF] Ganardi | Pattern matching on grammar-compressed strings in linear time[END_REF]. It constitutes information about the longest prefix resp. suffix of s containing a suffix resp. prefix of a pattern p. This information, if computed for the extension of a nonterminal A in G, can then be used to decide whether there is a crossing occurrence of p in A. The information is defined in such a way that given boundary information for strings s and t, the boundary information for st can be constructed in constant time, given additional data structures (see Algorithm 1). This allows efficiently computing boundary information for all non-terminals in G.

For a string s, let prefix p (s) be the longest prefix of s which is a suffix of p and suffix p (s) the longest suffix of s which is a prefix of p. If s occurs in p at position i, meaning s = p[i...i+|p|-1], then we define p-substring information for s as (i, i+|p|-1), and otherwise p-substring information for s is undefined (if p occurs multiple times in s, any occurrence defines a valid p-substring information for s). For a string s, a p-boundary information is defined as follows:

1. If s occurs in p, then it is simply p-substring information for s;

2. Otherwise, it is two substrings of p, x s and y s such that prefix p (s) is a prefix of x s y s which in turn is a prefix of s (p-prefix information), and two substrings of p, u s , v s such that suffix p (s) is a suffix of u s v s which in turn is a suffix of s (p-suffix information). (See Fig. 1.) For a string s, there are multiple ways p-boundary information can be constructed. We apply a recursive approach: for two strings s, t, assume to be given p-boundary information for s, t. Algorithm 1 (first described in [START_REF] Ganardi | Pattern matching on grammar-compressed strings in linear time[END_REF]) correctly constructs a pboundary information for c = st. Algorithm 1 A boundary information of c = st 1. If s is a substring of p and t is not, then the p-suffix information of c is the p-suffix information of t and we define the p-prefix information for c as follows:

(a) If sx t is a substring of p, then x c = sx t and y c = y t ;

(b) Otherwise, x c = s and y c = x t .

2. If t is a substring of p and s is not, then the p-prefix information of c is the p-prefix information of s and we define the suffix information for c as follows:

(a) If v s t is a substring of p then v c = v s t and u c = u s ;

(b) Otherwise, u c = v s and v c = t;

3. If s and t are both substrings of p, and c is a substring p[i . . . j] of p, then the p-boundary information is p-substring information for c, and we define it equal to (i, j). Otherwise, we put x c = u c = s and y c = v c = t.

4. If neither s nor t is a substring of p, then one can take p-prefix information for c equal to p-prefix information for s and p-suffix information to p-suffix information for t.

Definition 3 (Crossing occurrences). Let s, t be two strings. We say that a position i is a crossing occurrence of p in a string c = st if i is an occurrence of p in c and i ≤ |s| ≤ i+|p|-1. By extension, an occurrence i of p in the expansion A is a crossing occurrence of p for a non-terminal A of a grammar G, or simply a crossing occurrence for A, if A is associated with a production A → BC and i ≤ |B| ≤ i + |p| -1.

Ganardi and Gawrychowski [START_REF] Ganardi | Pattern matching on grammar-compressed strings in linear time[END_REF] showed that given a p-boundary information of two strings s, t one can efficiently decide whether there is a crossing occurrence of p in c = st. By extending their solution, we can report all such occurrences. Note that by Corollary 4, all crossing occurrences form an arithmetic progression.

Lemma 7. Assume to be given a p-boundary information of strings s k , t k for k ∈ [1, q]. One can compute all crossing occurrences of p in all strings s k t k , for k ∈ [1, q], in O(q + m) time. For each k, the output is represented as an arithmetic progression.

The proof of this lemma and our algorithm exploit the following fact: Fact 8 (see [5, Lemma 2.2, Theorem 1.3]). Let w be the size of the machine word. A string p of length m can be preprocessed in O(m) time so that:

• q substring concatenation queries on p can be answered in O(q + m/w) time. A substring concatenation query on a string p asks: Given two substrings u = p[i . . . j] and v = p[k . . . ℓ] of p, check whether uv occurs in p and, if so, return an occurrence;

• Given q substrings u 1 , . . . , u q of p one can compute prefix p (u i ) and suffix p (u i ) in O(q + m/w) time.

Compressed consecutive pattern matching

We are now ready to prove Theorem 1. Recall that the text is an n-length string over a constant size alphabet represented by an SLP G of size g ≪ n, and the patterns p 1 , p 2 have total length m. By scanning the patterns in O(m) time we can decide whether they contain characters outside of the alphabet of the text. If this is the case, there are no co-occurrences of p 1 , p 2 in the text. Below we assume that p 1 , p 2 are strings over the constant-size alphabet of the text.

The main strategy is to first compute all primary co-occurrences of p 1 and p 2 :

Definition 4 (Primary co-occurrence). Let A be a non-terminal of G associated with a production A → BC. We say that a co-occurrence (i, j) of

p 1 , p 2 in A is primary if i ≤ |B| ≤ j + |p 2 | -1.
We handle primary co-occurrences depending on whether the occurrence of p 1 is fully contained in B or a crossing occurrence, and whether the occurrence of p 2 is fully contained in C or a crossing occurrence. To do so, we preprocess the non-terminals of G to compute the boundary and secondary boundary information for p 1 and p 2 (see Section 4.1), all crossing occurrences, the leftmost and rightmost occurrences of p 1 and p 2 in any non-terminal. The secondary boundary information will be used in the case where there is a crossing occurrence of p 2 and we need to find the rightmost occurrence of p 1 starting before that occurrence.

Computing boundary information and crossing occurrences

We first use a linear-time pattern matching algorithm (e.g. the Knuth-Morris-Pratt algorithm [START_REF] Knuth | Fast pattern matching in strings[END_REF]) to check whether p 2 is a substring of p 1 . If it is, then every cooccurrence of p 1 , p 2 in the text is a pair (i, i + ℓ), where i is an occurrence of p 1 in the text and ℓ is the leftmost occurrence of p 2 in p 1 . (By definition, there is no occurrence of p 2 in [i, i + ℓ). Note also that there cannot exist an occurrence i < i ′ ≤ i + ℓ of p 1 , because then i + ℓ -i ′ < ℓ would be an occurrence of p 2 in p 1 , a contradiction with the choice of ℓ.) In other words, to find all co-occurrences of p 1 , p 2 in the text it suffices to find all occurrences of p 1 in the text, which can be done in O(g + m + output) time [START_REF] Ganardi | Pattern matching on grammar-compressed strings in linear time[END_REF].

Below we assume that p 2 is not a substring of p 1 . Define an array P such that for every j ∈ [0, |p 2 | -1], P [j] is the rightmost occurrence of p 1 in p 2 to the left of j if their is one, else -1. We call P the predecessor array. P can be computed in O(m) time by a linear-time pattern matching algorithm.

By [START_REF] Ganardi | Balancing straight-line programs[END_REF], we can restructure the SLP G representing the text in O(g) time to ensure that its height is O(log n), while its size increases by only a constant factor.

For every symbol A of G (a non-terminal or a terminal) associated with a production A → BC, we compute:

1. a p 1 -boundary information and a p 2 -boundary information for A; 2. All crossing occurrences of p 1 and p 2 for A, as well as the rightmost and the leftmost occurrences of p 1 and p 2 in A;

3. Furthermore, if p 2 -suffix information for A is (u A , v A ), then we compute:

(a) a p 1 -boundary information of u A and v A , which we refer to as secondary boundary information;

(b) All crossing occurrences of p 1 for u A , v A , as well as the rightmost occurrence of p 1 in A starting before u A .

Proposition 9. There is a O(g)-time algorithm that computes boundary and secondary boundary information for all symbols of G.

Proof. We first compute boundary information. For a terminal, it suffices to check if it occurs in p. If it does and i is one of the occurrences, we define the p-substring information to be (i, i), else we define p-prefix information and the p-suffix information to be the empty strings. Let the k-th level L k of G be the set of its symbols whose parse tree has height k. We now apply Lemma 7 to compute all crossing occurrences for the non-terminals of G in O(g + m) time. By a second application of Lemma 7, we compute, for every non-terminal A of G, all crossing occurrences for pairs u A , v A , which constitute p 2 -suffix information for A, using the same amount of time.

Proposition 10. Given the boundary information and the crossing occurrences for all symbols of G, one can compute the rightmost and leftmost occurrences of p 1 and p 2 in the expansion of every symbol of G in O(g) time.

Proof. We explain how to compute the rightmost occurrences of p 1 , the rest can be computed analogously. The algorithm processes the symbols of G bottom-up. Consider a symbol A of G. If it is a terminal, then we can find the rightmost occurrence of p 1 in its expansion (if it exists) in O(1) time. Otherwise, assume that A is associated with a production A → BC. If C contains an occurrence of p 1 , then the rightmost occurrence of p 1 in A is the rightmost occurrence of p 1 in C (and we have already computed it). Otherwise, if there are crossing occurrences of p 1 for B, C, it is the rightmost such occurrence. And finally, if C does not contain an occurrence of p 1 and there are no crossing occurrences, then we copy the rightmost occurrence of p 1 in B.

We will need the following auxiliary claim: Observation 11. Given an arithmetic progression by its starting position, difference, and length, we can find the predecessor of a number z in that progression in constant time.

Proposition 12. There is a O(g + m)-time algorithm that computes, for each symbol A of G, the rightmost occurrence of p 1 in A before u A , where

(u A , v A ) is p 2 -suffix information for A.
Proof. The algorithm processes the symbols of G bottom-up. Consider a symbol A of G. If it is a terminal, then (u A , v A ) is either not defined if A occurs in p 2 , or u A = v A are both equal to the empty string. In the second case, the rightmost occurrence of p 1 in A before u A is 0, if A = p 1 , otherwise no occurrence of p 1 exists in A. Now, if there is a production A → BC, let (u B , v B ) (resp., (u C , v C )) be the p 2 -suffix information for B (resp., C) that we computed using Algorithm 1. Note that they might not be defined, if B or C is a substring of p 2 . We review the cases of Algorithm 1:

In Cases 1 and 4, the p 2 -suffix information of A is the p 2 -suffix information of C. Therefore, the rightmost occurrence of p 1 before u A in A is either the last occurrence before u C = u A in C, or the rightmost crossing occurrence of p 1 for A, or the rightmost occurrence of p 1 in B, and we can compute it in constant time.

In Case 3, either (u A , v A ) is undefined or u A = B, and therefore the rightmost occurrence of p 1 is undefined.

In Case 2a, u A = u B , and therefore the rightmost occurrence of p 1 in A before u A is either the rightmost occurrence of p 1 in B before u B or the rightmost crossing occurrence of p 1 for A that precedes u B , which can be found in constant time by Observation 11. In Case 2b, we have u A = v B . Thus, the rightmost occurrence before u A equals to one of the following: We can find the rightmost occurrence fully contained in u B = p 2 [i . . . j] by querying the predecessor array P for j -|p 1 | + 1, and the three other candidate occurrences have been already computed.

Reporting co-occurrences

We now show how to quickly report the co-occurrences.

Proposition 13. Consider a symbol A of G associated with a production A → BC. Let j < |B| ≤ j + p 2 -1 be an occurrence of p 2 in A. One can find the rightmost occurrence i ≤ j of p 1 such that i

+ |p 1 | -1 < |B| in O(1) time.
Proof. Let (u B , v B ) be p 2 -suffix information for B. By definition, j belongs to u B v B . If j belongs to v B , then i is the rightmost existing one of the following candidates: If j is in u B , then i is the rightmost existing one of the following candidates:

1. The rightmost occurrence i ′ ≤ j of p 1 such that A[i ′ ...i ′ + |p 1 |) is fully contained in v B (
• The rightmost occurrence i ′ ≤ j of p 1 such that A[i ′ ...i ′ + |p 1 |
) is fully contained in u B (which we can find in O(1) time using the predecessor array P );

• The rightmost crossing occurrence i ′ ≤ j of p 1 for u B , v B (which we can find in O(1) time by Observation 11);

• The rightmost occurrence of p 1 in B starting before u B (which we have precomputed).

It follows that i can be computed in constant time.

For a node u of the parse tree of G, denote by off(u) the number of leaves to the left of the subtree rooted at u. Observation 14. Assume that p 2 is not a substring of p 1 , and let (i, j) be a cooccurrence of p 1 , p 2 in the text. In the parse tree of G, there exists a unique node u such its label A is associated with a production A → BC, and (i -off(u), j -off(u)) is a primary co-occurrence of p 1 , p 2 in A.

Lemma 15. Assume that p 2 is not a substring of p 1 and that we are given the information computed in Section 4.1. There is a O(g + m)-time algorithm that reports all primary co-occurrences of p 1 and p 2 in the expansions of the non-terminals of G. If there is more than one primary co-occurrence in the expansion of a non-terminal, they are output as O(1) arithmetic progressions.

Proof. Let A be a non-terminal associated with a production A → BC. We consider three types of co-occurrences of p 1 , p 2 in A:

1. The occurrence of p 1 is fully contained in B and the occurrence of p 2 in C; 2. The occurrence of p 1 is a crossing occurrence for B, C and the occurrence of p 2 is not; 3. The occurrence of p 2 is a crossing occurrence for B, C.

Let (i, j) be a co-occurrence of Type 1. It must have the property that i is the rightmost occurrence of p 1 fully contained in A[. . . |B|-1], j is the leftmost occurrence of p 2 in A[|B| . . . ], and there are no occurrences of p 1 , p 2 in between. As we store all crossing occurrences for B, C, the rightmost occurrences of p 1 , p 2 in B and the leftmost occurrences of p 1 , p 2 in C, we can check whether (i, j) exists and compute it in O(1) time by Observation 11.

A co-occurrence (i, j) of of Type 2 must satisfy the following properties: For Type 3, consider two cases. First, consider the case when j is the leftmost crossing occurrence. Let i ′ ≤ j be the rightmost occurrence of p 1 such that i ′ + |p 1 | -1 < |B|, which we can find in O(1) time by Proposition 13, and i ′′ be the rightmost crossing occurrence of p 1 that is at most j, which we can find in O(1) time as well using Observation 11. By definition, the only candidate for a co-occurrence containing j is (i = max{i ′ , i ′′ }, j). By construction of i ′ and i ′′ , there can't be any occurrence of p 1 in (i, j] and it suffices to check whether there are occurrences of p 2 in [i, j). If there is such an occurrence, it must be the rightmost occurrence of p 2 in B, and we can check if it is the case in constant time.

Consider now the case when j is not the leftmost crossing occurrence of p 2 for A. By Corollary 4, all crossing occurrences of p 2 form an arithmetic progression. Let j 0 be the leftmost occurrence, d be the difference and ℓ the length of this progression. By Corollary 4, A[j 0 . .

. j 0 + ℓ • d + |p 2 | -1] is periodic with period d. Let 1 ≤ k ≤ ℓ
be the largest such that the occurrence j * = j 0 + k • d forms a co-occurrence with an occurrence i of p 1 . By definition of a co-occurrence, j 0 ≤ j * -d < i ≤ j * . Furthermore, since p 2 is not a substring of p 1 , we have i + |p 1 | -1 < j * + |p 2 | -1. Hence, by periodicity, (i -k ′ • d, j * -k ′ • d) is a co-occurrence for all 1 -k ≤ k ′ ≤ ℓ -k. (In particular, by maximality of j * , we have j * = j 0 + ℓ • d.) Hence, it suffices to find the co-occurrence for k ′ = 1-k, i.e. to find the occurrence of p 1 preceding j 0 +d. This can be done in constant time by Proposition 13. This case is illustrated in Figure 2.

By Fact 8, the algorithm takes O(g + m) time.

Finally, we report all co-occurrences of p 1 , p 2 in the text given the primary cooccurrences for the non-terminals of G. Using the approach of [13, Section 6.4]), it can be done in O(g + output) time. Observation 14 guarantees that we report all co-occurrences.

Gapped and top-k consecutive pattern matching

We now explain how to modify the algorithm to report only the co-occurrences with a bounded gap (Corollary 2) and only the top-k co-occurrences in the text (Corollary 3).

Bounded-gap co-occurrences. We run the algorithm of Section 4 in O(g + m) time to generate a description of all primary co-occurrences (the elements of this description are single co-occurrences and arithmetic progressions of co-occurrences with a fixed gap) and select the elements of this description with a gap in [a, b]. For each selected element, we apply the approach of [START_REF] Roy Christiansen | Optimal-time dictionary-compressed indexes[END_REF]Section 6.4]) to generate all co-occurrences with a gap in the interval [a, b] in time O(g + m + output).

Top-k co-occurrences. To report the top-k co-occurrences, we first generate a description of all primary co-occurrences (the elements of this description are single co-occurrences and arithmetic progressions of co-occurrences with a fixed gap) in O(g + m) time as in Section 4. Second, we arrange the elements of the description in a heap in O(g) time sorted by the gaps. Then, conceptually, we attach to each node of the heap a path containing the secondary co-occurrences that originate from the element stored in the node. We finally select the k co-occurrences with smallest gaps in O(k) time using Frederickson's heap selection algorithm [START_REF] Frederickson | An optimal algorithm for selection in a min-heap[END_REF]. The algorithm and its analysis requires the min-heap property, the fact that all nodes have constant degree, and to have quick access to the children of an already visited node. The first two properties are guaranteed by construction, and the method of [13, Section 6.4]) guarantees that the children of an already visited node can be accessed in constant amortised time.

  We apply Algorithm 1 to compute boundary information for the symbols of each level in turn, starting from level 0. Processing L k takes |L k | substring concatenation queries and O(|L k |) extra time. Since the height of G is O(log n), by Fact 8 we obtain O( k (|L k | + m/w)) = O(g + m) total time. The secondary boundary information is computed by applying Algorithm 1 on the substrings constituting the boundary information. In more detail, note that for any non-terminal A of G associated with a production A → BC Algorithm 1 computes the boundary information of A by either copying the boundary information of B or C or by concatenating the substrings constituting the boundary information of B and C a constant number of times. It follows that in total there are O(|L k |) copying and concatenation operations at level k. For each concatenation operation, we apply Algorithm 1 to update the boundary information. Processing L k hence takes O(|L k |) substring concatenation queries and O(|L k |) extra time. As above, this leads to O( k (|L k | + m/w)) = O(g + m) total time.

1 .

 1 The rightmost crossing occurrence of p 1 for u B and v B ; 2. The rightmost occurrence of p 1 fully contained in u B ; 3. The rightmost occurrence of p 1 preceding u B which is fully in B; 4. The rightmost crossing occurrence of p 1 for A preceding u B .

1 Figure 2 :

 12 Figure 2: Co-occurrences with crossing occurrences of p 2 forming an arithmetic progression.

  which we can find in O(1) time using the predecessor array P ); 2. The rightmost crossing occurrence i ′ ≤ j of p 1 for u B , v B (which we can find in O[START_REF] Navarro | Reporting consecutive substring occurrences under bounded gap constraints[END_REF] time by Observation 11);3. The rightmost occurrence of p 1 that is fully in u B (which we can find in O(1) time using the predecessor array P );4. The rightmost occurrence of p 1 in B starting before u B (which we have precomputed).

  1. j cannot be in A[. . . |B| -1], since it is not a crossing occurrence and p 2 is not a substring of p 1 ; 2. Since i and j are consecutive, and i is a crossing occurrence, i must be the rightmost crossing occurrence and j must the leftmost occurrence of p 2 in A[|B| . . . ] = C. We retrieve i, the rightmost crossing occurrence of p 1 , and j, the leftmost occurrence of p 2 in A[|B| . . . ]. It remains to check that there is no occurrence of p 1 in (i, j] and no occurrence of p 2 in [i, j). If there is an occurrence of p 1 in (i, j], it can only be the leftmost occurrence of p 1 in A[|B| . . . ] = C. If there is an occurrence of p 2 in [i, j), it can only be a crossing occurrence for A. Both conditions can be tested in constant time by Observation 11.

A Proof of Lemma 7

Consider two strings s, t. Let u, v be p-suffix information of s and x, y p-prefix information of t. To find all crossing occurrences of p in a string st, it suffices to look at occurrences in uvxy as uv contains suffix p (s) and xy contains prefix p (t).

We can also assume that u is a prefix of p and y a suffix of p because there is an occurrence of p in uvxy if and only if there is an occurrence of p in suffix p (u)vxprefix p (y).

Here and below, whenever we replace a string u with suffix p (u) and or a string y with prefix p (y), we assume to compute them using Fact 8.

By Corollary 4, the crossing occurrences of p form a single arithmetic progression. We will consider several cases and for each case will report an arithmetic progression of occurrences, but in the end they can be merged into a single one. We repeatedly make use of the following procedure: Proposition 16. Let ℓ be a prefix of p, r a suffix of p, and c a concatenation of at most three substrings of p. After O(m)-time shared preprocessing of p, one can report all occurrences of p in ℓc starting at positions i ≤ |ℓ|/2 and all occurrences in cr ending at positions j ≥ |c| + |r|/2 in constant time. The occurrences are output as an arithmetic progression.

Proof. We show how to proceed for the occurrences in s = ℓc, the proof for the occurrences in cr is symmetric. Assume that there is an occurrence of p at position i ≤ |ℓ|/2. As ℓ is a prefix of p, i = α • d, where 0 ≤ α ≤ |ℓ|/2d is an integer and d is the period of ℓ.

After a classical shared O(m)-time preprocessing the period of any prefix of p can be extracted in O(1) time [START_REF] Knuth | Fast pattern matching in strings[END_REF]. If d > |ℓ|/2, then the only candidate is i = 0 and we can test whether p occurs at this position using a constant number of longest common extension queries. We now assume d ≤ |ℓ|/2. Let α max ≤ |ℓ|/(2d) be the rightmost position such that α max For an occurrence i of p in u ′ vxy ′ , consider three (overlapping) cases: 1. The occurrence is fully contained in u ′ vx; 2. The occurrence fully contains vx; 3. The occurrence is fully contained in vxy ′ . Consider Case 1. By applying Proposition 16 on c = u ′ v and r = x, we can assume that |x| ≤ m/2. We then have three subcases: (a) either an occurrence of p is fully contained in u ′ v, or (b) it contains v, or (c) it is fully contained in vx. In Case 1(a), as |u ′ | ≤ m/4 and |v| ≤ m, any occurrence of p in u ′ v ends in the second half of v and hence we can report all occurrences by applying Proposition 16 once to u ′ and prefix p (v). Case 1(c) is analogous. We repeat the argument for Case 3. Thus, it remains to report all occurrences of p in a string h = ef g fully containing f , where |e|, |g| ≤ m/4, e is a prefix of p, g is a suffix of p, and f is a concatenation of at most two substrings of p.

If the length of f is smaller than m/2, then |h| < m and there are no occurrences of p in h. Assume now that |f | ≥ m/2.

Consider first the case when f is a substring of p given by its starting and ending positions, i.e. let f = p[i . . . j]. By Corollary 6, after O(m)-time shared preprocessing we can find the arithmetic progression of the occurrences of f in p in constant time. If there are only two occurrences, we test if they extend in e and g to an occurrence of p using two longest common prefix and suffix queries.

Assume now that there are at least three occurrences. Let p mid be the minimal substring of p which contains all occurrences of f . By Corollary 4, the period of p mid equals the period of f , d. Let p = p left p mid p right . Next, using two longest prefix and suffix queries, we compute the maximal substring f ′ of h that starts and ends with an occurrence of f . Namely, by Corollary 4, it suffices to check how far the periodicity in f extends beyond f : f ′ must be periodic with period d, must fully contain f , and must start at a position |e|-α•d and end at a position |e|+|f |+α•β for some integers α, β. Let h = e ′ f ′ g ′ . By Corollary 4, the occurrences of f in h start at positions

Now consider the case when f is given as the concatenation of two substrings of p, i.e. f = yu. We would like to reduce this case to the first one. For that, we need to find an occurrence of f in p. As |f | ≥ m/2, at least one of y, u has length greater or equal to m/4. Assume w.l.o.g. |y| ≥ m/4, the other case is symmetric. By Corollary 6, after O(m)-time shared preprocessing we can find a constant number of arithmetic progressions representing the set of all occurrences of y in p in constant time, as well as the period d of y equal to the difference of the progressions. In more detail, if |y| ≥ m/2, we apply Corollary 6 on p and y directly. If m/2 ≥ |y| ≥ 3m/8, we represent p as two 3m/4-length blocks overlapping by m/2 characters and apply Corollary 6 to each block and y (then |y| is at least half the length of a block, and every occurrence is definitely contained in one of the blocks). Finally, if 3m/8 ≥ |y| ≥ m/4, we consider m/2-length blocks overlapping by 3m/8 characters.

By one longest common extension query, we find the longest prefix of u periodic with period d, let its length be ℓ. Fix an arithmetic progression of occurrences of y and let q last be the last position in it. Let q be the leftmost position in this progression such that q + ℓ ≥ q last . Similarly to above, it can be shown that there is an occurrence of y in the progression followed by an occurrence of u iff q +|y| is followed by an occurrence of u. We can decide whether this is the case in constant time by one longest common extension query and if it is report q as an occurrence of yu thus reducing to the first case.


Mohammad Sadegh

M.S Shakeri Shakeri
email: ms.shakeri@ifj.edu.pl

Phase formation by pulsed laser irradiation of suspended nanoparticles has recently been introduced as a promising synthesis technique for heterostructures. The main challenge still lingers regarding the exact mechanism of particle formation due to the non-equilibrium kinetic by-products resulting from the localized alternative, fast, high-temperature nature of the process. Here, we analyze the bond breaking/formation of copper or copper (II) interfaces with ethanol during the absorption of pulses for Cu-CuO-Cu2O formation applicable as a hyper-electrocatalyst in ethanol oxidation fuel cells. This study includes but is not limited to, a comprehensive discussion of laser-suspension interaction for practical control of the synthesis process. We have shown that beyond the physical transitions, the local interface between dissociated ethanol and the molten sphere is responsible for the oxidative/reductive interactions resulting in the formation of catalytic-augmented Cu 3+ by-product, thanks to the reactive bond force field molecular dynamics studies confirmed by ab-initio calculations and experimental observations.

Main

It is no exaggeration to say that the high application potential of the interaction between lasers and matter fascinates the scientific community with new applications every day. In this respect, the concept of laser-suspension interaction is not yet fully developed, but it promises a whole range of applications due to the temperature selectivity enabled by the absorption rules. When a suspension is irradiated with a laser pulse, the electromagnetic wave is locally absorbed by the suspended agglomerates, resulting in a temperature rise. Depending on their temperature, possible phase formations/transitions take place in a short time of the pulse duration. Immediately, the particles are cooled to ambient temperature by thermal equilibrium with the solvent molecules, which are transparent to the laser beam. This process is alternatively repeated during pulsed laser irradiation of suspensions (PLIS), initially known as pulsed laser melting in liquid (PLML) [START_REF] Ishikawa | Nano-and submicrometer-sized spherical particle fabrication using a submicroscopic droplet formed using selective laser heating[END_REF][START_REF] Ishikawa | Spherical particle formation mechanism in pulsed laser melting in liquid under controlled-pulse-number irradiation using a slit nozzle flow system[END_REF][START_REF] Pyatenko | Growth mechanism of monodisperse spherical particles under nanosecond pulsed laser irradiation[END_REF][START_REF] Ishikawa | Boron carbide spherical particles encapsulated in graphite prepared by pulsed laser irradiation of boron in liquid medium[END_REF][START_REF] Wang | Sizetailored ZnO submicrometer spheres: bottom-up construction, size-related optical extinction, and selective aniline trapping[END_REF][START_REF] Wang | General Bottom-Up Construction of Spherical Particles by Pulsed Laser Irradiation of Colloidal Nanoparticles: A Case Study on CuO[END_REF][START_REF] Shakeri | Solvent-particles interactions during composite particles formation by pulsed laser melting of α-Fe2O3[END_REF]. In 2007, Ishikawa et al [START_REF] Ishikawa | Boron carbide spherical particles encapsulated in graphite prepared by pulsed laser irradiation of boron in liquid medium[END_REF] reported for the first time that unlike the laser ablation process used to produce smaller nanoparticles, PLML uses lower laser fluences and forms larger particles than the original constituents by melting. Later, an absorption model was introduced to calculate the temperature of suspended particles irradiated by a pulsed laser [START_REF] Wang | Single-crystalline rutile TiO2 hollow spheres: room-temperature synthesis, tailored visible-light-extinction, and effective scattering layer for quantum dot-sensitized solar cells[END_REF], followed by the addition of a cooling term to the model to calculate the temperature even more accurately [START_REF] Sakaki | Pulsewidth dependence of the cooling effect on sub-micrometer ZnO spherical particle formation by pulsed-laser melting in a liquid[END_REF]. However, these efforts facilitate the interpretation of thermodynamic phase transitions during PLIS; the undeniable role of the kinetics of the probable chemical reactions has been ignored. Here, we first attempted to investigate how the laser/suspension parameters affect particle formation during nano-pulsed laser irradiation of suspended Cu or CuO nanoparticles in ethanol by studying the thermodynamically stable phases using conventional and PLIS-based phase diagrams. The oxidation state of copper was also analyzed experimentally and theoretically to reveal the evolution of Cu-CuO-Cu2O production as well as the possible formation of kinetic by-products. Besides, reactive bond molecular dynamics (RBMD) was used to study the kinetics of bond breaking/formation when the temperature of the ethanol-particle box is increased. In parallel, we proposed a mathematical model utilizing the laser-suspension parameters to consider the alternative particle growth during the PLIS process. We introduced the high-temperature solvent-sphere interactions, in addition to the physical phase transitions, as the main mechanisms for the PLIS synthesis of remarkable Cu-CuO-Cu2O electrocatalysts for ethanol oxidation fuel cells. Exploring the precise role of effective laser-suspension parameters, particle temperature evolution, phase formation mechanism, and alternative particle growth not only introduces PLIS process as a preferred controllable synthesis method for heterostructures, but also gives scientists sufficient insight into its enormous potential applications.

Results

Phase formation, phase diagrams, and temperature evolution

Powders synthesized by the PLIS method (Supplementary part a) contain Cu, CuO, and Cu2O phases according to JCPDS Nos. 003-1018, 48-1548, and 05-0667, respectively (Fig. 1a). The change in the intensity of the peaks shows the laser-induced variation in the oxidation state of Cu-CuO-Cu2O composite. According to the calculated phase diagrams in the Cu-O-C-H system, oxygen pressure plays an important role in the transitions between copper and its oxides (𝐿𝑜𝑔 𝑃 𝑂 2 -𝑇 diagram) when the temperature is high enough to avoid the formation of Cu(OH)2 and CuCO3 phases (Fig. 1b).

Moreover, the high pressure of CO (𝐿𝑜𝑔 𝑃 𝐶𝑂 -𝐿𝑜𝑔 𝑃 𝑂 2 diagram) causes the reduction of the oxide phases and the subsequent formation of metallic Cu (Fig. S1). Hence, more likely Cu, CuO, and Cu2O and less likely Cu(OH)2 and CuCO3 are the thermodynamically stable phases which are able to be crystallized in this system.

To display phase diagrams with the functionality of laser/suspension parameters, the reaction pathways of Cu and CuO phases were recorded by calculating the temperature dependence of enthalpy and Gibbs free energy of the phases (Table S2 and Fig. S2). Consequently, 𝐽𝜎 𝑎𝑏𝑠 𝜆 (𝑑) = 𝑚 𝑝 𝛥𝐻 was solved numerically and the laser fluence (J) required for all possible transitions was calculated for different sizes (D) of Cu and CuO spheres (Fig. 1c). Similarly, the dielectric constant was manipulated to show the flexible phase boundaries induced by the dynamic absorption efficiency (Fig. S3). On the other hand, the temperature profile of the particles was calculated numerically using the 4 th order Rung-Kutta solution of

𝑑𝐸 𝑑𝑡 = 𝑑𝐸 𝑎𝑏𝑠 𝑑𝑡 - 𝑑𝑞 𝑑𝑡
when both energy absorption and heat release are considered simultaneously (Fig. 1d). We have found that the contribution of energy absorption dominates the first and middle thirds of the Gaussian pulse, while heat dissipation tends to dominate the last third (Fig. S4). Therefore, pulse shape and pulse duration are responsible for the conservation of energy and heat dissipation, respectively. Nano-sized Cu and CuO particles experience the highest temperatures of 2843 and 2858 ̊ K, corresponding to 𝐶𝑢(𝑙) ↔ 𝐶𝑢(𝑔) and 𝐶𝑢 2 𝑂(𝑙) ↔ 2𝐶𝑢(𝑔) + 1 2 𝑂 2 (𝑔) reactions, respectively (Fig. 1e), while there is an inverse relationship between temperature and sub-micron particle size. The initial size distribution of agglomerates in the suspension is believed to be responsible for the multiphase crystallization leading to the synthesis of Cu-CuO-Cu2O heterostructures.

Static oxidation state study

Among 9 optical phonon modes of CuO with 𝐶 2ℎ 6 space group and 15 modes of Cu2O with 𝑂 ℎ 4 space group [START_REF] Tuschel | Practical group theory and Raman spectroscopy, part i: Normal vibrational modes[END_REF], 4 vibrational modes were observed in the Raman spectra of samples (Fig. 2a,b). The peak at 212 cm -1 , corresponding to 2Eu phonon mode, is generated by the twisting of Cu4O tetrahedron around the c-axis of Cu2O. There are also all three visible phonon modes of CuO, i.e., Ag mode centered at 280 cm -1 , Bg at 325 cm -1 , and 2Bg at 610 cm -1 . The T1u modes of Cu2O and/or bis-μ-oxo dimer core vibration of CuO2 -(copper oxide III) also oscillate at 610 cm -1 [START_REF] Deng | In situ Raman spectroscopy of copper and copper oxide surfaces during electrochemical oxygen evolution reaction: identification of CuIII oxides as catalytically active species[END_REF]. Raman spectra showed greater formation of Cu2O in the higher fluence irradiated CuO-ethanol samples and maximization of Cu2O in Cu150 among Cu-ethanol samples.

A much stronger shake-up satellite accompanied by a Cu 2p peak in XPS spectra is associated with more Cu 2+ species [START_REF] Mark | Resolving surface chemical states in XPS analysis of first row transition metals, oxides and hydroxides: Sc, Ti, V, Cu and Zn[END_REF][START_REF] Shen | Role of materials chemistry on the electrical/electronic properties of CuO thin films[END_REF]. Moreover, the absolute binding energy values (BE) of Cu 2p peaks do not allow us to distinguish between Cu + and Cu 0 oxidation states and between Cu 2+ and Cu + octahedral, since the differences between their energies are small [START_REF] Mark | Advanced analysis of copper X-ray photoelectron spectra[END_REF][START_REF] Białas | Copper aluminum spinels doped with cerium as catalysts for NO removal[END_REF][START_REF] Ghijsen | Electronic structure of Cu 2 O and CuO[END_REF]. In such a case, the distinction between Cu + and Cu 0 species can be derived from Wagner's Cu 2p3/2 -Cu L3M45M45 diagram [START_REF] Mark | Advanced analysis of copper X-ray photoelectron spectra[END_REF][START_REF]Database[END_REF]. Thus, to investigate the oxidation states qualitatively and quantitatively, we used information from highresolution spectra of Cu 2p (Fig. 2c,f), Cu L3M45M45 (Fig. 2d,g), and O 1s (Fig. 2e,h) regions simultaneously (Supplementary part c). The main photoelectron peaks of Cu 2p are accompanied by strong shake-up satellites in Cu-50 and CuO-RAW samples confirming the presence of copper mainly as Cu 2+ species [START_REF] Severino | Nature of copper active sites in the carbon monoxide oxidation on CuAl2O4and CuCr2O4Spinel type catalysts[END_REF][START_REF] Platzman | Oxidation of polycrystalline copper thin films at ambient conditions[END_REF][START_REF] Wu | Quantitative analysis of copper oxide nanoparticle composition and structure by X-ray photoelectron spectroscopy[END_REF][START_REF] Chusuei | Correlation of relative X-ray photoelectron spectroscopy shake-up intensity with CuO particle size[END_REF]. On the other hand, the weakest satellites are observed in the spectra obtained for Cu150 and CuO400, reflected in the smallest area of the sum of their CuO and Cu(OH)2 components (Cu 2+ content), which is less than 37 % of the total Cu 2p area. In Cu-ethanol samples, an increase in the low oxidation states (Cu 0 and Cu + ) is observed with increasing laser fluence at the expense of a decrease in the Cu 2+ components (both oxide and hydroxide). For Cu150, the (Cu 0 + Cu + )/Cu 2+ ratio reaches a maximum value of 2.9, while among CuO-ethanol samples, it is maximized at about 1.7 for CuO200 and CuO400.

The Cu K-edge absorption spectra (supplementary part d) include a pre-edge, an excrescence, and the main peak attributed to 1𝑠 → 3𝑑, 1𝑠 → 4𝑝 𝑧 , and 1𝑠 → 4𝑝 transitions, respectively (Fig. 2i,k) [START_REF] Timoshenko | Supervised machine-learningbased determination of three-dimensional structure of metallic nanoparticles[END_REF].

Although the 1𝑠 → 3𝑑 transition is forbidden according to the dipole selection rules, the pre-edge feature is defined as 3d-4p orbital mixing as well as vibronic and direct quadrupole coupling [START_REF] Cabaret | Firstprinciples calculations of X-ray absorption spectra at the K-edge of 3d transition metals: an electronic structure analysis of the pre-edge[END_REF][START_REF] Yang | Sensitive X-ray Absorption Near Edge Structure Analysis on the Bonding Properties of Au30 (SR) 18 Nanoclusters[END_REF].

The energy of the main peak decreases with laser fluence, while the excrescence energy is constant in all samples. However, the pre-edge shift behaves inconsistently, i.e., it increases for Cu-ethanol samples and decreases for CuO-ethanol samples (Table S7), which can be attributed to Cu oxidation and CuO reduction, respectively. Consequently, greater copper oxidation shifts the pre-edge to higher energies and vice versa. Linear combination fitting (LCF) of composite powders shows wall-to-wall conformance when Cu, CuO, and Cu2O reference spectra were utilized (Fig. S6). Quantitative LCF analysis shows the enrichment of Cu2O and the decrease of CuO with increasing laser fluence in both groups of samples. There is reasonable agreement between the quantitative results of the XPS and XANES spectra (Table S8).

Bond breaking/formation by molecular dynamics simulations

We observed the increasing traces of ethylene, methane, ethane and carbon monoxide by laser fluence in the chromatograph chamber (Table S10). These compounds were formed by dissociation of ethanol, although we know that the solvent is transparent to the laser beam. Therefore, we decided to investigate the particle-solvent interaction by means of reactive bond molecular dynamics (RBMD) simulations to support the hypothesis that phase formation during the PLIS process occurs not only through thermodynamic phase transitions, but also through oxidation/reduction processes induced by the interactions between dissociated solvent and molten sphere (supplementary part e).

According to the RBMD simulation (Table S11), the interaction between the solvent and the solid phase starts with the absorption of ethanol at the solid surface (Supplementary Video1). In the correlated MB1 simulation box (Figs. S9 andS11), the decomposition of ethanol begins with the absorption of the separated 𝑂𝐻 -groups on the Cu surface. The remaining C2H5 is decomposed to C2H4, followed by the formation of smaller hydrocarbons (Fig. 3a). The behavior of CuO in the MB2 simulation box, on the other hand, is different, since the decomposition of the solvent begins with the splitting off of H + and its subsequent adsorption on the oxide surface (Fig. 3b). The stronger tendency to react with oxygenated anions and hydrogenated cations is the main difference between the behavior of Cu and CuO heated spheres, respectively (Table S13). The reason for observing such a difference is attributed to the basic tendency of 𝐶𝑢 0 /𝐶𝑢 2+ to be oxidized/reduced in ethanol, depending on the oxygen content of the box, which is also confirmed by DFT calculations (Supplementary part f).

Thus, copper absorbs oxygen from ethanol (2𝐶𝑢 + 1 2

𝑂 2 = 𝐶𝑢 2 𝑂), while ethanol absorbs oxygen from copper oxide (𝐶 2 𝐻 5 𝑂𝐻 + 2𝑂 2 = 2𝐶𝑂 2 + 3𝐻 2 𝑂), both for oxidation purposes [START_REF] Huang | Molecular Dynamics Study of Laser Interaction with Nanoparticles in Liquids and Its Potential Application[END_REF][START_REF] Feng | Ethanol oxidation with high water content: A reactive molecular dynamics simulation study[END_REF][START_REF] Wang | Promotion effect of methane activation on Cu (111) by the surface-active oxygen species: a combination of DFT and ReaxFF study[END_REF][START_REF] Kański | Development of a Charge-Implicit ReaxFF for C/H/O Systems[END_REF][START_REF] Cheng | Nature of the active sites for CO reduction on copper nanoparticles; suggestions for optimizing performance[END_REF][START_REF] Ferrin | Modeling ethanol decomposition on transition metals: a combined application of scaling and Brønsted-Evans-Polanyi relations[END_REF]. By changing the temperature of the simulation box (models MB3 and MB4), the only difference detected was the ethanol decomposition rate, which was found to be 0.60, 5.35, and 55.42 molecules/ps for the solvents decomposed at 1000, 1500, and 2843 ̊ K, respectively. The reduction of the decomposition rate of ethanol is also observed when the temperatures of the solvent and the sphere are different (Fig. 3c,d).

The lowest decomposition rate was observed for the model with solvent at room temperature and sphere at 2843 ̊ K. During 125 ps of MD simulation for this model (MB6), the absorption of ethanol on the surface and its initial decomposition to C2H5 + and OH -are observed. Consequently, the temperature change influences the phase formation by changing the decomposition rate of the solvent.

Considering the statistical analysis in terms of the new species timeline (MB7 model), oxidation evolution proceeds through (I) ethanol absorption on the Cu surface, (II) hydroxyl cleavage of ethanol, (III) formation of Cu clusters during copper melting, (IV) surface oxidation with hydrogenated compounds, (V) decomposition of C2H5 into smaller hydrocarbons, and (VI) net oxidation (Table S13). Ethanol decomposition for the CuO-ethanol system is accelerated compared to the Cu-ethanol system (Fig. 3e). Statistical analysis also showed that surface oxidation begins with the absorption of hydroxyl and water molecules on Cu clusters (Fig. S10). Later, the hydrogen is separated and the oxygen forms bonds with several copper atoms to achieve net oxidation (Supplementary Video 2). Time-dependent snapshots of the MB1 cross section show deep diffusion of oxygen and hydrogen compounds into the interior of the sphere, while carbon compounds tend to remain in the surface layers. The accumulation of carbon and oxygen at the surface was also observed in the HAADF-EDX map of a Cu150 particle (Fig. 3f).

Microstructure and growth of particles

Analysis of different parts of a given sample by shifting the laser focus in Raman spectroscopy revealed widespread changes in the intensity of Raman shifts (Supplementary part g). The synchronization between PLIS-based phase diagrams (Fig. 1c,e) and the size distribution of the resulting particles (Fig. 4a-h) indicated the possible crystallization of different phases, which was also confirmed by HRTEM analysis (Supplementary part h). To examine particle formation during the PLIS process in more detail, we have attempted to derive a series of equations to see how particles grow during the PLIS process (Supplementary Part j). According to this model, the agglomerates are irradiated with a laser pulse, which leads to fusion and formation of larger particles. Due to the alternative nature of pulsed laser irradiation, these particles have enough time to form new agglomerates, which with a certain probability can be irradiated by another laser pulse, resulting in new growth up to a size that can be melted by the laser beam [START_REF] Wang | Sizetailored ZnO submicrometer spheres: bottom-up construction, size-related optical extinction, and selective aniline trapping[END_REF]. The calculated probability of the probe (X) showed that the different sizes of Cu agglomerates are irradiated almost between 1-2 times, while CuO agglomerates are irradiated between 1-3 times (Fig. 4i,j). The calculation of 𝑋 ≥ 1

rejected the hypothesis of the presence of LCF-measured copper as the residual phase. The formation of the necking zone observed mainly in the low fluence irradiated samples (Fig. 4k-n) was also simulated by the MB9 model (Fig. 4o). Here, the atoms involved in the bond breaking/formation process move towards the center of the simulation box, while the necking zone between two spheres is observed first (Supplementary Video3). Finally, multistage modeling (models MB10 and MB11)

showed a more complete dissociation of the solvent due to the increased formation of H2, H2O, CO, and C2 molecules compared to the previous stage (Fig. S13). Furthermore, solvent degradation shifts to the lower times as the number of stages increases, which is due to greater net oxidation (Fig. S14).

Possible formation of hypothetical Cu2O3

In some SAED patterns (Fig. 5c), we detected d-spacing around 3.25 Å, indicating a possible trace of a different oxidation state of copper [START_REF] Deng | In situ Raman spectroscopy of copper and copper oxide surfaces during electrochemical oxygen evolution reaction: identification of CuIII oxides as catalytically active species[END_REF]. A high-resolution XRD pattern also proved the existence of a characteristic peak at 2θ=27.5̊ (Fig. 5a) attributed to the (111) plane of the orthorhombic Cu2O3 phase (Fig. 5b). We found that the Cu2O3 phase is located at the CuO/Cu2O interface (Fig. 5d) and/or at the surface of Cu2O particles (Fig. S20), mainly due to the formation of areas of high oxygen content during the crystallization of Cu2O from CuO.

Electrocatalysis of ethanol oxidation

The electrochemically active surface area (ECSA) showing hydrogen absorption region calculated from the cyclic voltammogram curves (CV) (Fig. 6a) showed the highest mass activity [START_REF] Mark | Electrocatalyst approaches and challenges for automotive fuel cells[END_REF][START_REF] Duran | Electrochemical Active Surface Area Determination of Iridium-Based Mixed Oxides by Mercury Underpotential Deposition[END_REF] of 5065.00 cm 2 /mgCu and 2037.50 cm 2 /mgCu for CuO200/C and Cu200/C catalysts, respectively (Table S19). Moreover, the best catalytic properties were observed for the Cu100/C and Cu200/C catalysts.

In general, Cu-ethanol/C catalysts had greater potential for the ethanol oxidation reaction than CuOethanol/C catalysts (Fig. 6b), which can be attributed to the EOR consumption for CuO reduction [START_REF] Dupont | Electrochemically active surface area effects on the performance of manganese dioxide for electrochemical capacitor applications[END_REF][START_REF] Wang | Time-resolved studies for the mechanism of reduction of copper oxides with carbon monoxide: complex behavior of lattice oxygen and the formation of suboxides[END_REF]. The value of the onset potential is also minimized for Cu100/C and Cu200/C catalysts (Fig. S28).

As the most effective catalysts, Cu100/C and Cu200/C were investigated by in situ FTIR to reveal the products of ethanol oxidation (Fig. 6c,d). The IRRAS spectral peaks corresponding to CO2 (complete oxidation), CO, CH3CHO, and CH3COOH (partial oxidation) [START_REF] Kowal | Ternary Pt/Rh/SnO2 electrocatalysts for oxidizing ethanol to CO2[END_REF][START_REF] Shanza Rauf Khan | Investigation of catalytic and fuel additive applications of copper/copper (I) oxide/copper (II) oxide (Cu/CuO/Cu2O) microspheres synthesized by hydrothermal method using sucrose as template[END_REF] are at 2360 cm -1 , 2100 cm -1 , 1340 cm -1 , and 1280 cm -1 , respectively (Fig. S29). The highest absorption was observed for CO2 and the ratio of CO2/CO was measured to be 43 and 1400 for Cu200/C and Cu100/C catalysts, respectively (Fig. 6c,d and Table S19). Compared to the Cu200/C catalyst, the Cu100/C catalyst, which consists of smaller particles (larger surface area), produced 4 times more CO2 and about 10 times less CO, making it the most effective catalyst among all samples (Table S21). The Cu100/C

catalyst retains its full oxidation potential even after 12 hours, which was not observed for Cu200/C.

Apart from the surface area and compositional changes that made the 27.5%Cu-19.2%CuO-53.3%Cu2O sample the optimal electrocatalyst, the remarkable electrocatalysis measured here is also attributed to the role of Cu 3+ ions on the surface of the particles. The higher surface oxide (Cu 3+ ) in transition metal oxides (TMOs) and also the accumulation of charge carriers in the TMO heterojunctions facilitate the adsorption of alcohol, the desorption of decomposed molecules and the cleavage of the C-H bond by lowering the kinetic barrier [START_REF] Prajapati | Fundamental insight into electrochemical oxidation of methane towards methanol on transition metal oxides[END_REF][START_REF] Najafishirtari | A perspective on heterogeneous catalysts for the selective oxidation of alcohols[END_REF].

Discussions

Suspended agglomerates are heated by the energy absorption of a laser pulse according to their absorption efficiency, which is defined by the ratio between the wavelength of irradiation and the absorption cross section calculated according to the Mie theory. The absorbed energy is directly proportional to the laser fluence and the surface area of the agglomerate. On the other hand, the pulse factors influence the temperature development, so that the pulse shape is responsible for heat conservation, while the pulse duration controls the heat release. Cooling of the particles and reagglomeration of the irradiated particles occurs in the time between pulses by synergistic agitation of the suspension. In addition, pulse repetition affects particle growth by changing the probability of the probe. The heating-cooling process is repeated depending on the probability of the probe in the system, resulting in alternative particle growth limited by the melting possibility of agglomerates. The size distribution depends on the solvent molecules, the initial size of the nanoparticles and the slurry, which determines the temperature gradient of the agglomerates. More importantly, the temperature of agglomerates not only determines their thermodynamically stable phases, but also affects the rate of oxidation/reduction processes during interfacial solvent-particle interactions.

Although the solvent bath is at ambient temperature, the kinetic energy of the molecules coming into contact with the surface of the heated particles is very high, resulting in the bond breaking/formation at the interface between the dissociated solvent and the heated particles. The dissociated species diffuse into the sphere where the oxidation/reduction reactions take place according to their nature. In ethanol, the oxygen-hydrogen compounds diffuse deep into the particles, while larger carbon compounds tend to reside in the layers near the interface. So while the inner part of a particle has more to do with oxidation and physical transitions, the outer part is more controlled by chemical oxidation/reduction reactions that lead to the formation of kinetic byproducts. Here, experimental observations confirmed by DFT and MD simulations showed the formation of a higher oxidation state of copper, i.e., Cu 3+ , due to the enrichment of oxygen in the CuO-Cu2O interface and/or on the surface of the particles, resulting in the observation of excellent electrocatalysis in the ternary Cu-CuO-Cu2O

catalyst. The presented optimal catalyst is able to retain its potential for complete ethanol oxidation even after 12 hours of use. The present novel study dealing with the comprehensive laser-suspension

interaction not only provides a basis for heterostructure synthesis by PLIS, but also opens the knowledge gate to the perspective of the discipline.

Methods

Raw materials, suspension preparation, and irradiation process

Cu (US Research Nanomaterials, 40 nm average size, 99.9% purity, and 5 mM) or CuO (Sigma Aldrich powder, 50 nm average size, 99.5% purity, and 5 mM) nanoparticles (NPs) were dispersed in ethanol (POCH solvent, 99.8% purity) medium to prepare suspensions with a concentration of 0.0027 gr/liter. 15 ml of the resulting suspension was ultrasonically mixed and transferred to a sealed cell with a quartz window transparent to 523 nm wavelength. Then the mixture was irradiated with an unfocused pulsed laser beam generated by a Nd:YAG laser operating in second harmonic mode at a wavelength of 532 nm and a repetition rate of 10 Hz. Energy densities of 50, 100, 150, and 200 mJ/cm 2 .pulse for Cu-ethanol and 100, 200, 300, and 400 mJ/cm 2 .pulse for CuO-ethanol samples were used to irradiate colloidal suspensions for 60 minutes (Table S1). Ultrasonic agitation was used during irradiation to prevent undesirable sedimentation of suspended particles/agglomerates.

Characterizations

The patterns of the crystal structure of the particles were measured with an X-ray diffractometer (XRD, PANalytical X'Pert Pro). The detection was performed with Cu Kα (α = 1.54 Å) radiation at an operating current and voltage of 30 mA and 40 kV, respectively.

The WITec confocal Raman microscope (CRM alpha 300R), equipped with a λ = 532 nm laser and an Olympus MPLAN (100x/0.90NA) objective, was used to record Raman spectra. Data were accumulated using 60 scans with an integration time of 30 s and a resolution of 3 cm -1 . The monochromator of the spectrometer was calibrated on the basis of the Raman scattering line of a silicon plate (520.7 cm -1 ). Cooper and its oxides are generally susceptible to heat-induced phase changes [START_REF] Tuschel | Practical group theory and Raman spectroscopy, part i: Normal vibrational modes[END_REF][START_REF] Deng | In situ Raman spectroscopy of copper and copper oxide surfaces during electrochemical oxygen evolution reaction: identification of CuIII oxides as catalytically active species[END_REF]. Therefore, the spectra were recorded at very low laser power to avoid the thermal change induced by the laser (~ 0.45 mW). Baseline correction and cosmic ray removal were performed using WitecFour Plus software, version 5.3, while peak fitting analysis was performed using the software package GRAMS, version 9.2.

X-ray photoelectron spectroscopy (XPS) was performed in a multichamber UHV system with a hemispherical analyzer (SES R4000, Gammadata Scienta). A nonmonochromated AlK (1486.6 eV)

X-ray source with an anode operating at 12 kV and 15 mA current emission was used to generate the core excitation. The spectrometer has been calibrated in accordance with ISO 15472:2001. The energy resolution of the system operating at a fixed let-through energy of 100 eV was 0.9 eV (measured as full width at half maximum for the Ag 3d 5/2 excitation line).The base pressure in the analysis chamber was about 110 -10 mbar, and during the experiment, it was about 210 -9 mbar. In addition, the area of sample analysis was approximately 4 mm 2 (50.8 mm). The binding energy (BE) of the random carbon species was used to correct the measured spectra for surface charge (C 1s line at BE = 285.0 eV). Intensities were estimated by calculating the integral of each peak (CasaXPS 2.3.23) after subtracting the Shirley-type background and fitting the experimental curves with a combination of variable-ratio Gaussian and Lorentz lines (70:30).

The suspensions obtained from PLIS were precipitated on the sample holder and air-dried for X-ray absorption spectroscopy (XAS) analyzes. Absorbance sieves of finely powdered pure CuO, Cu2O

(purchased from Merck Co.), and Cu foil were also prepared as a reference for calculating the percentage of phases using the linear combination fitting (LCF) method. The X-ray absorption spectra were recorded at the ASTRA beamline of the National Synchrotron Radiation Center in Krakow, Poland (SOLARIS). The spectrum of the Cu metal foil was accurately recorded before each XAS measurement for calibration purposes. Finally, the spectra were imported into the XAS computer software "Athena" for normalization and extraction of the data [START_REF] Ravel | ATHENA, ARTEMIS, HEPHAESTUS: data analysis for X-ray absorption spectroscopy using IFEFFIT[END_REF].

The LCF method was evaluated by mathematically fitting the X-ray absorption spectra (XAS) of the resulting composite particles with the same spectra measured for Cu, CuO, and Cu2O as reference. In this method, which uses the additive nature of the absorption of each species, the proportions of the reference spectra are added to reconstruct the spectrum of choice. However, it can be applied to XANES, XANES derivative, or EXAFS spectra; here we used it for the entire XAS range measured.

The total absorption coefficient can be written as the sum of the chemical forms or species as 𝑆𝑎𝑚𝑝𝑙𝑒 = ∑ 𝑓 𝑖 (𝑆𝑇𝐷 𝑖 ). Here, "Sample" stands for the least square fit to the energy range of the sample spectrum, and fi stands for the scaling factors applied to each corresponding standard spectrum (STDi). The scaling factor determined from the LCF indicates the proportion of the individual phases in the analyzed sample. The subroutine of LCF was created with the software Athena (XAS data analysis). Here we performed LCF by fitting the normalized µ(E) spectrum of the composite samples over the reference spectra from 8900 to 9300 eV. The relative weights of the species can vary from 0 to 1 and the absorption edge energies are kept fixed during the analysis.

The hydrodynamic diameter of Cu and CuO nanoparticles was measured by dynamic light scattering (DLS) using a Malvern Zetasizer Nano-ZS instrument equipped with a He-Ne laser (λ = 633 nm) and operated at a backscattering angle of 173°.

The morphology of the synthesized particles was observed using a scanning electron microscope (Hitachi S4800 and Tescan Vega3). In addition, the average particle size was determined by measuring the diameters of 50 particles from each SEM image using ImageJ software.

The high-resolution images, selected area electron diffraction (SAED) patterns, and EDS-chemical maps were evaluated by a transmission electron microscopy (TEM, FEI Tecnai F20, 200 kV).

Thermodynamic and thermal calculations

The calculations of the thermodynamic equilibrium in the Cu-O-C-H system were carried out with the HSC Chemistry package (ver. 10.x, https://www.hsc-chemistry.com/). This software is also used for accurate calculation of Cp and enthalpy at different temperatures. The reaction pathways of heated Cu and CuO were also extracted from the Gibbs free energy and enthalpy diagrams from HSC Chemistry.

Heating-melting-vaporization model

There is a relationship between the laser fluence, the absorption cross section, the particle weight and the enthalpy of the particles as,

𝐽𝜎 𝑎𝑏𝑠 𝜆 (𝑑) = 𝑚 𝑝 𝛥𝐻 (1)
Where, J (J.cm -2 pulse -1 ) is the laser fluence, 𝜎 𝑎𝑏𝑠 𝜆 (cm 2 ) is the absorption cross-section of particles, 𝑚 𝑝 (g) is the particle mass, and 𝛥𝐻 (J g -1 ) is the enthalpy of the particles. The absorbed energy increases the temperature of the particle undergoing thermodynamic phase transitions.

To calculate the enthalpy of Cu and CuO spheres, the reaction paths must be known. When copper is heated, there are only two transitions, melting and boiling, so the enthalpy changes as follows.

𝛥𝐻 = ∫ 𝐶 𝑃 𝑠 (𝑇)𝑑𝑇 𝑇 𝑚 𝑇 0 + 𝛥𝐻 𝑚 + ∫ 𝐶 𝑃 𝑙 (𝑇)𝑑𝑇 𝑇 𝑏 𝑇 𝑚 + 𝛥𝐻 𝑏 (2)
here 𝐶 𝑃 𝑠 (𝑇) and 𝐶 𝑃 𝑙 (𝑇) (J g -1 K -1 ) are the heat capacities of solid and liquid Cu. Similarly, 𝛥𝐻 𝑚 and 𝛥𝐻 𝑏 (J g -1 ) are the latent heat of melting and boiling of Cu, which take place at 𝑇 𝑚 and 𝑇 𝑏 (  K), respectively. Finally, 𝑇 0 (  K) is the ambient temperature which was set to 298  K in all calculations.

For CuO (copper oxide (II)), for which the reaction pathway is shown in Table S2

here, 𝐶 𝑝 𝐶𝑢𝑂(𝑠) , 𝐶 𝑝 𝐶𝑢 2 𝑂(𝑠) , and 𝐶 𝑝 𝐶𝑢 2 𝑂(𝑙) (J g -1 K -1 ) are the heat capacities of solid CuO, solid Cu2O and molten Cu2O, respectively. Moreover, 𝛥𝐻 𝐶𝑢𝑂(𝑠)→𝐶𝑢 2 𝑂(𝑠) , 𝛥𝐻 𝑚 , and 𝛥𝐻 𝐶𝑢 2 𝑂(𝑙)→𝐶𝑢(𝑔) (J g -1 ) are the latent heat of CuO(s)-Cu2O(s) transition, Cu2O fusion, and Cu2O(l)-Cu(g) transition occurring at 𝑇 𝐶𝑢𝑂(𝑠)→𝐶𝑢 2 𝑂(𝑠) , 𝑇 𝑚 , and 𝑇 𝐶𝑢 2 𝑂(𝑙)→𝐶𝑢(𝑔) (  K) temperatures, respectively. Fig. S2 shows the changing trends of Cp and H for both phases. It also shows the transition temperatures used to design the reaction pathways according to the Gibbs free energy diagrams. The laser fluence is calculated as follows,

𝐽 = 𝐸 0 𝐴 𝐿 ⁄ (4)
where, 𝐸 0 (J pulse -1 ) is the pulse energy; 𝐴 𝐿 (cm -2 ) is the cross section of the laser beam. Fig. S4 shows the pulse shape and cumulative pulse intensity used in this study. The Gaussian distribution of the pulse shape would be responsible for the heating. The change in the intensity of the laser pulse due to the propagation direction of the laser affects the heat balance, which we will explain in more detail using the heating-cooling model. The absorption cross section of particles, which is responsible for the absorption of electromagnetic radiation, is calculated by the following equation.

𝜎 𝑎𝑏𝑠 𝜆 (𝑑) = 𝜋𝑑 2 𝑄 𝑎𝑏𝑠 𝜆 (𝑑) 4 (5)
here, d is the particle diameter and 𝑄 𝑎𝑏𝑠 𝜆 (𝑑) is the absorption efficiency of the particles calculated using scattering techniques (Mie theory in the case of submicron particles). The absorption efficiencies of Cu and CuO particles were calculated as a function of particle diameter using MiePlot software (ver. 4620, http://www.philiplaven.com/mieplot.htm), as shown in Fig. S3. The optical parameters used in the MiePlot software are listed in Table S3.

The weight of the spheres is calculated as follows,

𝑚 𝑝 = 𝜌 𝑝 (𝜋𝑑 𝑝 3 ) 6 (6)
where, 𝜌 𝑝 (g cm -3 ) is the particle density.

Heating-cooling model

We define a model that takes into account the heating of the particles due to the absorption of the laser beam and the simultaneous cooling due to the heat transfer with the surrounding media. In this model, only conductive heat transfer is considered, since convection around the particles is negligible in the submicrometer range. Conductive heat transfer is expressed as follows;

𝑑𝑞 𝑑𝑡 = ℎ. 𝜋𝑑 2 (𝑇 𝑡 -𝑇 ∞ ) (7)
where, πd 2 is the particle surface area, T(t) is the particle temperature, T∞ is the temperature of the surrounding liquid (298 ̊ K), and h (Wm -2 K -1 ) is the heat transfer coefficient defined by Eq. ( 13) as follows, ℎ = 𝑁𝑢 𝑑 .𝐾 𝑑 [START_REF] Ishikawa | Boron carbide spherical particles encapsulated in graphite prepared by pulsed laser irradiation of boron in liquid medium[END_REF] where K is the thermal conductivity of the surrounding fluid, Nud is the Nusselt number, and d is the particle diameter. The Nusselt number is the ratio of convective heat transfer to conductive heat transfer. In the case of natural convection on a sphere, the Nusselt number is given by Eq. ( 14) as [START_REF] Huang | Molecular Dynamics Study of Laser Interaction with Nanoparticles in Liquids and Its Potential Application[END_REF],

𝑁𝑢 𝑑 = 2 + 0.589𝑅𝑎 𝑑 0.25 [1+(0469/𝑃𝑟) 0.56 ] 0.44 (9)
here, Rad is the Rayleigh number and Pr is the Prandtl number. For submicron particles, the magnitude of Nusselt number is equal to 2 because the Rayleigh number is negligible in the submicron range. The values of the heat transfer coefficient for ethanol are given in Table S2.

According to the heating-cooling model, the accumulated heat energy in a particle is the difference between the laser energy absorbed by a particle and the energy dissipated by conductive heat transfer,

𝑑𝐸 𝑑𝑡 = 𝑑𝐸 𝑎𝑏𝑠 𝑑𝑡 - 𝑑𝑞 𝑑𝑡 (10)
The amount of absorbed energy as a function of pulse duration is given as follows,

𝑑𝐸 𝑎𝑏𝑠 𝑑𝑡 = 𝑄 𝑎𝑏𝑠 𝜆 (𝑑).𝜋𝑑 2 𝐽(𝑡) 4 (11)
Matlab software (ver. R2022a, https:// www.mathworks.com/products/new_products/latest_features. html) was used for the numerical solution of differential equation of heating-cooling model using Rung Kutta 4 th order derivation (Eq. 10).

Gas Chromatography (GC)

The GC analyzes were performed using an Agilent 6890N gas chromatograph. The levels of carbon dioxide, carbon monoxide, and oxygen in each sample were measured using a micro TCD detector, Porapak Q, and Molsieve 5A packed columns in heart-cutting mode. Methane, ethane, and ethylene were separated using a micropacked GG alumina column and a FID detector. For high readings of certain gas concentrations (> 100ppm), the GC was calibrated with the gas mixtures produced by Multax, and the accuracy of the concentrations was more than 2% for all gasses. Low concentrations of gasses were referred to the accepted WMO scale with the set of secondary standards. Uncertainties of GC analyzes (single standard deviation), including sampling, sample transfer, and injection repeatability, were as follows: CO2: 0.5ppm, CO: 0.2ppm, O2: 0.1%, CH4: 0.1ppm, C2H4: 0.1ppm, and C2H4 (or EtO): 0.1ppm.

Reactive bond force field Molecular Dynamics

All molecular dynamics (MD) simulations were performed using the ReaxFF module of the AMS software package [START_REF] Rüger | AMS 2022[END_REF], using a reactive bond force field (RBFF) with Cu/C/H/O parameters [START_REF] Zhu | Development of a reactive force field for simulations on the catalytic conversion of C/H/O molecules on Cu-metal and Cu-oxide surfaces and application to Cu/CuO-based chemical looping[END_REF]. 3dimensional systems (Table S11) with cubic simulation boxes are constructed and the periodic boundary condition is applied in all three directions. The size of the cubic simulation boxes is adjusted accordingly to keep the density the same for all systems. The canonical ensemble (NVT) is used for all MD simulations in conjunction with the Nosé-Hoover thermostat with a damping constant of 100 fs. Prior to RBFF simulations, all systems undergo energy minimization using the conjugate gradient algorithm to optimize the initial geometric configuration, followed by NVT equilibration at 298 ̊ K for 5 ps. After reaching equilibrium, a series of RBFF-MD simulations is performed for each system (Table S11). In RBFF-MD simulations, the use of high temperatures to accelerate reactions is a common strategy to overcome limited computing power [START_REF] Chenoweth | ReaxFF reactive force field for molecular dynamics simulations of hydrocarbon oxidation[END_REF][START_REF] Feng | A reactive molecular dynamics simulation study of methane oxidation assisted by platinum/graphene-based catalysts[END_REF][START_REF] Mao | Formation of incipient soot particles from polycyclic aromatic hydrocarbons: A ReaxFF molecular dynamics study[END_REF]. More importantly, the present study is a comparative study of different cases, so the absolute temperature used is less important. A time step of 0.25 fs is used, which has been shown to be suitable for high temperature simulations with

ReaxFF MD [START_REF] Chenoweth | ReaxFF reactive force field for molecular dynamics simulations of hydrocarbon oxidation[END_REF]. The binding information and dynamic trajectory are recorded every 25 fs. For species analysis, a Cutoff value of 0.3 is chosen for the bond order to detect the molecules that form during the simulation. A low Cutoff value is helpful to cover all reactions even those with very shortlived species [START_REF] Białas | Copper aluminum spinels doped with cerium as catalysts for NO removal[END_REF]. Three parallel simulations were run for each simulation box and the average of these simulations was used for further analysis. The reaction pathways (timeline of new species) are analyzed using the Chemical Trajectory Analyzer (ChemTraYzer) scripts [START_REF] Döntgen | Automated discovery of reaction pathways, rate constants, and transition states using reactive molecular dynamics simulations[END_REF]. The visualizations of the simulation results are generated using AMS, Visual Molecular Dynamics (VMD) and Ovito programs [START_REF] Humphrey | VMD: visual molecular dynamics[END_REF].

Growth model

The details of the particle growth model were explained in supplementary part g. Eq. (S21), Eq. (S25), and Eq. (S18) were used to calculate Fig. 4i, Table S16, and Fig. 4j, respectively.

Ab-initio calculations

Quantum Espresso (QE) software was used to calculate the electronic structure and energy minimization of Cu(111) slab-ethanol, CuO(111) slab-ethanol and Cu2O3 unit cell models . DFT calculations began with atomic modeling. Then the models were relaxed by minimizing the energy of the system. The calculation of the self-consistent field (SCF) was the last step before the post-processing calculations. Post-processing calculations include but are not limited to the band gap (BG), the partial density of states, and adsorption energy. The adsorption energy (Eads) was calculated as follows,

Eads = Eslab-molecule -(Eslab+Emolecule) (12)
where Eslab-molecule is the total energy of Cu(111) and CuO(111) surface after ethanol adsorption, Eslab is the total energy of the Cu(111) and CuO(001) surface, and Emolecule is the total energy of the isolated ethanol molecule.

A vacuum layer (20 Å) is also added to each slab-containing model to avoid the effect of periodicity of the structure in heterojunction. The Perdew-Burke-Ernzerhof (PBE) of the generalized gradient approximation with the Hubbard on-site potential (GGA+U) approximation was utilized as exchange and interaction potentials. The Van der Waals (vdW) correction is adopted to describe long-range vdW interactions and the dipole-dipole interaction is employed in the case of an asymmetric arrangement of species. The cut-off energy of the electronic wavefunction was 600 eV, and the kspace integration is performed according to the Monkhorst-Park scheme fitted to the reciprocal space size of the crystal structure of the models. The geometry optimization of the model is terminated when the force on each ion is not stronger than 0.05 eV. We have used the pseudopotentials Cu.rel-pbesoldn-kjpaw_psl.0.2.UPF, O.rel-pbesol-n-kjpaw_psl.0.1.UPF, C.rel-pbesol-n-kjpaw_psl.0.1.UPF, H.relpbesol-kjpaw_psl.0.1.UPF from http://www.quantum-espresso.org.

In addition, the jfeff10 software (https://times-software.github.io/feff10/) was used to calculate the XAFS and XANES spectra of the probable crystallized phases in this system including Cu, CuO, Cu2O, Cu2O3, CuCO3, and Cu(OH)2. The unit cells of the above phases were relaxed using QE and the final atomic positions were used in jfeff10 for XAS calculations.

Catalyst preparation

For the electrochemical measurements, the powders obtained from the PLIS process were placed in the functionalized Vulcan XC -72R and the functionalization of the carbon support was carried out as follows. The carbon powder (20 mg) was immersed in a 0.7 M aqueous solution of HNO3 for 30 minutes at room temperature. The Vulcan XC-72R was rinsed with distilled water to a neutral pH and then dried at 100 C for 10 h. Prior to addition, the carbon support was heated to 100°C for 1 h under a pure nitrogen atmosphere and oxidized to form surface functional groups. After carbon functionalization, the washed synthesized powders were dispersed in an ultrasonic bath for 30 minutes and finally applied to Vulcan XC -72R, which was added dropwise with vigorous stirring. In the last step, the mixture was mixed over a night under magnetic stirring and the obtained black powder was washed with ethanol and distilled water. Then it was dried at 80°C for 10 h.

Electrochemical measurements

For the electrochemical measurements, a BIO-LOGIC SP -200 potentiostat was used in a standard three-electrode electrochemical cell. Uniform catalyst inks were prepared by ultrasonically mixing 2 mg catalyst powder with 400 μL isopropyl alcohol, 100 μL ultrapure water, and 10 μL 5 wt% Nafion solutions for 30 minutes. Then, 10 μL of the ink suspension was applied to a polished glassy carbon electrode (GCE) to obtain the working electrode with a homogeneous thin catalyst layer after the solvent was naturally air dried. To determine the EOR activity of the catalysts, cyclic voltammetry measurements (CV) were performed in ethanol-containing solution. A standard glass cell with a Pt counter electrode and a silver chloride reference electrode was used. The electrolyte, containing 0.1 M NaOH and 0.5 M C2H5OH, was deoxygenated by bubbling Ar for 30 min before measurements. All potentials reported in this article were calculated with respect to the reversible hydrogen electrode (RHE) and all measurements were made at room temperature.

The Infrared Reflection Absorption Spectroscopy (IRRAS) measurements

Spectroelectrochemical ATR-FTIR in situ measurements were performed using a NicoletiS50 FT-IR spectrometer equipped with an MCT detector cooled with liquid N2, an ATR accessory with ZnSe crystal, and an electrochemical cell. The working electrodes are the same as those used in electrochemical experiments. Spectra were calculated from 64 scans with a spectral resolution of 2 cm -1 , in the IR range between 1200 cm -1 and 3000 cm -1 . Measurements were performed for 12 h, and the spectrometer was rinsed with Ar 1 h before the experiment. In addition, argon gas was used permanently during these 12 h. The kinetics curves of the peaks were determined for every 30 minutes. The curves were indexed for peaks corresponding to CO2, CO, CH3CHO, and CH3COOH to show the dynamics of the EOR products. sphere changes during absorption of a laser pulse, accompanied by simultaneous heat release. These curves were plotted for the Cu sphere with a diameter of 200 nm and the CuO sphere with a diameter of 250 nm, which were selected on the basis of the average agglomerate size of their stable suspension in ethanol. (Fig. S22). Eq. ( 10) and the data presented in Table S3 were also utilized to calculate the temperature profile. with more than 5 laser foci of Raman spectroscopy, and the data presented here are those obtained with the maximum repetition (Fig. S16). XPS analysis of (c) Cu 2p, (d) Cu LMM, and (e) O 1s spectra for Cu-ethanol system. XPS analysis of (f) Cu 2p, (g) Cu LMM, and (h) O 1s spectra for CuOethanol system. The Cu 2p, Cu LMM, and O 1s spectra were fitted with 4, 2, and 4 Gaussian doubles, respectively. The details of the quantitative analysis derived from XPS curves were presented in supplementary part Normalized extended X-ray absorption fine structure (EXAFS) and X-ray absorption near edge structure (XANES) for Cu K-edge spectra of (i) Cu-ethanol and (j) CuO-ethanol samples. All samples were analyzed 3 times and the average spectrum was reproduced here. Analysis of the Cu foil reference sample was performed before each measurement to meet calibration criteria.

The changes in the oxidation state of the composite powders are shown in these curves. The detailed X-ray absorption spectroscopy (XAS) analysis is described in supplementary part d. the dominant mechanism of complete oxidation leading to enormous CO2 production. The optimum catalyst, i.e. Cu100/C, retains its oxidation potential for 12 hours, which is not the case at all with Cu200/C. After 12 hours, Cu100/C can still be used as a catalyst for complete oxidation of ethanol, while Cu200/C is better for partial oxidation.

Fig. 1 .

 1 Fig. 1. (a) XRD patterns of Cu-ethanol and CuO-ethanol samples containing Cu, CuO and Cu2O phases. (b) 𝐿𝑜𝑔 𝑃 𝑂 2 -𝑇 plot at 𝑃 𝐶𝑂 = 1 𝑎𝑛𝑑 1 × 10 -10 bar calculated using HSC Chemistry software for the Cu-O-C system. Cu, Cu2O, CuO and CuCO3 are the possible thermodynamically stable phases that can be crystallized in this system. (c) Plot of laser fluence versus diameter (J-D) of Cu-ethanol and CuO-ethanol calculated from Eq. (1). This diagram shows the stable phases in the different sizes of the particles after irradiation with a certain fluence of the laser pulse. (d) Temperature profile of Cu-ethanol and CuO-ethanol systems showing how the temperature of a

  (e) Maximum temperature of particles as a function of size for Cu-ethanol and CuO-ethanol samples. The dashed lines show the transition temperatures. The crystallized phase of each particle is determined from its temperature after laser irradiation. For the calculation of (c), (d) and (f), the data presented in supplementary part b were used. In the diagrams in (c), (d), and (f), the light fill colors, i.e., yellow, green, and turquoise, indicate solid, liquid, and gaseous Cu, respectively, in Cu-ethanol diagrams. Purple, blue, orange and red are the illustrations of solid CuO, solid Cu2O, liquid Cu2O and gaseous Cu in CuO-ethanol diagrams, respectively.

Fig. 2 .

 2 Fig. 2. Raman spectra of (a) Cu-ethanol and (b) CuO-ethanol samples. Each sample was analyzed

Fig. 3 .Fig. 4 .

 34 Fig. 3. Solvent decomposition and formation of new species from ethanol calculated using RBMD for (a) Cu-ethanol system according to RB1 model at 2843 ̊ K, (b) CuO-ethanol system according to RB2 model at 2858 ̊ K. The maximum temperature for each system was chosen based on the data shown in Fig. 1e. Solvent decomposition and formation of new species calculated with RBMD for the Cuethanol system at a sphere temperature of 2843 ̊ K (c) with the RB5 model at a solvent temperature of 1000 ̊ K, and (d) with the RB6 model at a solvent temperature of 298 ̊ K. (e) Timeline of new species formation on the decomposition curves of ethanol for the Cu-ethanol and CuO-ethanol systems according to models RB7 and RB8. The species shown here were selected from thousands of new species according to their higher repetition to show the mechanism of bond breaking/formation in the systems. The evolution of the mechanism for Cu-ethanol is illustrated by (I) ethanol absorption, (II) hydroxyl cleavage, (III) formation of Cu clusters, (IV) surface oxidation, (V) further decomposition of the solvent, and (VI) net oxidation. Also shown is the absorption of ethanol, hydrogen splitting from ethanol, and formation of hydrogenated copper oxide for the CuO-ethanol system. These data were collected using the ChemTraYzer option of the AMS software based on a statistical analysis of all time steps of the simulations. (F) 3D and front snapshots of the sliced box of the MB1 model during RBMD simulation showing diffusion of species during the bond breaking/formation process. The diffusion of oxygen and hydrogen deep into the sphere and the remaining carbon compounds at the surface layer was confirmed by the EDX analysis results. (g) HAADF-EDX Analysis of a Cu2O particle synthesized by laser irradiation of a Cu-ethanol suspension at a laser fluence of 150 mJ/cm 2 .pulse (Cu150 sample). The accumulation of carbon and oxygen on the surface is clearly visible.

Fig. 5 .

 5 Fig. 5. (a) SAED pattern of a Cu200 particle showing the traces of Cu2O3 phase in a multiphase CuO and Cu2O particle. (b) High-resolution XRD pattern of Cu200 sample analyzed at a slow rate of 0.05 /min. It shows a characteristic peak associated with the Cu2O3 (111) plane at 2θ = 27.5. (c) Calculated XRD pattern of a relaxed orthogonal Cu2O3 unit cell using DFT. (d) FFT analysis of a Cu200 particle showing the crystallization of Cu2O3 at the interface of the CuO and Cu2O oxides based on the calculation of the d-spacing. The enrichment of oxygen during the transition between stable copper oxides (I & II) was considered to be the reason for the crystallization of copper (III) in their interface.

Fig. 6 . 1 M

 61 Fig. 6. (a) Cyclic voltammetry of Cu50/C, Cu100/C, Cu200/C, CuO100/C, CuO200/C and CuO400/C electrocatalysts in 0.1 M NaOH, sweep rate (50 mV/s); (b) EOR forward scan of the Cu50/C, Cu100/C, Cu200/C, CuO100/C, CuO200/C and CuO400/C catalysts. All curves were recorded in 0.1 M NaOH + 0.5 M C2H5OH solution at a scan rate of 50 mV/s at room temperature. Differences in the absorbance of peaks originating from CO2, CO, CH3CHO, and CH3COOH were observed during 12 h of EOR for (c) Cu200/C and (d) Cu100/C catalysts. The dynamics of ethanol oxidation mostly shows

Acknowledgements

This work is mostly supported by the Polish National Science Centre Program No. 2018/31/B/ST8/03043. It is also supported partially by the Polish National Science Centre Program No. 2022/06/X/ST3/01743. The computational works were done in cooperation with Prometheus Cluster, Cyfronet, AGH University of Science and Technology, Krakow using Grant No. PLG/2022/015573. The authors would like to thanks Prof. Marta Marszalek, Dr. Michal Kuprinski, and Dr. Arkadiusz Zarzycki for their support during the whole project. We also are thankful of Dr.

Hossein Maleki-Ghaleh due to his scientific consultation for improvement of the scientific relevancy of the current paper. Finally, a special thanks to Prof. Zbigniew Lodziana for accepting to pre-review the paper before submission.