Bart Lomiej Dudek

Pawe L Gawrychowski

Garance Gourdel

Tatiana Starikovskaya

Streaming Regular Expression Membership and Pattern Matching

Regular expression search is a key primitive in myriads of applications, from web scrapping to bioinformatics. A regular expression is a formalism for compactly describing a set of strings, built recursively from single characters using three operators: concatenation, union, and Kleene star. Two basic algorithmic problems concerning such expressions are membership and pattern matching. In the regular expression membership problem, we are given a regular expression R and a string T of length n, and must decide whether T matches R.

In the regular expression pattern matching problem, the task to find the substrings of T that match R.

By now we have a good understanding of the complexity of regular expression membership and pattern matching in the classical setting. However, only some special cases have been considered in the practically relevant streaming setting: dictionary matching and wildcard pattern matching. In the dictionary matching problem, we are given a dictionary of d strings of length at most m and a string T , and must find substrings of T that match one of the dictionary strings. In the wildcard pattern matching problem, we are given a string P of length m that contains d wildcards, where a wildcard is a special symbol that matches any character of the alphabet, and a string T , and must find all substrings of T that match P . Both problems can be solved in the streaming model by a randomised Monte Carlo algorithm that uses O(d log m) space [Golan and Porat (ESA 2017), Golan, Kopelowitz and Porat (Algorithmica 2019)].

In the general case, we cannot hope for a streaming algorithm with space complexity smaller than the length of R for either variant of regular expression search. The main contribution of this paper is that we identify the number of unions and Kleene stars, denoted by d, as the parameter that allows for an efficient streaming algorithm. This parameter has been previously considered in the classical setting, and it has been observed that in practice it is significantly smaller than the length of R. We design general randomised Monte Carlo algorithms for both problems that use O(d 3 polylog n) space in the streaming setting.

A crucial technical ingredient of our algorithms is an adaptation of the general framework for evaluating a circuit with addition and convolution gates in a space-efficient manner [Lokshtanov and Nederlof (STOC 2010), Bringmann (SODA 2017)], initially designed as a key component of a pseudopolynomial time algorithm for the subset sum problem. We show how to replace the Extended Generalised Riemann Hypothesis in [Bringmann (SODA 2017)] by an application of the Bombieri-Vinogradov theorem to achieve the same bounds (but unconditionally), which might be of independent interest.

Introduction

The fundamental notion of regular expressions was introduced back in the 1951 by Kleene [START_REF] Stephen | Representation of events in nerve nets and finite automata[END_REF]. Regular expression search is one of the key primitives in diverse areas of large scale data analysis: computer networks [START_REF] Kumar | Algorithms to accelerate multiple regular expressions matching for deep packet inspection[END_REF], databases and data mining [START_REF] Minos | Mining sequential patterns with regular expression constraints[END_REF][START_REF] Li | Indexing and querying XML data for regular path expressions[END_REF][START_REF] Murata | Extended path expressions of XML[END_REF], human-computer interaction [START_REF] Kin | Proton: multitouch gestures as regular expressions[END_REF], internet traffic analysis [START_REF] Johnson | Monitoring regular zxpressions on outof-order streams[END_REF][START_REF] Yu | Fast and memory-efficient regular expression matching for deep packet inspection[END_REF], protein search [START_REF] Navarro | Fast and simple character classes and bounded gaps pattern matching, with application to protein searching[END_REF], and many others. As such, this primitive is often the main computational bottleneck in these areas and in the pursuit for efficiency has been implemented in many programming languages: Perl, Python, JavaScript, Ruby, AWK, Tcl and Google RE2, to name just a few.

A regular expression R is a sequence containing characters of a specified alphabet Σ and three special symbols (operators): concatenation (•), union (|), and Kleene star ( * ), and it describes a set of strings L(R) on Σ. For example, a regular expression R = (a|b) * c specifies a set of strings L(R) on the alphabet Σ = {a, b, c} such that their last character equals c, and all other characters are equal to a or b. (See formal definition in Section 2). In this work, we consider two classical formalisations of regular expressions search, regular expression membership and pattern matching. In the regular expression membership problem, we are given a string T of length n, and field of streaming algorithms for string processing is relatively recent but, because of its practical interest, quickly developing. It started with a seminal paper of Porat and Porat [START_REF] Porat | Exact and approximate pattern matching in the streaming model[END_REF], who showed streaming algorithms for exact pattern matching and for the k-mismatches problem. This was followed by a series of works on streaming pattern matching [11, 15-17, 35-37, 39, 46, 58, 61], search of repetitions in streams [19-21, 33, 34, 52, 53], and recognising formal languages in streams [START_REF] Babu | Streaming algorithms for language recognition problems[END_REF][START_REF] Bathie | Property testing of regular languages with applications to streaming property testing of visibly pushdown languages[END_REF][START_REF] François | Streaming property testing of visibly pushdown languages[END_REF][START_REF] Ganardi | Automata theory on sliding windows[END_REF][START_REF] Ganardi | Querying regular languages over sliding windows[END_REF][START_REF] Ganardi | Randomized sliding window algorithms for regular languages[END_REF][START_REF] Ganardi | Sliding window algorithms for regular languages[END_REF][START_REF] Ganardi | Sliding window property testing for regular languages[END_REF][START_REF] Ganardi | Sliding windows over context-free languages[END_REF][START_REF] Magniez | Recognizing well-parenthesized expressions in the streaming model[END_REF].

For a general regular expression membership and pattern matching, it is not hard to see that Ω(m) bits of space are required by a reduction from Set Intersection. However, there are at least two interesting special cases of regular expression pattern matching that admit better streaming algorithms. In the dictionary matching, we are given a dictionary of d strings of length at most m over an alphabet Σ and for each position r in T must decide whether there is a position ≤ r such that T [ . . r] matches a dictionary string. A series of work [START_REF] Breslauer | Real-time streaming string-matching[END_REF][START_REF] Clifford | Dictionary matching in a stream[END_REF][START_REF] Shay Golan | Towards optimal approximate streaming pattern matching by matching multiple patterns in multiple streams[END_REF][START_REF] Golan | Real-time streaming multi-pattern search for constant alphabet[END_REF][START_REF] Porat | Exact and approximate pattern matching in the streaming model[END_REF] showed that this problem can be solved by a randomised Monte Carlo algorithm in O(d log m) space and O(log log |Σ|) time per character of the text. In the (d -1)-wildcard pattern matching the expression is R = P 1 (1|2| . . . |σ)P 2 (1|2| . . . |σ) . . . (1|2| . . . |σ)P d , where P i , 1 ≤ i ≤ d are strings of total length at most m over an alphabet Σ = {1, 2, . . . , σ}. Golan, Kopelowitz, and Porat [START_REF] Shay Golan | Streaming pattern matching with d wildcards[END_REF] showed that this problem can be solved by a randomised Monte Carlo algorithm in O(d log m) space and O(d + log m) time per character. The d-wildcard problem is a special case of the k-mismatch problem which asks to compute Hamming distances between a pattern and all its alignments to a text for which the Hamming distance does not exceed the given threshold k. The most space efficient algorithm for the d-mismatch problem is by Clifford, Kociumaka and Porat [START_REF] Clifford | The streaming k-mismatch problem[END_REF] and implies an algorithm that uses O(d log m d ) words of space and spends O(log m d ( √ d log d + log 3 m)) time per character which is also the most efficient for the d-wildcard problem.

In a related work, Ganardi et al. [START_REF] Ganardi | Automata theory on sliding windows[END_REF][START_REF] Ganardi | Querying regular languages over sliding windows[END_REF][START_REF] Ganardi | Randomized sliding window algorithms for regular languages[END_REF][START_REF] Ganardi | Sliding window algorithms for regular languages[END_REF] considered a variant of the regular expression membership problem, where the automaton describing the regular expression has constant size, and one must tell, for each position r of T , whether T [r -+ 1 . . r] ∈ L(R), where is an integer specified in advance ("window" size). As a culmination of their work, they showed that any randomised Monte Carlo algorithm for this variant of the regular expression membership problem takes either constant, or Θ(log log ), or Θ(log ), or Θ( ) bits of space, and provided descriptions of these complexity classes.

This brings the challenge of identifying a structural parameter of a regular expression that determines whether it admits better streaming algorithms. As mentioned earlier, Bille and Thorup [START_REF] Bille | Regular expression matching with multi-strings and intervals[END_REF] observed that in practice the number d of occurrences of the union symbol and Kleene stars is significantly smaller than the size m of the expression R. Furthermore, both the dictionary matching and the wildcard pattern matching can be casted as instances of the regular expression pattern matching, and streaming algorithms with space complexity of the form poly(d, log n) are known. The main goal of this paper is to investigate whether this is also the case for the general regular expression membership and pattern matching.

Our results

We consider the space complexity of regular expression membership and pattern matching in the streaming model of computation. As by now traditional in streaming string processing, we assume that we receive R and n first, preprocess them, and then receive the string T character by character. We do not account neither for the time nor for the space used during the preprocessing stage. In the membership problem, we must output the answer after having read T entirely, whereas in the pattern matching problem we must decide whether there is a substring T [ . . r] ∈ L(R) at the moment when we receive the character T [r].

Our main conceptual contribution is that we identify the small number d of occurrences of the union symbol and Kleene stars in R as allowing for space-efficient streaming algorithms for regular expression membership and pattern matching. More specifically, we design randomised Monte Carlo algorithms that solve both problems using O(d 3 polylog n) space and O(nd 5 polylog n) time per character of the text (Theorem 4.14). While it was known that the value of d determines the space complexity in the two special cases of streaming dictionary matching and wildcard pattern matching, our approach works for any regular expression. We leave it as an open problem to obtain algorithms with poly(d, log n) space complexity and poly(d, log n) time complexity.

