Linear Time Subsequence and Supersequence Regex Matching

Our main focus is on the subsequence and supersequence relations, and our first contribution is to show that the complexity of regular expression matching can be substantially improved when performed with these relations. Namely, we show that given a regex $r$ and string $w$, we can check in time $O(|w|+|r|)$ whether some subsequence of $w$ matches $r$, or whether some supersequence of $w$ matches $r$. As we show, this surprising tractability result is in strong contrast to the same problem for other string relations (infix, prefix, left-extension and extension), or for regex matching in the usual sense – in all these contexts, the $O(|w|\cdot |r|)$ algorithm is optimal assuming SETH.

Our linear time upper bound for subsequence and supersequence matching is achieved by transforming the regex $r$ into an $\epsilon$NFA $A$ that accepts $w$ if and only if $w$ has a subsequence (or supersequence) that matches $r$, following a known construction in the context of so-called upward and downward closures [8]. We then exploit special properties of $A$ that allow us to decide whether it accepts $w$ in linear time. While it is in general easy to see that the quadratic upper bound can be improved in the case of subsequence and supersequence matching, we think that linear time complexity is rather unexpected, and some algorithmic care is required to achieve it. In particular, we stress the fact that our $O(|w|+|r|)$ complexity bound does not assume the input alphabet to be constant.

Motivated by this positive algorithmic result, we investigate a natural generalisation of the matching problem: compute a maximum-length/minimum-length string $u$ with $u⪯w$ that matches $r$. For the subsequence and supersequence relations, we can show (conditionally) that this generalisation worsens the complexity: our $O(|w|+|r|)$ matching algorithm does not generalise to this stronger problem. More precisely, for the max-variant of the subsequence relation or the min-variant of the supersequence relation, we show that truly subquadratic algorithms would imply truly subquadratic algorithms for the longest common subsequence or the shortest common supersequence problems, which is impossible under SETH (see [13, 1]). For the min-variant of the subsequence relation or the max-variant of the supersequence relation, we show a weaker bound: an $O(|w|+|r|)$ algorithm would imply that we can detect triangles in a dense graph in linear time. On the positive side, however, we show that all these problems can be solved within the original matching complexity of $O(|w|\cdot |r|)$, in particular generalising the fact that longest common subsequences and shortest common supersequences can be computed within this bound. We also show that the same upper bound applies for the infix, prefix, and (left-)extension relations, and that it is optimal under SETH.

Finally, we investigate the complexity of checking whether all strings $u$ with $u⪯w$ match $r$. While it is easy to see that this can be solved efficiently for the infix and prefix relation, it becomes intractable for the (left-)extension, subsequence and supersequence relations. We pinpoint the complexity of all these variants (conditionally to SETH) except for the infix relation, i. e., we leave a gap between the upper and lower bound for the problem of deciding whether the input string has an infix which is rejected by an input regex.

Subsequences and supersequences play an important role in many different areas of theoretical computer science: in formal languages and logics (e. g., piecewise testable languages [56, 57, 36, 48], or subword order and downward closures [32, 43, 42, 62]), in combinatorics on words [51, 23, 54, 46, 52, 53] or combinatorial pattern matching [33, 35, 45, 58, 19, 27], for modelling concurrency [50, 55, 15], in fine-grained complexity [11, 14, 1, 2, 49]), etc. See also the surveys [10, 18, 40] and the references therein. Moreover, algorithmic problems related to the analysis of the set of subsequences of the strings of a formal language, given as a grammar or automaton, are studied in [4] and [21]. Closer to our topic, matching regular expressions to the subsequences of a string is an important matching paradigm in event stream processing, where we receive a stream of events that result from different processes, which means that consecutive events from the same process are represented as a subsequence in this string (see, e. g., [7, 28, 63, 38, 39, 25, 31]).

To prove our linear upper bound for the subsequence regex matching problem, we first transform the regular expressions into an $\epsilon$NFA $A_{\mathrm{𝗌𝗎𝖻}}$ that accepts the upward closure of $𝖫(r)$, i. e., the set $\{u\mid \exists v\in 𝖫(r):v{⪯}_{\mathrm{𝗌𝗎𝖻}}u\}$ (note that $w$ has a subsequence that matches $r$ if and only if $w\in 𝖫(A_{\mathrm{𝗌𝗎𝖻}})$). Similarly, the upper bound for the supersequence regex matching problem is based on constructing an $\epsilon$NFA $A_{\mathrm{𝗌𝗎𝗉}}$ for the downward closure $\{u\mid \exists v\in 𝖫(r):v{⪯}_{\mathrm{𝗌𝗎𝗉}}u\}$. The downward and upward closures are well-investigated concepts in formal language theory (see citations above). In particular, it has been noted in [8, Lemma 9] that the powerset-DFA of $A_{\mathrm{𝗌𝗎𝖻}}$ always transitions from a state set to a superset of this state set (analogously, the powerset-DFA of $A_{\mathrm{𝗌𝗎𝗉}}$ always transitions from a state set to a subset of this state set). However, this property does not imply that the powerset-DFA of $A_{\mathrm{𝗌𝗎𝖻}}$ and $A_{\mathrm{𝗌𝗎𝗉}}$ is necessarily small, since [47] proves an exponential lower bound on their number of states. Our notion of subsequence or supersequence matching is related to so-called upward-closed and downward-closed languages (which are languages respectively equal to their upward or downward closure), because for such languages the usual notion of regex matching coincides with subsequence and supersequence matching, respectively. These languages have been investigated, e. g., for downward-closed languages in [26] or in [3] (under the name “simple regular expressions”) and for upward-closed languages in [29]. However, to our knowledge, none of the works focusing on the upward or downward closure, or on upward-closed or downward-closed languages, have investigated the complexity of the matching problem like we do – so it was not known that these problems could be solved in time $O(|w|+m)$, or indeed that their complexity was lower than that of standard regex matching.