On a very high-level, our approach is based on storing carefully chosen subsets of occurrences of the strings appearing in R. As usual in the area, this is easier when the strings are not periodic, that is, any two occurrences of a string S in T must be more than |S|/2 characters apart. Of course, this is not always the case, and the usual remedy is to treat periodic and aperiodic strings separately (more specifically, in streaming pattern matching algorithms one applies this reasoning on every prefix of length being a power of 2). The technical novelty of our algorithms is that we apply this reasoning on O(log n) levels, thus obtaining a hierarchical decomposition of a periodic string. Next, because not all occurrences are stored we need to recover the omitted information. Very informally, we need to decide whether a substring of T sandwiched between two occurrences of strings A 1 , A 2 is a label of some run from A 1 to A 2 in the compact Thompson automaton for R, where the period of the substring is equal to the period of some prefix of length 2 k of one of the strings. The difficulty is that, while the substring has a simple structure, it could be very long, and it is not clear how to implement this computation in a space-efficient manner. We overcome this difficulty by recasting the problem in the language of evaluating a circuit with addition and convolution gates. This technique was introduced by Lokshtanov and Nederlof [START_REF] Lokshtanov | Saving space by algebraization[END_REF] for designing a space-efficient solution for the subset sum problem. Later, Bringmann [START_REF] Bringmann | A near-linear pseudopolynomial time algorithm for subset sum[END_REF] replaced complex numbers with computation modulo a prime number p to obtain a tighter bound on the time and space complexity. In more detail, he designed two solutions, one using the Extended Riemann Hypothesis and the other unconditional but with polynomially higher time and space. We revisit his approach and show that, in fact, one can replace the Extended Riemann Hypothesis by an application of the Bombieri-Vinogradov theorem to achieve the same bounds. We believe that this might be of independent interest. As a consequence of our improvement, we obtain an efficient randomised Monte Carlo algorithm for the following classical problem: given a directed multigraph G with non-negative integer weights on edges, its two nodes v 1 , v 2 , and a number x, decide whether there is a walk from v 1 to v 2 of total weight x. Our algorithm requires x • poly(|G|, log x) time and poly(|G|, log x) space.

The rest of the paper is organised as follows. We first remind the necessary definitions in Section 2, and in Section 3 we give an overview of the main technical ideas we introduced in this paper. We describe the new algorithms for regular expression membership and pattern matching in Section 4.2. Finally, in Section 5 we describe how to replace the Extended Riemann Hypothesis with an application of the Bombieri-Vinogradov theorem in Bringmann's framework and design a space-efficient algorithm for checking if there is a walk of specified weight between two nodes of a directed multigraph.

Preliminaries

We assume an integer alphabet Σ = {1, 2, . . . , σ} with σ characters. A string Y is a sequence of characters numbered from We say that X is a substring of Y if X = Y [i . . j] for some 1 ≤ i ≤ j ≤ n. The fragment Y [i . . j] is called an occurrence of X. We say that an integer p is a period of Y if for each 1

1 to n = |Y |. For 1 ≤ i ≤ n, we denote the i-th character of Y by Y [i]. For 1 ≤ i ≤ j ≤ n, we define Y [i . . j] to be equal to Y [i] . . . Y [j], called a fragment of Y . We call a fragment Y [1] . . . Y [j] a prefix
≤ i ≤ |Y | -p, Y [i] = Y [i + p].
The smallest period of Y is referred to as the period of Y . We say that Y is periodic with period ρ if ρ is the period of Y and ρ ≤ |Y |/2. For the period ρ of Y , we define the string period of Y to be equal to Y [1 . . ρ].

For an integer k, we denote the concatenation of k copies of Y by Y k . We say that a string X is primitive if X = Y k for any string Y = X and any integer k. Note that the string period of a string is always primitive. Definition 2.1. (Regular expression) We define regular expressions over Σ as well as the languages they match recursively. Let L(R) be the language matched by a regular expression R.

• Any a ∈ Σ ∪ {ε} is a regular expression and L(a) = {a}.

For two regular expressions A and B, we can form a new expression using one of the three symbols • (concatenation), | (union), or * (Kleene star):

• A • B is a regular expression and L(A • B) = {XY, for X ∈ L(A)and Y ∈ L(B)}; • A | B is a regular expression and L(A | B) = L(A) ∪ L(B); • A * is a regular expression and L(A * ) = k≥0 {X 1 X 2 . . . X k , where X i ∈ L(A) for 1 ≤ i ≤ k}.
Definition 2.2. (Thompson automaton [START_REF] Thompson | Programming techniques: regular expression search algorithm[END_REF]) For a regular expression R we define the Thompson automaton of R, T (R), recursively. This non-deterministic finite automaton (NFA) accepts all strings s ∈ L(R).

• If R = a ∈ Σ ∪ {ε}, T (R) is constructed as in Figure 1a; 1b. Namely, the initial state of T (A) becomes the initial state of T (R), the final state of T (A) becomes the initial state of T (B), and the final state of T (B) becomes the final state of T (R);

• If R = A • B, T (R) is constructed as in Figure
• If R = A|B, T (R) is constructed as in Figure 1c. Namely, the initial state of T (R) goes via ε-transitions both to the initial state of T (A) and to the initial state of T (B), and the final states of T (A) and T (B) go via ε-transitions to the final state of T (R); 1d. Namely, the initial state of T (R) and the final state of T (A) go via ε-transitions both to the initial state of T (A), and to the final state of T (R). We note that in general the size of a regular expression is much smaller than the total number of characters in it and is bounded by twice the number of union and Kleene star symbols plus two. The size of a regular expression measures its "complexity".

• If R = A * , T (R) is constructed as in Figure
i start f a (a) T (A) for a ∈ Σ ∪ {ε} i start f T (A) T (B) (b) T (A • B) i start f ε ε ε ε T (A) T (B) (c) T (A|B) i start f ε ε ε ε T (A) (d) T (A * )
Figure 1: Thompson automaton. In each automaton, i and f are the initial and final states, respectively.

i start f ε ε ε ε ε ε b a b b a b ε ε (a) T (b(ab|b) * ab) i start f ε ε ε ε ε ε b ab b ab ε ε (b) TC (b(ab|b) * ab)
≤ i ≤ j ≤ |S|, is an occurrence of a regular expression R, if S[i . . j] ∈ L(R)
, or in other words if there is a walk from the initial state of T C (R) to the final state of T C (R) such that the concatenation of the labels of the transitions in this walk equals S[i . . j].

We will also need a notion of a partial occurrence of R. Intuitively, S[i . . j] is a partial occurrence of R if it is a prefix of a string in L(R), but we will need a more precise definition. Definition 2.5. (Partial occurrence of a regular expression) We say that a fragment S[i . . j] of a string S, where 1 ≤ i ≤ j ≤ |S|, is a partial occurrence of a regular expression R ending with a prefix P of an atomic string A, if there is a walk from the initial state of T C (R) to the endpoint of the transition corresponding to A such that the concatenation of the labels of the transitions in this walk equals

S[i . . j]A[|P | + 1 . .].

Technical Overview

In this section, we give an overview of the main technical ideas we introduced in this paper. Statement of the problems and the model of computation. Let us start by giving the precise formulation of the regular expression membership and pattern matching problems and reminding the definition of the streaming model of computation.

Regular expression membership and pattern matching

Given a string T of length n over an alphabet Σ = {1, 2, . . . , σ}, where σ = n O (1) , and a regular expression R over Σ of size d. In the regular expression membership problem, we must decide whether T ∈ L(R). In the regular expression pattern matching problem, we must find all positions 1 ≤ r ≤ n, such that there exists a position 1

≤ ≤ r such that T [ . . r] ∈ L(R).
We work in the streaming model of computation. As it is now standard in the streaming string processing algorithms, we assume to receive n and R first. We do not account neither for the time nor for the space we need to preprocess R. After having preprocessed R, we receive T as a stream, character by character. At the moment we receive the first character of T , the main phase of the algorithm starts. During the main phase, we account for all the space and time used. Definitions and tools. Let A 1 , A 2 , . . . , A d be the atomic strings of the regular expression R. We define

Π = {A i [1 . . min{2 j , |A i |}] : 1 ≤ i ≤ d, 0 ≤ j ≤ log |A i | }. The prefixes of A i 's that belong to Π are called canonical.
We can assume that all atomic strings have length at most n, otherwise they never appear in the text and we can ignore them. Formally, during the preprocessing phase we delete all transitions (u, v) from T C (R) that are labelled by atomic strings of lengths larger than n. We also assume that d ≤ n, otherwise we can use the following solution: Claim 3.1. Given a streaming text T of length n and a regular expression of size d ≥ n. Assume that all atomic strings have length at most n each. There is a deterministic algorithm that solves the membership and the pattern matching problems for T and R in O(d 2 ) space and O(d 3 ) time per character of T .

Proof. First note that we can afford storing T in full. Second, we build a compact trie on the reverses of the atomic strings of R. The trie occupies O(dn) = O(d 2 ) space. Finally, let F contain all atomic strings A such that there is an ε-transitions path from the endpoint of the transition labelled by A to the final state of T C (R).

Define an array D of length n + 1 = O(d) such that D[0] contains a singleton set consisting of the starting state of T C (R) and D[r], 1 ≤ r ≤ n, stores all states u such that u is the end of some transition labelled by an atomic string and T [1 . . r] equals the concatenation of the labels of the transitions in some walk from the starting state of T C (R) to u. Assume that we have constructed D[1 . . r]. To compute D[r + 1], we use the trie to find the atomic strings

A 1 , A 2 , . . . , A q equal to D[1 . . r + 1], D[2 . . r + 1], . . . or D[r + 1] in O(r + q) time. Note that q ≤ d. For each atomic string A i , 1 ≤ i ≤ q, labelling a transition (v, w), we add w to D[r + 1] if there is a state u in D[r + 1 -|A i |]
such that there is an ε-transition path from u to v, which can be checked in O(d) time and space. In total, the algorithm spends O(d 3 ) time to process a character of T (q = O(d), and for each 1

≤ i ≤ q the set D[r + 1 -|A i |] contains O(d) states). The algorithm reports that T ∈ L(R) if D[n] contains a state v,
which is an endpoint of a transition labelled by some A ∈ F.