In Section 2, we give preliminaries and formally define the matching problems that we study. In Section 3, we first recall some basics about the state-set simulation of $\epsilon$NFAs and then explain how our regex matching problems for the subsequence and supersequence relation reduce to the state-set simulation of certain $\epsilon$NFAs. Then, in Section 4, we give the corresponding linear time algorithms. Sections 5 and 6 are concerned with the quantitative and universal problem variants for all considered string relations. The conditional lower bounds that complement our upper bounds are discussed in Section 7. Due to space restrictions, we only give proof sketches of some of our results (all proof details can be found in the full version [5] of this paper).

We let $\mathrm{\Sigma }$ be a finite alphabet of symbols (sometimes called letters) and write ${\mathrm{\Sigma }}^{\ast }$ for the set of strings (sometimes called words) over $\mathrm{\Sigma }$. We write $\epsilon$ for the empty string. For a string $w\in {\mathrm{\Sigma }}^{\ast }$, we denote by $|w|$ its length and, for every $i\in \{1,2,\mathrm{\dots },|w|\}$, we denote by $w[i]$ the $i^{\text{th}}$ symbol of $w$. For $i,j\in \{1,2,\mathrm{\dots },|w|\}$ with $i\le j$, we denote by $w[i:j]$ the factor (also called infix) $w[i]w[i+1]\mathrm{\cdots }w[j]$; in particular, $w[i:i]=w[i]$.

Regular expressions over $\mathrm{\Sigma }$ are defined as follows. The empty set $\mathrm{\varnothing }$ is a regular expression with $𝖫(\mathrm{\varnothing })=\mathrm{\varnothing }$, and every $x\in \mathrm{\Sigma }\cup \{\epsilon \}$ is a regular expression with $𝖫(x)=\{x\}$. If $s$ and $t$ are regular expressions, then $s\cdot t$, $s\vee t$, and $s^{\ast }$ are regular expressions with $𝖫(s\cdot t)=𝖫(s)\cdot 𝖫(t)$, $𝖫(s\vee t)=𝖫(s)\cup 𝖫(t)$, and $𝖫(s^{\ast })={(𝖫(s))}^{\ast }$. Here, we define as usual: $L_1\cdot L_2=\{uv\mid u\in L_1,v\in L_2\}$, $L^0=\{\epsilon \}$, $L^k=L^{k-1}\cdot L$ for every $k\ge 1$, and $L^{\ast }={\bigcup }_{k\ge 0}{L}^k$. The length $|s|$ of a regular expression $s$ is the total number of symbols of $s$ considered as a string.

We work with nondeterministic finite automata with $\epsilon$-transitions, called $\epsilon$NFA for brevity. An $\epsilon$NFA is a tuple $A=(Q,\mathrm{\Sigma },q_0,q_{𝖿},\delta )$ where $Q$ is a finite set of states, $q_0$ is the initial state, $q_{𝖿}$ is the final state, and $\delta \subseteq Q\times \mathrm{\Sigma }\cup \{\epsilon \}\times Q$ is the set of transitions. A transition of the form $(p,a,q)$ is called an $a$-transition. We will also interpret an $\epsilon$NFA $A$ as a graph which has vertex set $Q$ and which has directed edges labelled by symbols from $\mathrm{\Sigma }\cup \{\epsilon \}$ given by the transitions of $\delta$, i. e., any transition $(p,a,q)\in \delta$ is interpreted as a directed edge from $p$ to $q$ labelled by $a$. A transition $(p,a,p)$ with $p\in Q$ and $a\in \mathrm{\Sigma }\cup \{\epsilon \}$ is called a self-loop. A run of $A$ on an input string $w\in {\mathrm{\Sigma }}^{\ast }$ is a path (not necessarily simple) from $q_0$ to some state $p$ which is labelled with $w$, where the label of a path is just the concatenation of all $\mathrm{\Sigma }$-labels (ignoring $\epsilon$-labels). A run is accepting if $p=q_{𝖿}$. We write $𝖫(A)$ for the language accepted by $A$, i.e., the set of all strings for which $A$ has an accepting run. The size $|A|$ of $A$ is its number of transitions: we usually denote it by $m$, while $n$ denotes the number $|Q|$ of states.