In the regular expression pattern matching problem, we define an array D in the following way. As before, D[0] contains a singleton set consisting of the starting state of T C (R). For every 1 ≤ r ≤ n, D[r] stores the starting state of T C (R) and all states u such that u is the end of some transition labelled by an atomic string and T [ . . r], for some ≤ r, equals the concatenation of the labels of the edges in some walk from the starting state of T C (R) to u. Assume that we have constructed D[1 . . r]. To compute D[r + 1], we use the trie to find the atomic strings A 1 , A 2 , . . . , A q equal to D

[1 . . r + 1], D[2 . . r + 1], . . . or D[r + 1] in O(r + q) = O(d) time. For each atomic string A i , 1 ≤ i ≤ q, labelling a transition (v, w), we add w to D[r + 1] if there is a state u in D[r + 1 -|A i |]
such that there is an ε-transition path from u to v, which can be checked in O(d) time and space. In total, the algorithm spends O(d3 ) time to process a character of T . We report all positions r such that D[r] contains a state v, which is an endpoint of a transition labelled by some A ∈ F.

From now on, we assume that all atomic strings have length at most n, and that d ≤ n. For a string P and a text T , denote by occ(P, T ) the set of the ending positions of the occurrences of P in T . Our solutions for streaming regular expression membership and pattern matching are very similar, the main difference is how we define a witness: Definition 3.2. (Witness (Membership)) Let P be a canonical prefix of an atomic string, and r ∈ occ(P, T ). We say that r is a witness if T [1 . . r] is a partial occurrence of R ending with P . Definition 3.3. (Witness (Pattern matching)) Let P be a canonical prefix of an atomic string, and r ∈ occ(P, T ). We say that r is a witness if there exists a position 1 ≤ ≤ r such that T [ . . r] is a partial occurrence of R ending with P .

We exploit the following algorithm, which we refer to as the pattern matching algorithm2 : Theorem 3.4. (cf. [57, Theorem 2]) Given a pattern of length at most n and a text T of length n over an alphabet of size n O (1) . There exists a randomised Monte Carlo streaming algorithm that uses O(log n) space and O(log n) time per character of the text. When it receives T [i], it says whether i ∈ occ(P, T ). The algorithm is correct with high probability. 3 We also make use of the following well-known fact: Fact 3.5. (Fine and Wilf's periodicity lemma [START_REF] Fine | Uniqueness theorems for periodic functions[END_REF]) If a string X has two periods of length p and q and p + q ≤ |X|, then X also has a period of length gcd(p, q). Intuition: non-periodic case. To give intuition behind our solutions, consider a very simple case when every canonical prefix is not periodic. We start with the following simple observation: Observation 3.6. By Fact 3.5, if P is not periodic, there can be at most two occurrences of P in a string of length ≤ 2|P |.

Therefore, if none of the strings in Π is periodic, we can use the following approach. For each P ∈ Π and T , we run the pattern matching algorithm and at any moment store the two most recent witnesses for P discovered by the algorithm (for membership, witness are defined as in Definition 3.2, and for pattern matching as in Definition 3.3). When the algorithm discovers a new position r ∈ occ(P, T ), we must decide whether it is a witness. Let P = A[1 . . min{2 k , |A|}], where A is an atomic string.

If k = 0, we consider the starting node u of the transition in the compact Thompson automaton T C (R) labelled by A. Suppose that there is an ε-transitions path from the endpoints of the transitions labelled by atomic strings A i1 , A i2 , . . . , A ij to u. We then check if (r -1) is a witness for at least one of A i1 , A i2 , . . . , A ij . If it is, then r is a witness. Importantly, if r -1 is a witness for A i j , 1 ≤ j ≤ j, it is the most recent one and is stored in the memory of the instance of the pattern matching algorithm for A i j and T . Suppose now that k ≥ 1. We then must check whether (r -2 k-1 ) is a witness for A[1 . . 2 k-1 ]. If it is, then r is a witness for P . Note that by Observation 3.6, if (r -2 k-1 ) is a witness for A[1 . . 2 k-1 ], it is one of the two most recent ones and will be stored by the pattern matching algorithm for A[1 . .

2 k-1 ].
Let F contain all atomic strings A such that there is an ε-transitions path from the endpoint of the transition labelled by A to the final state of T C (R). In the regular expression pattern matching problem, we report all positions r such that r is a witness in occ(A, T ) for some A ∈ F. In the regular expression membership problem, T ∈ L(R) if n is a witness for occ(A, T ), for some A ∈ F.

We do not provide the formal analysis of the algorithm, as we only give it for intuition, but it is easy to see that it uses O(d 2 log 2 n) space and O(d log 2 n) time per character of the text (recall that we do not account for the time spent during the preprocessing phase). As all atomic strings have length at most n and d ≤ n, the algorithm is correct with high probability by Theorem 3.4. General case: main technical contributions. In general, unfortunately, some of the canonical prefixes are periodic we can no longer use Observation 3.6. However, the following generalisation holds: Observation 3.7. By Fact 3.5, if for a string P and a string X, X ≤ 2|P |, we have |occ(P, X)| > 2, then P is periodic and the set occ(P, X) can be represented as an arithmetic progression with difference ρ, where ρ is the period of P . 4Observation 3.7 gives the idea behind our approach for the general case. By this observation, we obtain that every r ∈ occ(P, T ), where P is a canonical prefix of some atomic string periodic with period ρ, belongs to a fragment of form (∆(P )) k , where ∆(P ) = P [|P | -ρ + 1 . .] and k is an integer. Instead of storing the last two witnesses for each canonical prefix, we would like to store the witnesses in the last two fragments of form (∆(P )) k . However, the number of such witnesses can be large. Our main technical novelty is a compressed representation of such witnesses. We give a high-level overview of the approach we use for the membership problem, our solution to the regular expression pattern matching problem is similar. We show that for each fragment of form (∆(P )) k it suffices to store a small, carefully selected subset of witnesses that belong to this fragment. The remaining ones can be restored in small space at request. Consider a witness r ∈ occ(P, T ), where P ∈ Π. By definition, there is a partition

T [1 . . r] = T [ 1 . . r 1 ]T [ 2 . . r 2 ] . . . T [ m . . r m ]
such that each fragment in the partition, except for the last one, is an atomic string, and the last one equals P . Furthermore, by Observation 3.7, r must belong to some fragment

F = T [i . . i + kρ -1] = (∆(P )) k . Let m be the index of the first fragment such that r m ≥ i. Consider the fragment W = T [ m . . r m ], m ≤ m ≤ m,
containing a position i + 2ρ -1 (we call this position an "anchor"). Note that W is a canonical prefix of some atomic string and r m ∈ occ(W, T ) is a witness. If there are a few witnesses t ∈ occ(W, T ) such that T [t -|W | + 1, t] contains the anchor i + 2ρ -1, we can store them explicitly. Otherwise, there is a periodic fragment containing i + 2ρ -1, and we can recurse for it by choosing a new anchor close to its starting point. We choose the definition of anchors (see Section 4.1) so that the recursion stops in a logarithmic number of steps and for some of the anchors there is a witness that we store explicitly for this anchor.

To summarize, the idea of the compact representation of witnesses that belong to a fragment of form (∆(P )) k is to choose a logarithmic set of anchors close to the starting point of the fragment, and for each of these anchors to store a constant number of witnesses for each canonical prefix in Π. Suppose now that r ∈ occ(P, T ), where P is a canonical prefix of an atomic string A, r belongs to a fragment F = T [i . . i + kρ -1] = (∆(P )) k . To decide whether it is a witness we use the following approach. From above we know that r is a witness iff there is a witness r ∈ occ(A , T ), where A is an atomic string, that we store in the compact representation of witness in F , and there is a path in T C (R) from the ending node of the transition labelled by A and to the starting node of the transition labelled by A such that the concatenation of the strings on the edges of the path equals T [r +1 . . r-|A|] (which is a substring of (∆(P )) k ). Unfortunately, it is not clear how to verify this condition in a straightforward way as we do not have random access neither to ∆(P ), nor to the strings on the edges of T C (R). Instead, using anchors again, we show that verifying this condition can be reduced to the following question, where G is a graph of size poly(d, log n) (see Lemma 4.12 for details):

Walks in a weighted graph Given a directed multigraph G with non-negative integer weights on edges, two nodes and a number x, decide if there is a walk from the first node to the second one of total weight x.

Walks in a weighted graph and circuits. In Section 5, we show the following theorem: Theorem 3.8. There exists an algorithm which, given a directed multigraph G with non-negative integer weights on edges, its two nodes v 1 and v 2 and a number x, decides if there is a walk from v Let N = |V (G)|. For the simpler case when the graph is unweighted, we could use a folklore approach and compute the x-th power of the adjacency matrix in O(N 3 log x) time and O(N 2 ) space. In order to handle arbitrary weights of edges, we compute the arrays C k of bit-vectors of length x + 1, where C k [u, v][d] stores a bit indicator of whether there exists a walk from u to v in G of at most 2 k edges of total weight exactly d. The following formula holds:

C k [u, v][d] = w∈V (G) i∈{0,...,d} C k-1 [u, w][i] ∧ C k-1 [w, v][d -i]
Using the fast Fourier transform to compute the convolutions, we obtain an algorithm with time O(N 3 x log 2 x) and space O(N 2 x).

In our application, x can be equal to n, and the approach above uses Ω(n) space, which is prohibitive. In order to improve the space complexity, we represent the above computations as a circuit with binary Or and Convolution x gates operating on bit-vectors of length x + 1. Every element C k [u, v] requires a separate gate and while computing its value we need to perform N convolutions, for every possible intermediate node w, so in total there are O(N 3 log x) gates. The Convolution x gates store only the first x + 1 bits of the results, as we never need paths of total weight larger than x. We are interested only in a single bit of output of the circuit, namely

C log x [v 1 , v 2 ][x].
If there were only Or gates in the circuit, we could store only the x-th element at each gate. In order to handle also Convolution x gates, we use the discrete Fourier transform over a suitably chosen ring.

We use the technique introduced by Lokshtanov and Nederlof [START_REF] Lokshtanov | Saving space by algebraization[END_REF] and then modified Bringmann [START_REF] Bringmann | A near-linear pseudopolynomial time algorithm for subset sum[END_REF] to work with numbers modulo p instead of complex numbers. Informally, they show that if we operate on Z t p (vectors of length t with elements in Z p for suitably chosen p and t) instead of the bit-vectors, we can compute out(C)[x], the x-th element of the output of the circuit C in O(|C|t polylog p) time and O(|C| log p) space (see details in Theorem 5.1). However, there are technical difficulties that we need to overcome to apply their technique to our solution. The approach of Bringmann [START_REF] Bringmann | A near-linear pseudopolynomial time algorithm for subset sum[END_REF] requires that t > x and Z p contains a t-th root of the unity. The main difficulty is to choose these numbers as small as possible as they directly affect the complexity of the algorithm. This question was also faced by Bringmann [START_REF] Bringmann | A near-linear pseudopolynomial time algorithm for subset sum[END_REF], who showed two variants of the framework, one using the Extended Riemann Hypothesis and the other unconditional but with polynomially higher time and space, which is not good enough for our streaming application. By using Bombieri-Vinogradov theorem (see details in Theorem 5.6) and facts about counting primes in arithmetic progressions, we obtain an unconditional time bound comparable to that of Bringmann that assumes the Extended Riemann Hypothesis.

Regular Expression Membership and Pattern Matching

In this section, we address the problems of regular expression membership and pattern matching in the streaming model of computation. In Section 4.1, we introduce a notion of anchors that is the key to achieving the desired space complexity. In Section 4.2, we describe the algorithms.

Anchors

In this section we define the notion of anchors that will allow us to store all occurrences (partial or not) of regular expressions detected by the algorithm efficiently. Definition 4.1. (Anchors) Consider a periodic string W with period ρ. Set the anchor a 0 = 2ρ and the period ρ 0 = ρ. Suppose that (a r , ρ r ) q-1 r=0 are defined. We define (a q , ρ q ) recursively. Consider the set S of fragments W [i . . j] of W satisfying the following properties:

1. W [i . . j] contains a q-1 and is periodic with period π < ρ q-1 ; 2. i + 4π -1 ≤ a q-1 (there are at least four repetitions of the string period of W [i . . j] before a q-1 ); 3. a q-1 ≤ j -4π -r, where r = (j -i + 1) (mod π) (there are at least four repetitions of the string period of W [i . . j] after a q-1 ).

Let i q = min{i : W [i . . j] ∈ S} and j q = max{j : W [i q . . j] ∈ S}. If W [i q . . j q ] is undefined, recursion stops. Otherwise, ρ q is defined to be the period of W [i q . . j q ] and a q := i q + 2ρ q -1.

Let A(W ) = {a 0 , a 1 , . . . , a Q }, where (a Q , ρ Q ) is the last defined anchor-period pair. We call A the generator

set of anchors of W . Define A * (W ) = ∆∈Z+ (A(W ) + ∆ • ρ) ∩ [1, |W | -2ρ].
We refer to A * simply as the set of anchors of W . For an illustration, see Fig. 3. Proof. Let A(W ) = {a 0 , a 1 , . . . , a Q }. For each 0 ≤ q ≤ Q, let W [i q . . j q ] be the fragment associated with a q , and ρ q be its period. (In particular, for q = 0 we have i 0 = 1, j 0 = |W |, ρ 0 = ρ.) We show that for each 1 ≤ q ≤ Q we have |W [i q . . j q ]| ≤ 2ρ q-1 . This implies, in particular, that |W [i q . . a q-1 ]| ≤ 2ρ q-1 and therefore ρ q ≤ ρ q-1 /2. The lemma follows immediately.

W ρ 0 = ρ a 0 i 2 ρ1 ρ2 i 1 j 1 a 1 j 2 a 2
Fix 0 ≤ q ≤ Q. Assume by contradiction that |W [i q . . j q ]| > 2ρ q-1 . We then have that W [i q . . j q ] has periods ρ q-1 and ρ q and ρ q-1 + ρ q < |W [i q . . j q ]|. Hence, W [i q . . j q ] is periodic with period π = gcd(ρ q-1 , ρ q ) by Fact 3.5. The substring W [i q . . j q ] contains a full copy of W [i q-1 . . i q-1 + ρ q-1 -1]. Therefore, W [i q-1 . . i q-1 + ρ q-1 -1] has a period π, which implies that it equals (W [i q-1 . . i q-1 + π -1]) ρq-1/π , i.e. the string period of W [i q-1 . . j q-1 ] is not primitive, a contradiction. Definition 4.3. Let W be a periodic string with period ρ. We say that a fragment F = W [i . . j] is anchored by an anchor a ∈ A * (W ) if i ≤ a ≤ j and for any strings

U ∈ Σ * , V ∈ Σ ρ such that V = W [1 . . ρ] there are at most eight occurrences of F in U V (W [1 . . j])
. r] = W [ 1 . . r 1 ]W [ 2 . . r 2 ] . . . W [ k . . r k ]. (a) There exists 1 ≤ k ≤ k such that W [ k . . r k ] is anchored by an anchor a ∈ A * (W ) ∩ [r -4ρ + 1, r]. (b) If, in addition, 1 ≤ ≤ 2ρ, there exists 1 ≤ k ≤ k such that W [ k . . r k ] is anchored by an anchor a ∈ A * (W ) ∩ [1, 4ρ].
Proof. The high-level idea of the proof of (a) and (b) is as follows. Let A(W ) = {a 0 , a 1 , . . . a Q }. For every 0 ≤ q ≤ Q and an integer ∆ > 0 to be determined later, define a ∆ q := a q + ∆ • ρ. Let F q = W [ kq , r kq ] be the fragment that contains a ∆ q . We show that either F q is anchored by a ∆ q or q < Q, which yields the lemma. We exploit two auxiliary claims: Claim 4.5. Let π be the period of F q , 0 ≤ q ≤ Q. If F q is not anchored by a ∆ q , then there exist

U ∈ Σ * , V ∈ Σ ρ with V = W [1 .
. ρ] such that there is a fragment S[p . . t] of the string S = U V (W [. . r q ]) satisfying the following properties:

1. p ≤ |U | + |V | + a ∆
q ≤ t (the fragment contains the anchor); 2. S[p . . t] is periodic with period π;

3. p + 7 • π ≤ |U | + |V | + a ∆
q (there are at least seven repetitions of the string period of the fragment before the anchor);

4. |U | + |V | + a ∆ q ≤ t -6π -r
, where r = t -p + 1 (mod π) (there are at least six repetitions of the string period of the fragment after the anchor).

Proof. Let U ∈ Σ * , V ∈ Σ ρ with V = W [1 .
. ρ] such that there are least eight occurrences of

F q in S = U V (W [1 . . r q ]) containing a := |U | + |V | + a ∆ q . Let the last eight occurrences be S[p k . . t k ], 1 ≤ k ≤ 8.
As all occurrences contain a, the length of S[p 1 . . t 8 ] is at most 2|F q |. By Observation 3.7, we obtain that S[p 1 . . t 8 ] is periodic with period π, p k = p 1 + (k -1)π, and

t k = t 1 + (k -1)π. As p 8 = p 1 + 7π ≤ a, we have S[p 1 . . a] ≥ 7π. On the other hand, t 2 -r + 1 ≥ t 1 + 1 ≥ a + 1. Therefore, |S[a + 1 . . t 8 -r]| ≥ |S[t 2 -r + 1 . . t 8 -r]| ≥ 6π
. By taking p = p 1 and t = t 8 , we obtain the claim. For an illustration, see Fig. 4. Claim 4.6. Assume that q ≥ 0 and that the period of F q is π < ρ q . If F q is not anchored by a ∆ q , then q < Q.

U V W [. . r kq ] t a π F q p
Proof. By Claim 4.5, there exist

U ∈ Σ * , V ∈ Σ ρ with V = W [1 .
. ρ] such that there is a fragment S[p . . t] of the string S = U V (W [. . r q ]) periodic with period π that contains a := |U | + |V | + a ∆ q and such that there are at least six repetitions of the string period before and after a.

Let us show that a -2ρ q + 1 ≤ p < t ≤ a + 2ρ q . Suppose by contradiction that p < a -2ρ q + 1. We have that S[a -2ρ q + 1 . . a] = W [a ∆ q -2ρ q + 1 . . a ∆ q ] (note that by definition a ∆ q ≥ 2ρ q for any ∆). Furthermore, W [a ∆ q -2ρ q + 1 . . a ∆ q ] has periods ρ q (by definition of i q and a ∆ q ) and π (by the assumption). By Fact 3.5, W [a ∆ q -2ρ q + 1 . . a ∆ q ] has a period gcd(ρ q , π) < ρ q . As W [a ∆ q -2ρ q + 1 . . a ∆ q ] contains a full copy of the string period of W [i q . . j q ], we obtain that it is not primitive, a contradiction. (See Fig. 5). To show that t ≤ a+2ρ q , note that S[a+1 . .

a+2ρ q ] = W [a ∆ q +1 . . a ∆ q +2ρ q ], a ∆ 0 +2ρ ≤ |W | and, for q ≥ 1, a ∆ q +2ρ q ≤ a ∆ q-1
by definition of i q and a q . Therefore, for all q ≥ 0, W [a ∆ q + 1 . . a ∆ q + 2ρ q ] is periodic with period ρ q . The rest of the argument is analogous.

From a -2ρ q + 1 ≤ p < t ≤ a + 2ρ q and the fact that S[p . . t] contains at least six repetitions of its string period before and after a, we obtain that i q+1 , j q+1 and hence a q+1 , ρ q+1 are well-defined, which completes the proof of the claim.

We are now ready to show (a) and (b).

(a) Let ∆ ≤ |W |/ρ -2 be the smallest integer such that a 0 + ∆ • ρ ≥ r -4ρ. Note that ∆ is welldefined. Consider an anchor