It is well-known that a given regular expression $r$ can be converted in time $O(|r|)$ into an $\epsilon$NFA $A$ such that $𝖫(A)=𝖫(r)$ and $|A|=O(|r|)$. This can be achieved, e. g., using Thompson’s construction [34, Section 3.2.3]. Thus, in the sequel, we assume that all input regular expressions are given as $\epsilon$NFAs, and we state our results directly for arbitrary $\epsilon$NFAs.

Moreover, we assume that our $\epsilon$NFAs are trimmed, which means that every state is reachable from $q_0$ and every state can reach $q_{𝖿}$. This can always be ensured in time $O(m)$. If an $\epsilon$NFA is trimmed, then we also have that the number of states of the input automaton is at most twice the number of transitions. We also assume that for each $x\in \mathrm{\Sigma }$ we have at least one transition labelled with $x$, which means that $|\mathrm{\Sigma }|$ is in $O(m)$.

A string relation (over $\mathrm{\Sigma }$) is a subset of ${\mathrm{\Sigma }}^{\ast }\times {\mathrm{\Sigma }}^{\ast }$. For any string relation $⪯$ and $w\in {\mathrm{\Sigma }}^{\ast }$ we define ${\mathrm{\Lambda }}_{⪯}(w)=\{u\in {\mathrm{\Sigma }}^{\ast }\mid u⪯w\}$, i.e., the set of all strings that are in $⪯$ relation to $w$; we also lift this notation to languages $L\subseteq {\mathrm{\Sigma }}^{\ast }$, i.e., ${\mathrm{\Lambda }}_{⪯}(L)={\bigcup }_{w\in L}{\mathrm{\Lambda }}_{⪯}(w)$. Next, we define several well-known string relations.¹¹1Our generalised regex matching setting works for any string relation, but those that we study are all reflexive, transitive and antisymmetric; hence, we use the symbol $⪯$.

The prefix and infix relations are denoted by ${⪯}_{\mathrm{𝗉𝗋𝖾}}$ and ${⪯}_{\mathrm{𝗂𝗇}}$: formally, we write $u{⪯}_{\mathrm{𝗉𝗋𝖾}}w$ when $uv=w$ for some $v\in {\mathrm{\Sigma }}^{\ast }$ and we write $u{⪯}_{\mathrm{𝗂𝗇}}w$ when $vu{v}^{\prime }=w$ for some $v,v^{\prime }\in {\mathrm{\Sigma }}^{\ast }$. The left-extension and extension relations are denoted by ${⪯}_{\mathrm{𝗅𝖾𝗑𝗍}}$ and ${⪯}_{\mathrm{𝖾𝗑𝗍}}$: formally, we write $u{⪯}_{\mathrm{𝗅𝖾𝗑𝗍}}w$ when $u=vw$ for some $v\in {\mathrm{\Sigma }}^{\ast }$ and write $u{⪯}_{\mathrm{𝖾𝗑𝗍}}w$ when $w{⪯}_{\mathrm{𝗂𝗇}}u$. The subsequence and supersequence relations are denoted by ${⪯}_{\mathrm{𝗌𝗎𝖻}}$ and ${⪯}_{\mathrm{𝗌𝗎𝗉}}$: we write $u{⪯}_{\mathrm{𝗌𝗎𝖻}}w$ when $w[j_1]w[j_2]\mathrm{\dots }w[j_{|u|}]=u$ for some , and write $u{⪯}_{\mathrm{𝗌𝗎𝗉}}w$ when $w{⪯}_{\mathrm{𝗌𝗎𝖻}}u$. Note that we do not study the suffix and right-extension relations because they amount to prefix and left-extension up to mirroring the strings.

The well-known regex matching problem is to decide whether $w\in 𝖫(r)$ for a given regular expression $r$ and input string $w$. As explained above, this generalises to the $\epsilon$NFA acceptance problem, where we want to decide whether $w\in 𝖫(A)$ for a given $\epsilon$NFA $A$ and input string $w$. In this paper, we study the $⪯$-matching problem for $⪯$ a string relation among those presented above: For a given string $w\in {\mathrm{\Sigma }}^{\ast }$ and an $\epsilon$NFA $A$, decide whether $A$ accepts a string $u$ with $u⪯w$, i. e., decide whether ${\mathrm{\Lambda }}_{⪯}(w)\cap 𝖫(r)\ne \mathrm{\varnothing }$.

We also define quantitative versions of the matching problem. For a string relation $⪯$, the min-variant of the $⪯$-matching problem is as follows: For a given string $w\in {\mathrm{\Sigma }}^{\ast }$ and an $\epsilon$NFA $A$, compute a shortest string $u$ with $u⪯w$ and $u\in 𝖫(A)$, or report that no such string $u$ exists. The max-variant of the $⪯$-matching problem is as follows: For a given string $w\in {\mathrm{\Sigma }}^{\ast }$ and an $\epsilon$NFA $A$, either report that there are arbitrarily large strings $u$ with $u⪯w$ and $u\in 𝖫(A)$, or compute a longest string $u$ with $u⪯w$ and $u\in 𝖫(A)$, or report that no such string $u$ exists. Further, all lower bounds on the quantitative versions of the matching problem will already apply in the setting where we are only required to compute the length of the resulting string.

Finally, we define a universal variant of the matching problem. For a string relation $⪯$, the universal-variant of the $⪯$-matching problem is as follows: For a given string $w\in {\mathrm{\Sigma }}^{\ast }$ and an $\epsilon$NFA $A$, decide whether $A$ matches all strings $u$ with $u⪯w$, i. e., decide the inclusion problem ${\mathrm{\Lambda }}_{⪯}(w)\subseteq 𝖫(A)$.

See Figure 1 for an overview of all our upper and lower bounds with respect to the variants of the regex matching problem. Recall that $m$ is the size of the input $\epsilon$NFA.

The computational model we use to state our algorithms is the standard unit-cost word RAM with logarithmic word-size $\omega$, which allows processing inputs of size $n$, where $\omega \ge \log n$. This is a standard computational model for the analysis of algorithms, defined in [22]. To make some of our algorithms faster, we use the standard technique of lazy initialisation of arrays [30] to avoid spending linear time in the array size to initialise its cells. The time needed, after the lazy initialisation, to store a value in a cell of the array, or to check if a cell of the array was initialised and if so return the value it stores, is $O(1)$.

Recall that the inputs for our problems (see previous paragraph) are always an $\epsilon$NFA and a string over $\mathrm{\Sigma }$. For these inputs, we make the following assumptions. For an $\epsilon$NFA $A=(Q,\mathrm{\Sigma },q_0,q_{𝖿},\delta )$ with $|Q|=n$, $|\mathrm{\Sigma }|=\sigma$, and $m=|\delta |$, we assume that $Q=\{1,\mathrm{\dots },n\}$ and $\mathrm{\Sigma }=\{1,\mathrm{\dots },\sigma \}$; we can assume that both $Q$ and $\mathrm{\Sigma }$ are ordered sets, w.r.t. the canonical order on natural numbers. Hence, the processed strings are sequences of integers (representing the symbols), each of these integers fitting in one memory word. This is a common assumption in string algorithms: the input alphabet is said to be an integer alphabet (see, e. g., [17]). As we assume $\epsilon$NFAs to be trimmed, we also know that $n,\sigma$ are in $O(m)$. Moreover, an $\epsilon$NFA $A$ is given by its number of states, size of the input alphabet, initial and final state, and a list of $m$ transitions of the form $(q,a,q^{\prime })$, with $q,q^{\prime }\in Q$ and $a\in \mathrm{\Sigma }\cup \{\epsilon \}$.

Further, using radix sort, we can prepare for each state $q$ having outgoing transitions the list $L[q]$ of these transitions, sorted first according to the symbol labelling them, and then by the target state; for states without outgoing transitions $L[q]\leftarrow \mathrm{\varnothing }$. This allows us to simultaneously construct, for each $q\in Q$ and $a\in \mathrm{\Sigma }\cup \{\epsilon \}$ for which $q$ has an outgoing $a$-transition, the list $T[q,a]$ of transitions of the form $(q,a,q^{\prime })$; $T[q,a]$ is undefined for $q\in Q$ and $a\in \mathrm{\Sigma }\cup \{\epsilon \}$ in the case where $q$ has no outgoing $a$-transition. We will make the convention that, in the case that a self-loop $(q,a,q)$ exists, then $(q,a,q)$ is the first transition stored in $T[q,a]$; this allows us to test in $O(1)$ whether there exists a self-loop $(q,a,q)$ for any $q\in Q$ and $a\in \mathrm{\Sigma }\cup \{\epsilon \}$. Both $L[\cdot ]$ and $T[\cdot ,\cdot ]$ are implemented as arrays (of lists), which are lazily initialised (as mentioned above). So, computing the defined elements of $L[\cdot ]$ and $T[\cdot ,\cdot ]$ can be done in linear time, i. e., in $O(m)$.

For an NFA A without $\epsilon$-transitions and an input string $w$, the state-set simulation starts with $S_0=\{q_0\}$ and then, for every $i=1,2,\mathrm{\dots },|w|$, computes the set $S_i={𝖢}_{w[i]}(S_{i-1})$, where, for any state set $S$ and symbol $b\in \mathrm{\Sigma }$, we call ${𝖢}_b(S)$ the set of all states that can be reached from a state in $S$ by a $b$-transition, i. e., ${𝖢}_b(S)=\{q\mid p\in S\wedge (p,b,q)\in \delta \}$. Clearly, each $S_i$ contains exactly the states that are reachable from $q_0$ by a $w[1:i]$-labelled path. Now if we are dealing with an $\epsilon$NFA, then we can use the same idea, but we also have to compute the $\epsilon$-closures ${𝖢}_{\epsilon }^{\ast }(S)$ in between, i. e., the set of all states that can be reached from a state in $S$ by a path of $\epsilon$-transitions. More precisely, we start with $S_0={𝖢}_{\epsilon }^{\ast }(\{q_0\})$ and then, for every $i=1,2,\mathrm{\dots },|w|$, we compute the set $S_i={𝖢}_{\epsilon }^{\ast }({𝖢}_{w[i]}(S_{i-1}))$. Now each $S_i$ contains exactly the states that are reachable from $q_0$ by a path that is labelled with $w[1:i]$ (with $\epsilon$-transitions being ignored in the path label). Computing $S_0$ is called the initialisation and computing $S_i$ from $S_{i-1}$ is called an update step of the state-set simulation. For every $i=0,1,2,\mathrm{\dots },|w|$, the set $S_i$ is the set of active states at step $i$. We also say that a state $p$ is active at step $i$ if $p\in S_i$.