a ∆ 0 = a 0 + ∆ • ρ ∈ A * (W ) ∩ [r -4ρ + 1, r]. Let F 0 = W [ k0 .
. r k0 ] be the fragment that contains a ∆ 0 and π be its period. If F 0 is anchored by a ∆ 0 , we are done. Otherwise, by Claim 4.5, there exist U ∈ Σ * , V ∈ Σ ρ with V = W [1 . . ρ] such that there is a fragment S[p . . t] of the string S = U V (W [. . r k0 ]) periodic with period π that contains a := |U | + |V | + a ∆ 0 and such that there are at least six repetitions of the string period of F 0 before and after a. As we have r k0 -a ∆ 0 +1 ≤ r-a ∆ 0 +1 ≤ 4ρ, there is π ≤ 2ρ/3. It follows that i 1 , j 1 and hence a 1 , ρ 1 are well-defined, i.e. 0 < Q. W [a -2ρ q + 1, a] has period gcd(π, ρ q ) < ρ q a -2ρ q + 1 Figure 5: Illustration of the proof of Claim 4.6, case p < a -2ρ q + 1.

We now show that for arbitrary q ≥ 1 either a ∆ q = a q + ∆ • ρ anchors F q or the period π of F q is smaller than ρ q , which by Claim 4.6 implies that q < Q. By our choice of ∆, F q is well-defined. If F q is anchored by a ∆ q , we are done. Otherwise, by Claim 4.5, there exist q . Recall that a ∆ q = (i q + 2ρ q ) + ∆ • ρ. First, we have that π = ρ q , otherwise we could have extended W [i q . . j q ] to the left. Second, let us show that the case π > ρ q is impossible. Suppose otherwise. If

U ∈ Σ * , V ∈ Σ ρ with V = W [1 . . ρ] such
t -4π + 1 ≤ |U | + |V | + a ∆ q-1 , then W [a ∆ q + 1 . . a ∆ q-1
] contains a copy of S[1 . . 2π], and therefore S[1 . . 2π] has a period ρ q . By Fact 3.5, the string period S[1 . . π] of S is not primitive, a contradiction. (See Fig. 6a

.) Otherwise, |U | + |V | + a ∆ q-1 is contained in S[p .
. t], which has period π > ρ q-1 . In addition, there are at least four repetitions of the string period of S[p . . t] before and after

|U | + |V | + a ∆ q-1 , and p < |U | + |V | + a ∆ q -2ρ q ≤ |U | + |V | + i q , a
contradiction with the choice of W [i q . . j q ]. (See Fig. 6b.) It finally follows that π < ρ q and therefore by Claim 4.6, q < Q. (b) Let ∆ be the smallest integer such that a 0 + (∆ -2)ρ ≥ (note that ∆ = 1, 2). Consider an anchor a ∆ 0 = a 0 + ∆ • ρ ∈ A * (W ) ∩ [1, 4ρ]. We first show that either F 0 is caught by a ∆ 0 , or 0 < Q.

U V W [. . r kq ] a ∆ q-1 t a ∆ q π ρ q Contradicts primitivity of S[1 . . π] Subcase t -4π + 1 ≤ |U | + |V | + a ∆ q-1 . U V W [. . r kq ] a ∆ q-1 t a ∆ q π ρ q p i q + |U | + |V | Contradicts minimality of i q Subcase t -4π + 1 ≥ |U | + |V | + a ∆ q-1 .
If F 0 is anchored by a ∆ 0 , we are done. Otherwise, let π be the period of F 0 . We claim that π < ρ = ρ 0 . As F 0 is not anchored, by Claim 4.5 there exist U ∈ Σ * , V ∈ Σ ρ with V = W [1 . . ρ] such that there is a fragment S[p . . t] of the string S = U V (W [. . r k0 ]) periodic with period π that contains a := |U | + |V | + a ∆ 0 and such that there are at least six repetitions of the string period of S before and after a. We can immediately rule out the case π = ρ as a ≤ 4ρ and V = W . 2π] has a period gcd(π, ρ), and therefore the string period of S is not primitive, a contradiction. For q ≥ 1, F q is well-defined by our choice of ∆. The rest of the argument repeats the argument in the proof of (a). This concludes the proof of Lemma 4.4.

Algorithms

In this section, we give a description of our new streaming algorithms for regular expression membership and pattern matching. The structure of the algorithms is very similar, the main difference is how we define a witness (see Definitions 3.2 and 3.3). For this reason, we describe the algorithms in parallel. Recall that T is a string of length n over an alphabet Σ = {1, 2, . . . , σ}, where σ = n O (1) , and A 1 , A 2 , . . . , A d are the atomic strings for the regular expression R. Recall also that Π is the set of canonical prefixes of the atomic strings, defined as Π

= {A i [1 . . min{2 j , |A i |}] : 1 ≤ i ≤ d, 0 ≤ j ≤ log |A i | }.
We make use of the following corollary of Fact 3.5:

For Bringmann's framework to be efficient, one must provide a method to choose p and ω. Bringmann [START_REF] Bringmann | A near-linear pseudopolynomial time algorithm for subset sum[END_REF] showed two different methods, one requiring the Extended Riemann Hypothesis and the other one resulting in an additional t ε factor in both time and space [START_REF] Bringmann | A near-linear pseudopolynomial time algorithm for subset sum[END_REF]Lemma 4.4]. Below we show that one can achieve the bounds of the former method unconditionally.

Finding primes

The goal of this section is to prove the following theorem: Theorem 5.2. There is a procedure that, given y, finds in O(y polylog y) arithmetic operations and O(log y) space a prime p and ω such that for every N ≤ 2 O(y log y) , with probability at least 1/2 the following holds:

1. ω is a t-th primitive root of unity in Z p , for some t satisfying y ≤ t = O(y polylog y);

2. p = O(y 2 polylog y); 3. p N .
Let B be a constant to be determined later. To compute numbers p and ω we run the following procedure:

1. Set x to be the smallest number such that 1 2

√

x log -B x ≥ y (using binary search);

2. Choose a random q ∈ [ 1 2 , 1] • √ x log -B x;
3. Find a prime p such that p ≤ x and p ≡ 1 mod q (by guessing candidate p and checking all numbers up to √ p if they divide p or not);

4. Find a generator g of Z * p (by guessing candidate g and checking if g p-1 p ≡ 1 mod p for all prime divisors p of p -1); 5. Set t = q and ω = g is well-defined. As g is a generator, we have that ω is a t-th primitive root of unity in Z * p . By the choice of x and p, we have p ≤ x = O(y 2 polylog y) and hence y ≤ q = t = O(y polylog y). In the following lemma we show that with probability at least 7/8, there are many primes p satisfying p ≤ x and p ≡ 1 mod q and hence we can efficiently find one. Finally, we show how to find the generator g efficiently. Let π(x; q, a) = |{p ≤ x : p ≡ a (mod q)}| and φ(n) = |{1 ≤ a ≤ n : gcd(a, n) = 1}|. Lemma 5.3. Let q be chosen uniformly at random from

[ 1 2 , 1] • √ x log -B x.
With probability at least 7/8 we have π(x; q, 1) = Ω( √ x(log x) B-1 ).

Before we prove the lemma, we remind some number-theory notation and facts related to counting primes. The reader familiar with this area can skip this part. We first remind the definitions of von Mangoldt function Λ(n) and Chebyshev functions ψ and ϑ:

ψ(x; q, a) = n≤x n≡a (mod q) Λ(n),
where Λ(n) = log p if n = p k for some prime p and k ∈ Z + , 0 otherwise. ϑ(x; q, a) = p≤x p≡a (mod q) log p, where the summation is over prime numbers p.

By skipping the last two arguments we denote ϑ(x) = 0≤a<q ϑ(x; q, a) and similarly for ψ(x).

Fact 5.4. (By definition) ϑ(x; q, a) ≤ π(x; q, a) • log x. Proof. Theorem 13 of [START_REF] Barkley | Approximate formulas for some functions of prime numbers[END_REF] states that ψ(x) -ϑ(x) = O( √ x), so for completeness we show an adaptation of this property to numbers forming an arithmetic progression. ψ(x; q, a) -ϑ(x; q, a) Theorem 5.6. (Bombieri-Vinogradov theorem [START_REF] Bombieri | Le grand crible dans la théorie analytique des nombres[END_REF]) For every A > 0 there exists B = B(A) > 0 such that for every x:

= n≤x n≡a mod q n=p k ,k≥1 log p - p≤x p≡a mod q log p ≤ n≤x n=p 2 log p + n≤x n=p k ,k≥3 log p ≤ ϑ( √ x) + O( 3 √ x log 2 x) = O( √ x) as n≤x n=p 2 log p = p≤ √ x log p = ϑ( √
q≤ √ x(log x) -B max y≤x max gcd(a,q)=1 ψ(y; q, a) - y φ(q) = O(x log -A x).
With all the notation at hand we are ready to prove Lemma 5.3.

Proof.

[Proof of Lemma 5.3] Let R = [ 1 2 , 1]• √ x log -B
x be the range from which we draw q. By choosing y = x and a = 1 and summing only over q ∈ R we lower bound the left-hand side of Bombieri-Vinogradov theorem obtaining that, for every A > 0 there exists B = B(A) > 0 such that (5.1) q∈R ψ(x; q, 1) -x φ(q)

= O(x log -A x).

Similarly to Markov's inequality, for q chosen uniformly at random from R we have with probability at least 7/8:

(5.2) ψ(x; q, 1) -x φ(q)

= O( √ x(log x) -A+B ) Indeed, there can be at most |R|/8 numbers q in R such that ψ(x; q, 1) ≥ 8•Ω(x log -A x)

|R|

= Ω( √ x(log x) -A+B ) in order not to exceed the right-hand side of (5.1). Let B be the constant from Theorem 5.6 for A = 1. Without loss of generality, we assume B ≥ 3 > A = 1. Now we rewrite (5.2) using properties of φ(n), ϑ(n) and ψ(n) and obtain: π(x; q, 1) = Ω( √ x(log x) B-1 )

In more detail: x φ(q) -ψ(x; q, 1) = O( √ x(log x) -A+B ) from (5.2)

x q ≤ ϑ(x; q, 1) + O( √ x) + O( √ x(log x) -A+B ) from Fact 5.5 and φ(q) ≤ q x q ≤ π(x; q, 1) • log x + O( √ x(log x) -A+B ) from Fact 5.4 and B > A π(x; q, 1) ≥ √ x(log x) B-1 -O( √ x(log x) -A+B-1 ) as q ∈ R π(x; q, 1) = Ω( √ x(log x) B-1 ) as A = 1

Hence, the appropriate choice of y = Θ(x) guarantees that no convolution gate overflows. Now we estimate the size of the constructed circuit. We compute r = O(log 2 x) arrays D k . For each of them we process O(r 3 ) k-good triples which perform two products each.

f (k) ≤ k-good k1,k2,k3 f (k 1 ) • (y • g) 2 • f (k 3 ) ≤ k 3 (y • g) 2 • f 2 (k max ) ≤ W f 2 (k max )
where k max is the largest possible value of k i that can be a part of a k-good triple and W = r 3 • (y • g) 2 = O(x 5 ) as y = O(x) and we consider the case when x = Ω(g). From Equation (5.4) we have:

2 • (1 + ε) kmax-1 < (1 + ε) k k max + log 1+ε 2 -1 < k
As arguments of f are integers, it would be more convenient to write k max ≤ k -c where c = log 1+ε 2 -1 ≥ log 1+ε 2 -1. As f is monotonous, we have: which gives the desired bound on the obtained values.

f (k) ≤ W • f 2 (k -c), k ≥ c W, k < c

  of Y and use a simplified notation Y [. . j], and a fragment Y [i] . . . Y [n] a suffix of Y denoted by Y [i . .]. We say that a fragment Y [i . . j] contains a position k if i ≤ k ≤ j. We denote by ε the empty string.

Definition 2 . 3 .

 23 (Compact Thompson automaton) Given a Thompson automaton T (R), we define the compact Thompson automaton T C (R) as the automaton obtained from T (R) by replacing every maximal path of transitions labelled by a 1 , a 2 , . . . , a k ∈ Σ by a single transition labelled by a 1 a 2 . . . a k . The non-empty labels of T C (R) are called atomic strings, and the size of the (multiset) of the atomic strings is defined to be the size of R.

Figure 2

 2 Figure 2 gives an example of the Thompson automata for R = b(ab|b) * ab. We note that in general the size of a regular expression is much smaller than the total number of characters in it and is bounded by twice the number of union and Kleene star symbols plus two. The size of a regular expression measures its "complexity".

Figure 2 :

 2 Figure 2: The Thompson automatons of the regular expression b(ab|b) * ab.

1 to v 2

 2 of total weight x in O((|E(G)| + |V (G)| 3 )x polylog x) time and O((|E(G)| + |V (G)| 3 ) polylog x) space and succeeds with probability at least 1/2.

Figure 3 :

 3 Figure 3: Anchors of a periodic string W with period ρ.

  containing the anchor (i.e., containing |U | + |V | + a).

Lemma 4 . 4 .

 44 Let W be a periodic string with period ρ. Consider a fragment W [ . . r] of length at least 4ρ and a partitioning W [ .

Figure 4 :

 4 Figure 4: Illustration of Claim 4.5.

  that there is a fragment S[p . . t] of the string S = U V (W [. . r kq ]) periodic with period π that contains |U | + |V | + a ∆ q and such that there are at least six repetitions of the string period of S[p . . t] before and after |U | + |V | + a ∆

Figure 6 :

 6 Figure 6: Illustration of the proof of Lemma 4.4(a), case π > ρ q .

  [1 . . ρ]. Consider now the case π > ρ 0 . Consider the suffix S[a + 1 . .] = W [a ∆ 0 + 1 . . r k0 ]. It contains an occurrence of S[1 . . 2π]. By Fact 3.5, S[1 .

  t | p -1 and ω = g p-1 t

Fact 5 . 5 .

 55 (cf.[START_REF] Barkley | Approximate formulas for some functions of prime numbers[END_REF] Theorem 13]) ψ(x; q, a) ≤ ϑ(x; q, a) + O( √ x).

  x) and finally ϑ(x) = x + o(x) by[59, (2.29)].

  Every product introduces O(|V (G)| 3 ) and gates. Hence the total number of gates is O(|E(G)| + |V (G)| 3 • polylog x). Finally we discuss the properties of the values computed in D r and all the intermediate gates. Recall that D k [u, v][d] is the value of D k [u, v][d] if computed exactly, without taking modulo p at every step. For each d ≤ (1 + ε) k , every walk between u and v of weight d contributes at least 1 to D k [u, v][d]. Notice that such walk may contribute more than 1, as it can be cut into three parts in many ways, for different triples k 1 , k 2 , k 3 . As no walks of weight different from d contribute to D k [u, v][d], there is a walk from u and v of weight d iff D k [u, v][d] > 0. However, while computing the arrays D k we operate in Z p , so we might have false negative error if p | D k [u, v][d]. In Theorem 5.2 we include such situations in the probability of failure (we fail if p | N , where N = D r [u, v][d]), but we need to ensure that D r [u, v][d] never exceeds 2 O(t log t) . Lemma 5.10. Suppose we execute the above algorithm up to the r-th matrix D r in Z, not applying modulo p in every gate. Then all the obtained values are bounded by 2 O(x log x) . Proof. Recall that ε = 1 log x , r = log 1+ε x , we operate on vectors with t = O(x polylog x) entries, and the convolutions do not overflow as the result always fits in the first y = O(x) elements of the vectors. Let f (k) be a monotonous function that upper bounds the values in D k and g = |V (G)|. Observe that a single product A B of matrices with entries bounded by respectively a max and b max results in a matrix with entries bounded by g • y • a max • b max . Hence, as values in B k2 are 0 or 1, from Equation (5.5) we have the following bound:

2 = log x + O( 1 )

 21 which solves by induction to f (k) < W 2 k c +1 -1 . Then, as W = O(x 5 ) we have:f (r) < W 2 r c +1 -1 < W O(2 r/c ) < 2 O(2 r/c log x)Finally, we show that r/c ≤ log x + O(1).Combining that with the above bound on f (r) we obtain:f (r) < 2 O(2 r/c log x) ≤ 2 O(2 log x+O(1) log x) = 2 O(x log x)

  Copyright c 2022 by SIAM Unauthorized reproduction of this article is prohibited 680 Downloaded 12/06/22 to 131.254.252.95 . Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/terms-privacy

				π
			ρ q
	U	V	W [. . r kq ]
			p	a	t

Downloaded 12/06/22 to 131.254.252.95 . Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/terms-privacy

Copyright c 2022 by SIAM Unauthorized reproduction of this article is prohibited

One could also use one of the streaming dictionary matching algorithms (see the introduction), but this does not change the final complexity and makes the description of the algorithm more complex.

With high probability means with probability at least 1 -1/n c for any predefined constant c > 1.

Note that when |occ(P, X)| ≤ 2, we can represent occ(P, X) as at most two (degenerate) arithmetic progressions of length 1, we will use this fact to simplify the description of the algorithms.

Partially supported by the National Science Centre, Poland, under grant number 2017/27/N/ST6/02719 and by the Foundation for Polish Science (FNP). † Institute of Computer Science, University of Wroc law, Poland. Partially supported by the Bekker programme of the Polish National Agency for Academic Exchange (PPN/BEK/2020/1/00444) and the grant ANR-20-CE48-0001 from the French National Research Agency (ANR). ‡ DI/ENS, PSL Research University, IRISA Inria Rennes, France. Partially supported by the grant ANR-20-CE48-0001 from the French National Research Agency (ANR). § DI/ENS, PSL Research University, France. Partially supported by the grant ANR-20-CE48-0001 from the French National Research Agency (ANR).

Preprocessing. We start by deleting all transitions (u, v) from T C (R) that are labelled by atomic strings of lengths larger than n.

Let F contain all atomic strings A such that there is an ε-transitions path from the endpoint of the transition labelled by A to the final state of T C (R). In addition, for each atomic string A, compute the subset A i1 , A i2 , . . . , A ij of atomic strings such that there is an ε-transitions path from the endpoint of the transition labelled by A i j , 1 ≤ j ≤ j, to the starting point of the transition labelled by A.

For each periodic P ∈ Π, consider a string ∆(P ) = P [|P | -ρ + 1 . .], where ρ is the period of P . During the preprocessing step, the algorithm computes the generator set of anchors A (Definition 4.1) for the string W = (∆(P )) ∞ .

Define the overlap of two strings X and Y as the maximal length of a suffix of X that equals a prefix of Y , Π(P ) to be the set of all canonical prefixes such that their overlap with W is at least 2ρ, and Overlap(P ) = P ∈Π(P ) { : is the overlap of P and W }. The algorithm computes Π(P ) and Overlap(P ) during the preprocessing step as well.

For regular expression pattern matching, it also computes the smallest integer µ(P ) such that p = µ(P ) • ρ ∈ occ(P, W ) and p is a witness for P in W (in the sense of Definition 3.3).

Finally, the algorithm creates a directed graph G(P ) = (V, E) from the compact Thompson automaton T C (R). Consider again the string W = (∆(P )) ∞ . For each canonical prefix P ∈ Π(P ), the algorithm creates a node v ∈ V corresponding to a pair (P , r), where r is the remainder of the overlap of P and W modulo ρ. Additionally, for every fragment W [i . . j] = P ∈ Π which is anchored by an anchor a ∈ A * (W ), it creates a node v ∈ V corresponding to a pair (P , j (mod ρ)) (for two identical prefix-remainder pairs, it creates just one node).

Consider two nodes v , v ∈ V . Suppose that v corresponds to (P , r ) and v to (P , r ), where P , P are canonical prefixes of atomic strings A , A , respectively, and r , r are remainders modulo ρ. For 0 < ≤ 10ρ, the algorithm adds an edge (v , v ) of length to E if there is a walk in T C (R) from the ending state of the transition labelled by A to the ending state of the transition labelled by A such that the concatenation of the labels in this walk equals to a string L = ∆(P )[r . .]∆(P ) α ∆(P )[. . r ], where the integer power α is chosen so that |L| = (in other words, the concatenation equals to a fragment of W with the offsets defined by v and v and of an appropriate length, if such a fragment does not exist, the algorithm does not create the edge).

It might seem that the resulting graph is infinite, but as we show below, this is not the case.

Claim 4.8. Consider all occurrences W [ i . . r i ], i ∈ Z + , of a string X in W . The size of the set {r i (mod ρ) :

Copyright c 2022 by SIAM Unauthorized reproduction of this article is prohibited 682 Downloaded 12/06/22 to 131.254.252.95 . Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/terms-privacy Proof. We consider two cases: |X| ≥ 2ρ and |X| < 2ρ. In the first case, by Fact 3.5, if there is at least one occurrence of X in W , then X is periodic with period ρ. By Corollary 4.7, we have r i = q (mod ρ) for some fixed q and all i ∈ Z + . The claim follows from Lemma 4.2.

In the second case, for all a ∈ A * (W ) such that a ≥ 2ρ, and for all strings

It follows that for all a, a ∈ A * (W ) such that a, a ≥ 2ρ and a = a (mod ρ), the sets {r i (mod ρ) : W [ i . . r i ] is anchored by a, i ∈ Z + } and {r i (mod ρ) : W [ i . . r i ] is anchored by a , i ∈ Z + } are equal. Moreover, each of them contains only a constant number of elements. Therefore, the size of the set {r i (mod ρ) : Proof. The size of Π, and consequently Π(P ), is O(d log n). For each string P ∈ Π(P ), the remainder r of the overlap of P and W modulo ρ is defined in a unique way. By Claim 4.8, for each string P ∈ Π there are O(log ρ) different remainders r modulo ρ such that there is an anchored occurrence of P ending at a position p = r (mod ρ).

Observe that the interval [0, 10ρ] can contain only a constant number of values such that the power α is an integer. Hence for each pair of nodes we have only a constant number of possible edges, so |E| = O(d 2 log 4 n).

For each edge, we can check whether it exists in time

Corollary 4.10. (Of Theorem 3.8) There exists an algorithm which, given the graph G(P ), its two nodes v 1 and v 2 and a number x ≤ n, decides if there is a walk from v 1 to v 2 of total weight x in O(xd 3 polylog n) time and O(d 3 polylog n) space and succeeds with high probability.

Proof. Recall that ρ ≤ n. We substitute the bounds from Corollary 4.9 into Theorem 3.8. Then we repeat the algorithm of Theorem 3.8 2c log n times and output the majority answer to obtain a success probability of at least 1 -1/n c . Main phase. During the main phase of the algorithm, we run the pattern matching algorithm (Theorem 3.4) for every P ∈ Π. For every non-periodic P ∈ Π, we store (at most) two latest witnesses. For every periodic P ∈ Π, we run the pattern matching algorithm for ∆(P ) = P [|P | -ρ + 1 . .] and T , where ρ is the period of P . Definition 4.11. We say that a fragment T [i . . j] is a streak of a string X if T [i . . j] = X k for some integer k ≥ 1 and it is maximal, i.e. it cannot be extended neither to the left nor to the right.

The pattern matching algorithm detects streaks of ∆(P ) in the arrived prefix of T . Every witness r for P belongs to occ(P, T ) and by Observation 3.7 ends in such a streak. At any moment of the algorithm, we store (at most) two latest streaks and a compact representation of witnesses in occ(P, T ) that end in it. For membership testing we assume that the witnesses are defined as in Definition 3.2, and for pattern matching as in Definition 3.3. Perhaps a bit counter-intuitively, the representation contains witnesses from occ(P, T ) and witnesses for other canonical prefixes as well, the reason for it will become clear later. Formally, the representation of a streak S = T [i . . j] consists of the following elements, where ρ = |∆(P )|:

1. For each P ∈ Π(P ) and its overlap with W , the representation contains p = i + -1 if p ∈ occ(P , T ) and is a witness; The algorithm uses the compact representations of witnesses to decide whether a newly detected occurrence r ∈ occ(P, T ) for some P ∈ Π is a witness: Lemma 4.12. Let d < n. Assume that T [r] is the latest arrived character of the text and that r ∈ occ(P, T ). Assume that for each non-periodic P ∈ Π we store two latest witnesses in occ(P , T ), and for each periodic P ∈ Π we store the two latest streaks of ∆(P ) and compact representations of the witnesses in them. In addition, assume that we store the set of all atomic strings A such that (r -1) is a witness for occ(A, T ). One can decide whether r is a witness for P in O(nd 4 polylog n) time and O(d 3 polylog n) (extra) space with high probability.

Proof. Let

where A is an atomic string. Consider two cases: k = 0 and k ≥ 1.

Case 1:

. . , A ij be the atomic strings such that there is an ε-transitions path from the endpoint of the transition labelled by A i j , 1 ≤ j ≤ j, to the starting point of the transition labelled by A. The position r is a witness for P iff for some 1 ≤ j ≤ j, the position (r -1) is a witness for A i j . We can decide whether this holds in O(d) time.

Case

, and ρ = |∆(P )|. If P is non-periodic and r ∈ occ(P , T ), the algorithm stores it explicitly by Observation 3.6. Otherwise, by Observation 3.7, r belongs to one of the two latest streaks of ∆(P ), let it be a fragment

. Suppose that r is a witness for P . Let us first explain the solution for the regular expression membership problem, and then we will show how to modify it for the regular expression pattern matching problem.

In the membership problem, if r is a witness for P , then

. r m ] be the fragment containing i. We consider two subcases:

) is a multiple of ρ, then we obtain that T [r m -ρ . . r m -1] = ∆(P ), a contradiction with the definition of S. If -(r m -i + 1) is not a multiple of ρ, then there is an occurrence of ∆(P ) in the prefix (∆(P )) 2 of S that does not end at positions ρ or 2ρ. By Corollary 4.7, we obtain a contradiction. Therefore, r m -i + 1 = and the compact representation of witnesses in S stores r m ∈ occ(T [ m . . r m ], T ).

If m = m or r m -r m ≤ 8ρ, then we are done: if r is a witness, it must be stored explicitly, and we can check whether it is the case in O(d log 2 n) time. Otherwise, we use the following claim:

, is either anchored by an anchor a ∈ A * (S), or has length at least 2ρ, and for each 1 ≤ q ≤ q, m q -r m q -1 ≤ 10ρ.

Proof. The sequence is built as follows. Let m 0 = m and m q be the latest index added to the sequence. If there is an index m such that T [ m . . r m ] has length at least 2ρ or m = m and m -r q ≤ 10ρ, then set m q +1 = m and continue. Otherwise, let m be the smallest index such that m -r m q ≥ 8ρ. Note that we also have m -r m q ≤ 10ρ (otherwise, the length of T [ m -1 . . r m -1 ] would have been larger than 2ρ). By Lemma 4.2, there is

We set m q +1 = m and continue.

Let v be the node in G(P ) corresponding to (T [ m . . r m ], r m -i + 1 (mod ρ)), and v be the node corresponding to (P , r m -i + 1 (mod ρ)). We have that j is a witness iff there exists the sequence m = m We now explain how to modify the argument so that it can be used for regular expression pattern matching. Note that in pattern matching, if r is a witness for P , then there is some position , 1 ≤ ≤ r such that r ∈ occ(P , T ) is a witness. The position can be inside the streak S, i.e. m can be undefined, making it impossible to apply the argument above. However, we can easily check if this is the case using the integer µ(P ) we computed during the preprocessing step: if µ(P ) • ρ ≥ (r -i + 1), then r is a witness and we are done, and otherwise ≤ i (if r is a witness), m is defined, and we can apply the argument above. Proof. If d ≥ n, we can use Claim 3.1. Below we assume that d < n. Recall that we do not account for the time used during the preprocessing step (but one can note that it is polynomial in d and the total length of the atomic strings of R). The information computed during this step, including the graphs G(P ) for each P ∈ Π, takes O(d 3 log 5 n) space.

During the main step, we use Lemma 4.12 to maintain the compact representations of the streaks of ∆(P ) for each P ∈ Π, and to decide, eventually, whether T matches the regular expression R. Whenever an instance of the pattern matching algorithm detects an occurrence of ∆(P ), we decide in constant time whether this occurrence extends the latest streak of ∆(P ) or starts a new one. If the number of streaks becomes equal to three, we discard the oldest streak.

When an instance of the pattern matching algorithm detects r ∈ occ(P, T ) for some P ∈ Π, we must decide whether r is a witness and whether we must store it in the compact representation of the streaks containing r. We apply Lemma 4.12 to decide whether r is a witness in O(nd 4 polylog n) total time and O(d 3 polylog n) space and then in O(d log n) time whether r must be added to the compact representations of the streaks containing r. Note that a position r can belong to occ(P, T ) for O(d log n) canonical prefixes P ∈ Π, and therefore in the worst case we spend O(nd 5 polylog n) to process r. The compact representations of the streaks take O(d 2 log 3 n) space.

Recall that F contains all atomic strings A such that there is an ε-transitions path from the endpoint of the transition labelled by A to the final state of T C (R). In the regular expression pattern matching problem, we report all positions r such that r is a witness in occ(A, T ) for some A ∈ F. In the regular expression membership problem, T ∈ L(R) if n is a witness for occ(A, T ) for some A ∈ F.

Proof of Theorem 3.8

An important tool in our proof is the framework that allows computing output of a circuit time-and spaceefficiently. Before we describe the framework in detail, we provide some notation following [START_REF] Bringmann | A near-linear pseudopolynomial time algorithm for subset sum[END_REF]. A circuit is a directed acyclic graph with nodes of in-degree 0 or 2. Degree-0 nodes are called inputs and degree-2 nodes are gates. In our application, every node corresponds to a vector from Z t p (i.e. a vector of length t with values in Z p ) indexed from 0 to t -1, for some values of p and t that will be specified later. A vector in Z t p is a singleton if it has at most one non-zero entry.

There are two types of gates: and that denote respectively the pointwise addition and vector convolution binary gates, that is (a b)

Every gate corresponds to the result of its underlying operation applied to its incoming nodes. We say that a convolution gate with input a, b ∈ Z t p does not overflow, if for all i ≥ t, (a b)[i] = 0. An element ω is a t-th root of unity in Z p iff ω t ≡ 1 mod p but ω s ≡ 1 mod p for all 0 < s < t.

With the definitions at hand, we are ready to state the technique introduced by Lokshtanov and Nederlof [START_REF] Lokshtanov | Saving space by algebraization[END_REF] for complex numbers and its modular variant discussed by Bringmann [START_REF] Bringmann | A near-linear pseudopolynomial time algorithm for subset sum[END_REF]: Theorem 5.1. (cf. [START_REF] Bringmann | A near-linear pseudopolynomial time algorithm for subset sum[END_REF]Theorem 4.2]) Let p be a prime, t ≥ 1, and suppose that Z p contains a t-th root of the unity, ω. Let C be a circuit over (Z t p , , ) which takes as an input only singleton constants and outputs a vector out(C) ∈ Z t p . Suppose that no convolution gate overflows. Then given p, t, ω, and 0 ≤ x < t we can compute out(C)[x] in time O(|C|t polylog p) and space O(|C| log p). Downloaded 12/06/22 to 131.254.252.95 . Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/terms-privacy Lemma 5.7. Suppose π(x; q, 1) = Ω( √

x(log x) B-1 ). With probability at least 7/8, in O( √ x log x) arithmetic operations and O(log x) space we can find such a prime p ≤ x such that p ≡ 1 mod q.