Given a state set $S$ and a symbol $b\in \mathrm{\Sigma }$, computing the set ${𝖢}_b(S)$ can be easily done in time $O(m)$, since we only have to compute for $p\in S$ the states $q$ with a transition $(p,b,q)$, which are given by $T[p,b]$. Thus, we have to inspect every transition at most once. Computing the $\epsilon$-closure ${𝖢}_{\epsilon }^{\ast }(S)$ can also be done in time $O(m)$ by a breadth-first search (BFS) that starts in all states of $S$ and only considers $\epsilon$-transitions (again, the entries $T[p,\epsilon ]$ can be used for that). This means that the initialisation and each update step can be done in time $O(m)$, which yields a total running time of $O(|w|m)$ for the whole state-set simulation. What is more, this running time is conditionally optimal. Indeed:

We now explain how we can use state-set simulation to solve the $⪯$-matching problem, specifically for the subsequence and supersequence relations (which are our main focus in this paper). It is easy to see that we can transform an $\epsilon$NFA $A$ into two $\epsilon$NFAs $A_{\mathrm{𝗌𝗎𝖻}}$ and $A_{\mathrm{𝗌𝗎𝗉}}$ such that $w\in 𝖫(A_{\mathrm{𝗌𝗎𝖻}})\iff {\mathrm{\Lambda }}_{{⪯}_{\mathrm{𝗌𝗎𝖻}}}(w)\cap 𝖫(A)\ne \mathrm{\varnothing }$ and $w\in 𝖫(A_{\mathrm{𝗌𝗎𝗉}})\iff {\mathrm{\Lambda }}_{{⪯}_{\mathrm{𝗌𝗎𝗉}}}(w)\cap 𝖫(A)\ne \mathrm{\varnothing }$. For example, this is done in [8, Lemma 8]. We review this construction as we adapt it later.

The $\epsilon$NFA $A_{\mathrm{𝗌𝗎𝖻}}$ is obtained from $A$ by simply adding a transition $(p,b,p)$ for every state $p$ and $b\in \mathrm{\Sigma }$. Intuitively speaking, these loops equip $A$ with the general possibility to consume symbols from $w$ without transitioning in a new state, which corresponds to ignoring symbols from $w$. Hence, the “non-ignoring” transitions of an accepting run of $A_{\mathrm{𝗌𝗎𝖻}}$ on $w$ spell out a subsequence of $w$ accepted by $A$. On the other hand, the $\epsilon$NFA $A_{\mathrm{𝗌𝗎𝗉}}$ is obtained from $A$ by simply adding a transition $(p,\epsilon ,q)$ for every existing transition $(p,b,q)$ with $b\in \mathrm{\Sigma }$. This means that while reading $w$ the automaton can always virtually process some symbols that do not belong to $w$. Hence, in an accepting run of $A_{\mathrm{𝗌𝗎𝗉}}$ on $w$, the actual transitions that read the symbols from $w$ along with the added $\epsilon$-transitions that virtually read some symbols spell out a supersequence of $w$ accepted by $A$.

Consequently, we can solve the subsequence and supersequence matching problem by checking whether $w\in 𝖫(A_{\mathrm{𝗌𝗎𝖻}})$ and $w\in 𝖫(A_{\mathrm{𝗌𝗎𝗉}})$, respectively, via state-set simulation. Since $|A_{\mathrm{𝗌𝗎𝖻}}|=O(n|\mathrm{\Sigma }|+m)$ and $|A_{\mathrm{𝗌𝗎𝗉}}|=O(m)$, we get the following:

It has been observed in [8, Lemma 9] that the $\epsilon$NFAs $A_{\mathrm{𝗌𝗎𝖻}}$ and $A_{\mathrm{𝗌𝗎𝗉}}$ have special properties that can be exploited in the state-set simulations to improve the bounds of Theorem 3.2.

Firstly, for $A_{\mathrm{𝗌𝗎𝖻}}$, whenever a state $p$ of $A_{\mathrm{𝗌𝗎𝖻}}$ is added to the set of active states in the state-set simulation, it will stay active until the end of the state-set simulation. This is due to the existence of the transition $(p,b,p)$ for every $b\in \mathrm{\Sigma }$. Consequently, for the state-set simulation of $A_{\mathrm{𝗌𝗎𝖻}}$, we have $S_0\subseteq S_1\subseteq \mathrm{\dots }\subseteq S_{|w|}$. Secondly, for $A_{\mathrm{𝗌𝗎𝗉}}$, we can observe that the state-set simulation starts with $S_0=Q$, i. e., the set of all states, which is due to the fact that every state in $A$ is reachable from $q_0$ by $\epsilon$-transitions and therefore is in the $\epsilon$-closure of $q_0$ with respect to $A_{\mathrm{𝗌𝗎𝗉}}$. Moreover, when a state $q$ is removed, it is never added back. Indeed, assume by contradiction that $q\notin S_{i-1}$ but $q$ gets added to $S_i$ by an update step. Then $q$ is not reachable from $S_{i-1}$ by $\epsilon$-transitions, but it is reachable from ${𝖢}_{w[i]}(S_{i-1})$ by $\epsilon$-transitions: this is impossible because in $A_{\mathrm{𝗌𝗎𝗉}}$ there is a transition $(p,\epsilon ,q)$ for every existing transition $(p,b,q)$ with $b\in \mathrm{\Sigma }$. Thus, $S_0\supseteq S_1\supseteq \mathrm{\dots }\supseteq S_{|w|}$.