Proof. Clearly, we can check if a number n is prime by iterating through all numbers 2, 3, . . . , √ n and checking if they are a divisor of n. Let Q = {n ≤ x : n = 1 mod q}. Observe that the probability that a number chosen uniformly at random from Q is prime is at least:

Hence by checking Θ(log x) numbers from Q we find a prime with probability at least 7/8. Proof. First, we generate the set of all divisors of p -1 in O( √ p) time by iterating through 2, 3, . . . , √ p -1 and checking if they are a divisor of p -1. By using an auxiliary accumulator we can restrict only to prime divisors, we call this set D. Now we can check if a number g is a generator of Z * p by checking if for every p ∈ D, a prime divisor of p -1, we have g (p-1)/p ≡ 1 mod p. Using exponentiating by squaring, this runs in total O(polylog p) time.

The probability of a random g ∈ {0, . . . , p -2} to be a generator is φ(p -1)/(p -1) = Ω(1/ log log p), as φ(n) = Ω(n/ log log n) [59, Theorem 15]. Hence by checking Θ(log log p) numbers from Z * p we find a generator with probability at least 7/8. Finally, as x ≥ y 2 and π(x; q, 1) = Ω( √ x(log x) B-1 ) and B ≥ 3 we have π(x; q, 1) ≥ y log 2 y ≥ 8 log N , as N ≤ 2 O(y log y) . Because N has at most log N prime divisors, the probability that the chosen prime p is one of them is at most 1/8. Summing up, there are four events due to which our algorithm can fail:

1. The number q does not satisfy π(x; q, 1) = Ω( √ x(log x) B-1 ); 2. We did not find p in the planned number of iterations;

3. The chosen p divides N ; 4. We did not find g in the planned number of iterations.

We note that we do not have access to the value of N during the algorithm, so we cannot spot immediately that the chosen p is wrong. When we fail to find g or p in the planned number of iterations we terminate. However, if q is chosen wrongly, we cannot detect it immediately, but then the subsequent steps (choosing p or g) will have a larger probability of failure. To conclude, the overall probability of a failure is at most 1/2 and the running time of the whole procedure is O( √ x polylog(x)) = O(y polylog y). This concludes the proof of Theorem 5.2.

5.2 Walks in a weighted graph. We can finally prove Theorem 3.8. We first describe an algorithm that uses significantly much more time and space than desired, and then improve it. We compute arrays C k for k ∈ {0, . . . , log x } indexed by nodes u, v ∈ V (G), where C k [u, v] is a bit-vector of length x + 1 such that:

implies that there exists a walk of weight d from u to v;

2. For every d ≤ 2 k , if there exists a walk of weight

In other words, C k contains the information about all walks of weight at most 2 k in G and possibly some other walks of weight at most x. We initialize the array C 0 in the following way:

Now we compute the consecutive arrays C k by repeated application of (or, Convolution x )-product as follows: Saving space with circuits. To save both time and space, we will use circuits and the framework of Theorem 5.1. In order to use this framework, we need to modify our algorithm in various aspects. First, in O(x polylog x) time we find the appropriate values of p, t, ω using Theorem 5.2 from Section 5.1 for y = Θ(x) that will be defined precisely later. Then t = O(x polylog x). Instead of bit-vectors as entries of the array C k , we operate on vectors from Z t p over (Z p , +, •). In other words we use (addition in Z t p ) instead of Boolean or and (the standard (+, •)-convolution modulo p) instead of the Boolean (∨, ∧)-convolution. Then the product between

counts modulo p walks from u to v of weight d, possibly counting one walk more than once -we analyse these values in detail at the end of the proof. Now we describe the construction of the circuit. To simplify the presentation, we work with multi-ary addition gates * which can be replaced with binary gates at the expense of doubling the total size of the circuit.

The above construction gives a circuit on O(|E(G)| + |V (G)| 3 log x) gates with singleton constants, out of which we need to output if C log x [v 1 , v 2 ][x] > 0. However, we still cannot use the framework from Theorem 5.1, as we cannot guarantee that there are no convolution gate overflows. Indeed, if there are edges of weight almost x, we would obtain walks of weight x 2 . In the following paragraph we show a refined construction in which we have more control on the maximum weight of walks considered in the k-th step of the algorithm. Refined construction. Let ε be a value to be determined precisely later. Instead of the arrays C k , we will compute arrays D k that, informally, describe all walks of total weight at most (1 + ε) k , some walks of weight Now we show that all the invariants about D k are satisfied. Clearly there are no false-positive entries in the array. We never miss a walk of weight at most (1 + ε) k , as the condition (a) filters out the triples k i contributing only the walks of total weight larger than (1 + ε) k . The condition (b) guarantees that the first and third part of the walk have weight at most 1 2 (1 + ε) k . In the following lemma we show that we also never construct walks of too large weight.

Applying the above inequality to (5.6) concludes the inductive step.

Setting ε = 1/ log x, as log(1 + ε) > ε we obtain that there are


Sandra Domenek
email: sandra.domenek@agroparistech.fr

ECO-DESIGN OF PACKAGING: A CHALLENGE FOR THE SUPPLY CHAIN OF FOOD

Keywords: biobased and biodegradable polymers, valorization of agricultural by-products, circularity

Introduction.

Packaging is an active partner for the conservation and distribution of foods. Its main functions are transport, communication with the customer, protection of food against chemical, physical, and microbial contamination. The packaging system for a given products has different components which are i) primary packaging, i.e. the material directly in contact with the food, ii) secondary packaging, e.g. boxes containing several consumer units, and iii) tertiary or transport packaging, which includes larger transport boxes, pallets, cling films, containers, etc. Plastics are the main material used in packaging and represent roughly one third of the mass of the packaging system. Faced with the plastic pollution of the environment, which is largely caused by single use plastics, improvements in the packaging system to decrease its environmental impact are necessary. Recent legislations in the EU aim directly at the decrease, and even interdiction, of single use plastics (SUP directive EU 2019/904). Because packaging is a facilitator of the supply chain, in has both, direct and indirect, environmental impacts. Direct impacts are caused by the fabrication and disposal of the materials in themselves, while indirect impacts are caused by food loss, inefficient logistics, design problems, etc. (1). With this respect, an optimum has to be found taking into account the environmental impact of the packaging system and the impact of lost food (Fig. 1). Furthermore, packaging materials need to be integrated in circular economy flows. In the case of food packaging, this could be achieved by increasing their circularity in the technosphere by recycling or by composting or anaerobic digestion together with food wastes in the biosphere (Fig. 2).

Results. One of the main hurdles for recycling of plastics into high added value products, such as food packaging, is the presence of contaminants coming from the process or various sources in an open system (2,3). The unpredictability of contaminants is a huge challenge to risk evaluation by analytical chemistry and risk management. Examples are shown how non-targeted chemical analysis can be coupled to calculation-based risk evaluation methods [START_REF] Kermorvant | FoodSim[END_REF]. Circularity in the biosphere could be achieved using by-products of agriculture and forestry to product new biobased and biodegradable materials [START_REF] Delliou | Agricultural, Forestry and Bioindustry Biotechnology and Biodiscovery[END_REF]. Those materials need of course to comply with the safety and performance standards of food packaging. Different examples are discussed concerning the formulation of polylactides (PLA) in the aim to increase ductility and biodegradability using byproducts of the vegetable oil industry [START_REF] Delliou | Agricultural, Forestry and Bioindustry Biotechnology and Biodiscovery[END_REF]. The barrier properties of PLA towards oxygen are lower than petrochemical benchmarks. Active antioxidant packaging is one means to achieve performing materials and using underexploited resources such as natural antioxidants [START_REF] Stoll | [END_REF].

Recently, large improvements in oxygen barrier properties were achieved using nanocelluloses and innovative material architectures (7). Blended polyhydroxyalkanoates potentially produced from agricultural byproducts could be shown to be suitable for the packaging of frozen foods (8).

Conclusions.

To bring these promising research results into the market and increase circularity of the whole supply chain, a co-development with all members is necessary to increase acceptability an avoid shifting impacts form one place to the other. We are working now actively in generating these trade-offs with the members of the supply chain (project Chaire CoPack) (9).

Fig. 1 .

 1 Fig. 1. Scheme of the environmental impact of a given service unit which is the packaging and the contained food

Fig. 2 .

 2 Fig. 2. Circular economy schemes for the food/packaging system