This means that in the state-set simulation for $A_{\mathrm{𝗌𝗎𝖻}}$ and $A_{\mathrm{𝗌𝗎𝗉}}$ on an input string $w$, we can encounter at most $n+1$ different sets of active states. Further, for each set of active sets, there are at most $|\mathrm{\Sigma }|$ possible update steps necessary (since if ${𝖢}_{\epsilon }^{\ast }({𝖢}_{w[i+1]}(S_i))=S_i$ and $w[i+1]=w[j+1]$ and $S_i=S_j$ for some hold, then we do not need to update $S_j$). Every actual update can again be done in time $O(m)$, which yields the following:

This is already a significant improvement over Theorem 3.2, since the running time is linear in $|w|$. In the next two sections, we look deeper into the problem of subsequence and supersequence matching and manage to lower its complexity to the optimum of $O(|w|+m)$.

We prove the upper bounds of the different problem variants in the same way: We reduce $A$ and $w$ to a $\mathrm{\Sigma }\cup \{\epsilon \}$-labelled directed graph $G$ with edge weights of $0$ or $1$ and with a designated start vertex $s$ and target vertex $t$, such that the shortest or longest infix, prefix, extension, left-extension, subsequence and supersequence corresponds to a path from $s$ to $t$ with minimum or maximum weight, respectively, and the label of the path corresponds to the witness string (i. e., the infix, prefix, etc.) and its weight to the length of the witness string. By basic graph algorithmic techniques, it is not difficult to check in time $O(|G|)$ whether there is a path from $s$ to $t$ and if so, to compute such a path (along with its label) having minimum or maximum weight (or to report that the weight is unbounded for such paths). Since $O(|G|)=O(|w|m)$ for all our reductions, the $O(|w|m)$ upper bound follows. Let us in the following sketch the reductions for the different relations.

Let us just discuss the infix relation, since the prefix relation is similar. We can build in time $O(|w|m)$ the product graph $G_{A,w}$, which has vertices $\{0,\mathrm{\dots },|w|\}\times Q$ and edges as follows. For each transition $(q,\epsilon ,q^{\prime })$ in $A$ and for each $i\in \{0,\mathrm{\dots },|w|\}$, add an edge from $(i,q)$ to $(i,q^{\prime })$ in $G_{A,w}$ with label $\epsilon$ and weight $0$. For each transition $(q,b,q^{\prime })$ with $b\in \mathrm{\Sigma }$ and for each $i\in \{1,\mathrm{\dots },|w|\}$ with $w[i]=b$, add an edge from $(i-1,q)$ to $(i,q^{\prime })$ in $G_{A,w}$ with label $b$ and weight $1$.

To this product graph $G_{A,w}$ we add a source vertex $s$ with $\epsilon$-labelled edges with weight $0$ to $(i,q_0)$ for each $i\in \{0,\mathrm{\dots },|w|\}$ and a target vertex $t$ with $\epsilon$-labelled edges with weight $0$ from $(i,q_{𝖿})$ for each $i\in \{0,\mathrm{\dots },|w|\}$. It can now be seen that paths from $s$ to $t$ in $G$ are in one-to-one-correspondence with accepting runs of $A$ over the infixes of $G$, with the weight of the path being the length of the corresponding infix. As mentioned above, we can compute weight-minimum and -maximum paths from $s$ to $t$ along with their weights in time $O(|G|)=O(|w|m)$.

Let us only discuss the case of the extension relation, since the left-extension can be handled similarly (and is generally a bit simpler).

We build again the product graph $G_{A,w}$, but we also add to $G_{A,w}$ two graphs that are basically copies of the $\epsilon$NFA $A$. One such copy has vertices $\{q_{\leftarrow }\mid q\in Q\}$ and edges as follows: for each transition $(q,x,q^{\prime })$ in $A$ there is an edge from $q_{\leftarrow }$ to $q_{\leftarrow }^{\prime }$ labelled $x$ and having weight $0$ if $x=\epsilon$ and weight $1$ otherwise. The other copy has vertices $\{q_{\to }\mid q\in Q\}$ and is defined in exactly the same way as the first copy but replacing the “$\leftarrow$” subscripts by “$\to$” subscripts. Then, for each state $q\in Q$ we add an $\epsilon$-labelled edge with weight $0$ from $q_{\leftarrow }$ to $(0,q)$, and for each state $q^{\prime }\in Q$ we add an $\epsilon$-labelled edge with weight $0$ from $(|w|,q^{\prime })$ to $q_{\to }^{\prime }$. We call the resulting graph $G$ and we note that this construction can be done in time $O(|w|m)$. Let the source vertex $s$ of $G$ be ${(q_0)}_{\leftarrow }$ and let the target vertex $t$ of $G$ be ${(q_{𝖿})}_{\to }$.

Now, every path from $s$ to $t$ in $G$ can be decomposed in three parts: (1) a path from $s$ to $q_{\leftarrow }$ for some $q\in Q$, which is a path labelled with a string $v\in {\mathrm{\Sigma }}^{\ast }$, with weight $|v|$, and such that there is a run from $q_0$ to $q$ in $A$ when reading $v$; (2) a path from $(0,q)$ to $(|w|,q^{\prime })$ for some $q^{\prime }\in Q$, which is a path labelled by $w$, with weight $|w|$, and that is witnessing that there is a run from $q$ to $q^{\prime }$ in $A$ when reading $w$; (3) a path from ${(q^{\prime })}_{\to }$ to $t$ labelled with a string $v^{\prime }\in {\mathrm{\Sigma }}^{\ast }$, with weight $|v^{\prime }|$ and such that there is a run from $q^{\prime }$ to $q_{𝖿}$ in $A$ when reading $v^{\prime }$. Consequently, $vw{v}^{\prime }$ is an extension of $w$ accepted by $A$. Conversely, it can be seen that, for any strings $v,v^{\prime }\in {\mathrm{\Sigma }}^{\ast }$ such that the extension $vw{v}^{\prime }$ of $w$ is accepted by $A$, there must be a path in $G$ from $s$ to $t$ labelled with $vw{v}^{\prime }$ and with weight $|vw{v}^{\prime }|$.

Let us begin with the subsequence relation. We start with the product graph $G_{A,w}$ and add edges with weight $0$ and label $\epsilon$ from $(i,q)$ to $(i+1,q)$ for each state $q$ of $A$ and each . Let us call these additional edges extra-edges, and note that they mimic the self-loops $(q,b,q)$ for every $b\in \mathrm{\Sigma }$ added in the $\epsilon$NFA $A_{\mathrm{𝗌𝗎𝖻}}$ defined in Section 3, relative to the original $\epsilon$NFA $A$. However, note that we do not explicitly construct $A_{\mathrm{𝗌𝗎𝖻}}$, as we cannot afford within the time bound $O(|w|m)$. We call this graph $G$ and note that it can be constructed in time $O(|w|m)$. Let the source $s$ of $G$ be $(0,q_0)$ and let the target $t$ be $(|w|,q_{𝖿})$.

An accepting run of $A_{\mathrm{𝗌𝗎𝖻}}$ on $w$ that corresponds to a subsequence $u$ of $w$ (by the symbols read by the original transitions from $A$) translates into a path from $s$ to $t$ with label $u$ and weight $|u|$: Each transition $(q,x,q^{\prime })$ of the run that is an original transition of $A$ translates into a corresponding $x$-labelled edge of $G_{A,w}$ from $(i,q)$ to $(i+1,q^{\prime })$ or from $(i,q)$ to $(i,q^{\prime })$ (depending on whether $x\in \mathrm{\Sigma }$ or $x=\epsilon$), where $i$ depends on the length of the prefix of $w$ already consumed; and each loop-transition $(q,b,q)$ that is added to $A$ in the construction of $A_{\mathrm{𝗌𝗎𝖻}}$ translates into an extra-edge from $(i,q)$ to $(i+1,q)$. Conversely, any path from $s$ to $t$ with label $u$ and weight $|u|$ translates into an accepting run of $A_{\mathrm{𝗌𝗎𝖻}}$ on $w$ such that its original transitions of $A$ read exactly $u$, which therefore must be a subsequence of $w$.

For the supersequence relation, the reduction is slightly different. We start again with the product graph $G_{A,w}$, but now we add for each transition $(q,b,q^{\prime })$ in $A$ with $b\in \mathrm{\Sigma }$ and each $i\in \{0,\mathrm{\dots },|w|\}$ a $b$-labelled edge with weight $1$ from $(i,q)$ to $(i,q^{\prime })$. Now, these extra-edges mimic the $\epsilon$-transitions added in the $\epsilon$NFA $A_{\mathrm{𝗌𝗎𝗉}}$ defined in Section 3, relative to the original $\epsilon$NFA $A$. We note that for any $\epsilon$-transition $(q,\epsilon ,q^{\prime })$ of $A_{\mathrm{𝗌𝗎𝗉}}$ that is not a transition of $A$, there are several (and at least one) transitions $(q,b,q^{\prime })$ with $b\in \mathrm{\Sigma }$ in $A$; thus, there are also several (and at least one) extra-edges from $(i,q)$ to $(i,q^{\prime })$ that differ in their labels.

Similar as in the subsequence-case, the paths from $s$ to $t$ in $G$ correspond to accepting runs of $A_{\mathrm{𝗌𝗎𝗉}}$ on $w$, where the label of the path is the supersequence $u$ of $w$ induced by the accepting run and its weight is $|u|$. The original transitions of $A$ translate into edges of $G_{A,w}$ as before, but every transition $(q,\epsilon ,q^{\prime })$ of $A_{\mathrm{𝗌𝗎𝗉}}$ that is not a transition of $A$ translates into an extra-edge from $(i,q)$ to $(i,q^{\prime })$ of $G$ (where $i$ again depends on the length of the prefix of $w$ that has already been consumed). As observed above, there might be several extra-edges from $(i,q)$ to $(i,q^{\prime })$ that differ in their labels; we just take any of those (in fact, this decision only affects the symbols of the subsequence $u$ that do not belong to $w$, but not its length). Also note that unlike in the subsequence case, extra-edges have now weight $1$, since they correspond to symbols of the supersequence of $w$ (while in the subsequence-case they correspond to symbols of $w$ that do not belong to its accepted subsequence $u$).

Checking whether all prefixes of a string are accepted by an automaton can be easily done via state-set simulation, and checking the same for all infixes can be done similarly by running a state-set simulation from every starting position. Let us show why the cases of the relations ${⪯}_{\mathrm{𝖾𝗑𝗍}},{⪯}_{\mathrm{𝗅𝖾𝗑𝗍}},{⪯}_{\mathrm{𝗌𝗎𝖻}}$ and ${⪯}_{\mathrm{𝗌𝗎𝗉}}$ follow from known facts about finite automata.

The PSPACE upper bound with respect to ${⪯}_{\mathrm{𝖾𝗑𝗍}}$ follows from the fact that ${\mathrm{\Lambda }}_{{⪯}_{\mathrm{𝖾𝗑𝗍}}}(w)$ can be expressed by an $\epsilon$NFA, and $\epsilon$NFA-inclusion can be decided in PSPACE. The reasoning is analogous for ${⪯}_{\mathrm{𝗅𝖾𝗑𝗍}}$. The same argument shows PSPACE membership for ${⪯}_{\mathrm{𝗌𝗎𝗉}}$ by building an $\epsilon$NFA accepting the supersequences of $w$. The ${⪯}_{\mathrm{𝗌𝗎𝖻}}$-variant is in coNP, since we can guess a subsequence of $w$ and check acceptance for it.

The PSPACE-hardness with respect to ${⪯}_{\mathrm{𝖾𝗑𝗍}}$, ${⪯}_{\mathrm{𝗅𝖾𝗑𝗍}}$ and ${⪯}_{\mathrm{𝗌𝗎𝗉}}$ is easy to see: For $w=\epsilon$, these problems are equivalent to $\epsilon$NFA-universality, i. e., checking whether $𝖫(A)={\mathrm{\Sigma }}^{\ast }$, which is PSPACE-hard. This leaves the coNP-hardness for ${⪯}_{\mathrm{𝗌𝗎𝖻}}$, which can be shown as follows. For a $3$-CNF formula $F$ over $n$ variables we build an $\epsilon$NFA $A_F$ that accepts all $\{0,1\}$-strings of length $k\in \{1,2,\mathrm{\dots },n-1,n+1,\mathrm{\dots },2n\}$ and all $\{0,1\}$-strings of length $n$ that represent non-satisfying assignments of $F$. Then, ${\mathrm{\Lambda }}_{{⪯}_{\mathrm{𝗌𝗎𝖻}}}({(01)}^n)\subseteq 𝖫(A_F)$ if and only if $F$ is not satisfiable. $◀$

We first observe that SETH-based lower bounds for the ${⪯}_{\mathrm{𝗂𝗇}}$-, ${⪯}_{\mathrm{𝗉𝗋𝖾}}$-, ${⪯}_{\mathrm{𝖾𝗑𝗍}}$- and ${⪯}_{\mathrm{𝗅𝖾𝗑𝗍}}$-matching problem can be concluded by minor adaptions of the original construction from [9]. Moreover, since the min- and max-variants also solve the non-quantitative version of the matching problem, we can conclude that these lower bounds also hold for the quantitative variants:

Further, we can show that the $O(|w|m)$ upper bound for the universal variant of the matching problem for the prefix or infix relation is also optimal under SETH. The construction can be sketched as follows. For a string $w$ and $\epsilon$NFA $A$, we build an $\epsilon$NFA $A^{\prime }$ with $𝖫(A^{\prime })=(\{\mathrm{\#}\}\cdot 𝖫(A)\cdot \{\mathrm{\#}\})\cup (\{\mathrm{\#}\}\cdot {\mathrm{\Sigma }}^{\ast })\cup ({\mathrm{\Sigma }}^{\ast }\cdot \{\mathrm{\#}\})\cup {\mathrm{\Sigma }}^{\ast }$ for a fresh symbol $\mathrm{\#}$. It is not hard to see that $w\in 𝖫(A)\iff {\mathrm{\Lambda }}_{{⪯}_{\mathrm{𝗂𝗇}}}(\mathrm{\#}w\mathrm{\#})\subseteq 𝖫(A^{\prime })$. Hence, the universal variant of the ${⪯}_{\mathrm{𝗂𝗇}}$-matching problem reduces to the normal ${⪯}_{\mathrm{𝗂𝗇}}$-matching problem, so that the lower bounds of Theorem 7.1 apply. The case of ${⪯}_{\mathrm{𝗉𝗋𝖾}}$ is very similar. We therefore have: