<p>Consider the following setup. Let <span class="math-container">$s$</span> be a string in the pattern <code>&lt;w1&gt;&lt;w2&gt;...</code> for words <span class="math-container">$w_1, w_2, \dots$</span> that don't include <code>&lt;&gt;</code> in their alphabet. Now with the regex <code>.*&lt;w&gt;.*</code> we can check the existence of a word in the 'database' <span class="math-container">$s$</span>. Better yet, we can substitute arbitrary characters of <span class="math-container">$w$</span> with a wildcard symbol <code>.</code>.</p>
<p>This gives a reduction from <a href="https://dl.acm.org/doi/abs/10.1145/301250.301330" rel="nofollow noreferrer"><em>Lower bounds for high dimensional nearest neighbor search and related problems</em></a> by Borodin et. al. where it's shown that constant time queries with polynomial space is impossible.</p>
<p>A stronger conjecture is provided, which would answer your question negatively altogether:</p>
<blockquote>
<p>The common “wisdom” among researchers is that simultaneously getting <span class="math-container">$poly(nd)$</span> storage and <span class="math-container">$poly(d)$</span> search time is impossible. Moreover, it has been conjectured that either storage or search time must grow exponentially in <span class="math-container">$d$</span> (at least for certain values of <span class="math-container">$n$</span>). This conjecture is known as the curse of dimensionality[19].</p>
<p>[19] K. Clarkson.  An algorithm for approximate closest-point queries.  In Proc. of 10th SCG, pp.160–164, 1994.</p>
</blockquote>
<p>Here <span class="math-container">$n$</span> is the number of strings and <span class="math-container">$d$</span> is the size of each string, thus <span class="math-container">$nd \sim |s|$</span>.</p>

CC BY-SA 4.0
2021-06-17T08:32:53.710Z
Should "reduction to" be "reduction from" in this answer?
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2021-06-17T09:02:47.277Z
@a3nm Yes, I always confuse the two :( The thing that you're reducing *from* is usually the *goal* of your argument, so in my mind it's our destination, and I'm likely to use 'to' wrong.
orlp
CC BY-SA 4.0
2021-06-14T12:23:07.507Z
2021-06-17T09:01:43.690Z
2021-06-17T09:01:43.690Z
orlp
<p>It seems to me that your problem is very close to pattern matching in compressed text, which is an active area of research. It consists in searching given patterns in compressed strings, without decompressing them. It is then faster than parsing the strings.</p>
<p>I am not an expert, but the following seems to be a good reference:
<em><a href="https://doi.org/10.1016/j.jda.2003.12.002" rel="nofollow noreferrer">Practical and flexible pattern matching over Ziv–Lempel compressed text</a></em> by Gonzalo Navarro and Mathieu Raffinot.</p>

CC BY-SA 4.0
2021-06-15T07:02:15.740Z
2021-06-15T13:49:23.230Z
2021-06-15T13:49:23.230Z
Matthieu Latapy
<p>I think this works:</p>
<p>The basic idea is that after reading <span class="math-container">$p\overset{u}{\to}q$</span> and <span class="math-container">$q\overset{v}{\to}r$</span> in the automaton, we add a transition <span class="math-container">$p\overset{u\cdot v}{\to}r$</span>. Of course, we need to avoid testing equality of strings because that would already be too slow. This is where the DAG factorization comes in.</p>
<p>I write <span class="math-container">$\Sigma$</span> for the alphabet, call the input word / string <span class="math-container">$s\in \Sigma^*$</span>, and use a non-deterministic finite automaton <span class="math-container">$\mathcal A=(Q, \Sigma, \Delta, I, F)$</span> instead of the regular expression.</p>
<p><strong>Precomputation: Computing a DAG factorization of <span class="math-container">$s$</span></strong></p>
<p>A <em>tree factorization</em> is a finite (binary) tree (with a linear order on the children of each node) whose leaves are labeled by letters of the alphabet. Each node <span class="math-container">$n$</span> in a tree factorization <span class="math-container">$T$</span> represents a word <span class="math-container">$u_n$</span> defined as follows:</p>
<ul>
<li><p>If <span class="math-container">$n$</span> is a leaf labeled with the letter <span class="math-container">$a$</span> then <span class="math-container">$u_n=a$</span>;</p>
</li>
<li><p>If <span class="math-container">$n$</span> is an internal node with children <span class="math-container">$n_1$</span> and <span class="math-container">$n_2$</span> then <span class="math-container">$u_n=u_{n_1}\cdot u_{n_2}$</span> where <span class="math-container">$\cdot$</span> denotes concatenation.</p>
</li>
</ul>
<p>While it is slightly easier to reason about tree factorizations, to get a fast algorithm, we instead use a DAG (i.e. directed acyclic graph) factorization where children can be shared by several parents. A <em>DAG factorization</em> is a DAG (with a linear order on the successors of each node) such that has exactly one source (i.e. one node with no incoming edge), and such that each sink (i.e. node with no outgoing edge) is labeled by a letter <span class="math-container">$a\in \Sigma$</span>.
Each node <span class="math-container">$n$</span> in a DAG factorization <span class="math-container">$T$</span> represents a word <span class="math-container">$u_n$</span> defined as follows:</p>
<ul>
<li><p>If <span class="math-container">$n$</span> is a sink labeled with the letter <span class="math-container">$a$</span> then <span class="math-container">$u_n=a$</span>;</p>
</li>
<li><p>It <span class="math-container">$n$</span> is not a sink and has children <span class="math-container">$n_1,\dots, n_j$</span>, then <span class="math-container">$u_n=u_{n_1}\cdot \dots \cdot u_{n_j}$</span>.</p>
</li>
</ul>
<p>A <em>DAG factorization</em> of a string <span class="math-container">$s$</span> is a DAG factorization <span class="math-container">$G$</span> such that its source <span class="math-container">$n$</span> represents the word <span class="math-container">$s$</span>, i.e. <span class="math-container">$u_n=s$</span>.</p>
<p>The precomputation is just computing a DAG factorization of <span class="math-container">$s$</span>, ideally the smallest possible. By <a href="https://math.stackexchange.com/a/4179041/10385">this answer</a>, we can build a DAG factorization <span class="math-container">$G$</span> based on a complete binary tree such that <span class="math-container">$$|G|=O\left(\frac{|s|}{\sqrt{\log |s|}}\right)$$</span> (where <span class="math-container">$|G|$</span> is the number of nodes in <span class="math-container">$G$</span>).</p>
<p>This of course assumes that the alphabet is fixed. If the alphabet is not fixed, we can take an alphabet of size <span class="math-container">$|s|$</span> to build a word whose letters are all different, and the size of any DAG factorization of this string would have to contain all those letters as leaves, and hence be at least linear in <span class="math-container">$|s|$</span>.</p>
<p>In the best case senario, <span class="math-container">$|G|$</span> is logarithmic in <span class="math-container">$|s|$</span>. For example, when <span class="math-container">$s=a^{2^k}$</span>, we can take a complete binary tree with nodes of depth <span class="math-container">$j$</span> labeled by <span class="math-container">$a^{2^j}$</span>.</p>
<hr />
<p><strong>Running an automaton on a DAG factorization</strong></p>
<p>Given a DAG factorization <span class="math-container">$G$</span> of <span class="math-container">$s\in \Sigma^*$</span>, and the input automaton <span class="math-container">$\mathcal A=(Q, \Sigma, \Delta, I, F)$</span>, the algorithm runs by associating a transition relation <span class="math-container">$\Delta_{n}\subseteq Q\times  Q$</span> to each node <span class="math-container">$n$</span> of <span class="math-container">$G$</span> such that for each <span class="math-container">$p$</span> and <span class="math-container">$n$</span>, <span class="math-container">$(p, u_n, q) \in \Delta^* \iff (p, q) \in \Delta_n$</span>, i.e. <span class="math-container">$\Delta_n$</span> relates <span class="math-container">$p$</span> and <span class="math-container">$q$</span> if we can get from <span class="math-container">$p$</span> to <span class="math-container">$q$</span> by reading <span class="math-container">$u_n$</span> in the automaton.</p>
<ul>
<li><p>For leaves, <span class="math-container">$\Delta_n=\Delta$</span>;</p>
</li>
<li><p>For internal nodes <span class="math-container">$n$</span> with children <span class="math-container">$n_1$</span> and <span class="math-container">$n_2$</span>, <span class="math-container">$$\Delta_n= \Delta_{n_1} ; \Delta_{n_2}=\{(p,r):\exists r, (p,q) \in \Delta_{n_1}\text{ and }(q,r) \in \Delta_{n_w}\}$$</span></p>
</li>
</ul>
<p>We represent those transitions relations by dictionaries. Checking whether <span class="math-container">$(p,q)\in \Delta_{n_1}$</span> and <span class="math-container">$(q,r)\in \Delta_{n_2}$</span> costs <span class="math-container">$O(\log |Q|^2)=O(\log |Q|)$</span>, so by iterating over all triplets <span class="math-container">$(p,q,r)$</span>, we can compute <span class="math-container">$\Delta_{n_1} ; \Delta_{n_2}$</span> in <span class="math-container">$O(|Q|^3\log |Q|)$</span>. Since we visit each node once, the total runtime is therefore <span class="math-container">$$O(|G|\times |Q|^3\log |Q|)$$</span></p>
<p>If the automaton is deterministic, we can replace the iteration over <span class="math-container">$(p,q,r)$</span> by an iteration over <span class="math-container">$p$</span>, so we get <span class="math-container">$$O(|G|\times |Q|\log |Q|)$$</span></p>
<hr />
<p><strong>Conclusion</strong></p>
<p>Given a fixed alphabet <span class="math-container">$\Sigma$</span>, and a word <span class="math-container">$s\in \Sigma^*$</span>, we precompute a DAG factorization <span class="math-container">$G$</span> of <span class="math-container">$s$</span> with a number of nodes <span class="math-container">$$|G|=O\left(\frac{|s|}{\sqrt{\log |s|}}\right)$$</span> Then, given a non-deterministic finite automaton <span class="math-container">$\mathcal A=(Q, \Sigma, \Delta, I, F)$</span>, we check whether <span class="math-container">$s$</span> is accepted, i.e. whether there exists <span class="math-container">$p\in I$</span> and <span class="math-container">$q\in F$</span> such that <span class="math-container">$(p,s,q)\in\Delta^*$</span>, by first computing <span class="math-container">$\Delta_n$</span> in time <span class="math-container">$$O(|G|\times |Q|^3\log |Q|)$$</span> and then checking whether there exists <span class="math-container">$p\in I$</span> and <span class="math-container">$q\in F$</span> such that <span class="math-container">$(p,q)\in\Delta_n$</span> in time <span class="math-container">$O(|I|\times |F|\times \log |Q|)$</span>. Since <span class="math-container">$|G|$</span> is sublinear in <span class="math-container">$|s|$</span>, we get a total complexity sublinear in <span class="math-container">$|s|$</span>:<span class="math-container">$$O\left(\frac{|s|}{\sqrt{\log |s|}}\times |Q|^3\log |Q|\right)$$</span></p>

CC BY-SA 4.0
2021-06-22T01:56:06.993Z
What do you mean the induced tree of a DAG?  There might be multiple trees.  Do you require that all trees that are induced from the graph are tree factorizations?
D.W.
CC BY-SA 4.0
2021-06-22T11:16:37.550Z
@D.W. To get a unique induced tree, a DAG is indeed not enough, but asking for a unique source should make the induced tree unique. I redefined DAG factorization directly to make things clearer.
xavierm02
CC BY-SA 4.0
2021-07-04T19:20:24.713Z
That's a pretty fun argument, but sorry I'm just missing something. The answer https://math.stackexchange.com/a/4179041 shows that there is a DAG factorization of the size that you claim, but I'm not sure of how you would actually construct the factorization -- given that as you say testing equality can be costly. Is it obvious how efficiently the DAG factorization can indeed be built? (That said it's true that the question asked for "polynomial-time precomputation" so I guess it's clear you could do it if you don't care about the polynomial degree.)
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2021-07-05T13:10:43.087Z
@a3nm What I mean by equality testing being costly is that if you test equality of some strings whose length is of the same order of magnitude as $|s|$, then you can't be sublinear, but the precomputation does not need to be sublinear so we can test string equality during the precomputation. To build the DAG for a word of size $2^k$, you can start by building the tree factorization that always splits the word in two subwords of equal size. Then, initialize a union-find structure on the nodes and mark two leaves as equivalent whenever they have the same letter
xavierm02
CC BY-SA 4.0
2021-07-05T13:32:32.767Z
Then, build a matrix $A$ such that $A[d][j]$ is the equivalence class of the $j^\text{th}$ node at depth $d$.  Then, for each $j$ in decreasing order, sort $A[d]$ according to the lexicographical order pairs of the equivalence class of the left child, and the equivalence class of the right child. (This may require adding an integer label to the roots in the union-find structure in some languages, but in others the physical address would do) Then, for each adjacent nodes in $A[d]$, mark them as equivalent in the union-find structure if they have equivalent left and right children.
xavierm02
CC BY-SA 4.0
2021-07-05T13:47:44.433Z
Finally, replace each node in the tree by its representant in the union-find structure. The cost of building the tree factorization $T$ is $O(|T|)$, i.e. $O(|s|\log |s|)$. The cost of building $A$ and the union-find structure is also $O(|T|)$ because it's $O(1)$ per node.  Since there are at most $2^d$ nodes of depths $d$, sorting $A[d]$ takes $O(2^d \times d)$ comparisons, and each comparison takes $O(\log (|T|^2))$, i.e. $O(\log (|T|))$, so we get $O(2^d \times d\times \log |T|)$. Merging by iterating over $A[d]$ takes $O(2^d \times \alpha(|T|))$.
xavierm02
CC BY-SA 4.0
2021-07-05T13:48:38.080Z
So in total, I think this yields $O(|s| \log |s| \log (|s| \log |s|))$.
xavierm02
CC BY-SA 4.0
2021-07-05T20:06:56.473Z
Thanks for the detailed explanation! Just wanted to check that the precomputation is not linear -- I agree it can be made close to linear. Just a simple thing I didn't understand in the argument -- why is $|T|$ in $O(|s| \log |s|)$? Isn't the initial $T$ (complete binary tree with $|s|$ leaves) of size $2|s|-1$, so $O(|s|)$?
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2021-07-05T21:53:06.077Z
@a3nm Yeah that's a mistake. Either I took a very loose approximation "width $\times$ height" because it did not change the total, or it's a missed copy-and-paste from the sorting complexity. And now that I look at it, the total complexity is probably better written $O(|s|(\log |s|)^2)$
xavierm02
CC BY-SA 4.0
2021-06-21T23:35:21.450Z
2021-06-22T11:18:00.267Z
2021-06-22T11:18:00.267Z
xavierm02
<p>Does there exist a data structure with the following properties. Given a string <span class="math-container">$s$</span>, it performs some polynomial amount of precomputation to construct the data structure. After construction, it allows searching <span class="math-container">$s$</span> for arbitrary regular expression patterns in time sublinear in the length of <span class="math-container">$s$</span>, ideally constant or logarithmic. Ideally, the runtime would only depend polynomially on the length of the regex pattern being searched. Is anything known about this? If not, what is the closest one can come?</p>

CC BY-SA 4.0
2021-06-11T16:36:07.757Z
I don't see how you could test equality of a string to another fixed string in time sublinear in the size of the fixed string, and your problem seems to reduce to this when the regular expression only contains symbols of the alphabet. Am I missing something?
xavierm02
CC BY-SA 4.0
2021-06-11T20:03:31.427Z
@xavierm02, yes, I think you are missing something.  The poster would be satisfied with an algorithm whose running time is $O(|p|)$ where $|p|$ is the length of the regexp pattern.  In your example, $|p|=|s|$, so such an algorithm would not contradict the obvious lower bound you are thinking of.
D.W.
CC BY-SA 4.0
2021-06-13T11:14:09.513Z
Right. I have the vague intuition that this could work: For each substring of $s$, add a new symbol that represents it, and let $f$ be the homomorphism that maps each new symbol to the corresponding substring of $s$, and maps the old symbols to themselves. Let $a$ be the symbol associated with the whole string, i.e. such that $f(a)=s$. The string $s$ is accepted by an automaton $A$ iff the reverse homomorphic image $B$ of $A$ by $f$ accepts $a$. Building $B$ explicitly is of course too long, but it seems plausible that we can build it lazily to solve the problem reasonably fast
xavierm02
CC BY-SA 4.0
2021-06-22T08:25:20.573Z
Would you be interested by a "PAC" version of this ? i.e. works w.h.p. when $s$ matches $p$ or is far from matching it.
GBathie
<ds.algorithms><ds.data-structures>
Sublinear Time Regular Expression Search
user62586
# Sublinear Time Regular Expression Search

(Asked by: username_0 on 2021-06-10)

Does there exist a data structure with the following properties. Given a string $s$, it performs some polynomial amount of precomputation to construct the data structure. After construction, it allows searching $s$ for arbitrary regular expression patterns in time sublinear in the length of $s$, ideally constant or logarithmic. Ideally, the runtime would only depend polynomially on the length of the regex pattern being searched. Is anything known about this? If not, what is the closest one can come?

**Tags:** ds.algorithms, ds.data-structures
> **Comments:**
> **username_1**: I don't see how you could test equality of a string to another fixed string in time sublinear in the size of the fixed string, and your problem seems to reduce to this when the regular expression only contains symbols of the alphabet. Am I missing something?  
> **username_2**: @xavierm02, yes, I think you are missing something.  The poster would be satisfied with an algorithm whose running time is $O(|p|)$ where $|p|$ is the length of the regexp pattern.  In your example, $|p|=|s|$, so such an algorithm would not contradict the obvious lower bound you are thinking of.  
> **username_1**: Right. I have the vague intuition that this could work: For each substring of $s$, add a new symbol that represents it, and let $f$ be the homomorphism that maps each new symbol to the corresponding substring of $s$, and maps the old symbols to themselves. Let $a$ be the symbol associated with the whole string, i.e. such that $f(a)=s$. The string $s$ is accepted by an automaton $A$ iff the reverse homomorphic image $B$ of $A$ by $f$ accepts $a$. Building $B$ explicitly is of course too long, but it seems plausible that we can build it lazily to solve the problem reasonably fast  
> **username_3**: Would you be interested by a "PAC" version of this ? i.e. works w.h.p. when $s$ matches $p$ or is far from matching it.  

---

## 3 answers

### Answer by username_4 on 2021-06-14. Score: 8

Consider the following setup. Let $s$ be a string in the pattern `...` for words $w\_1, w\_2, \dots$ that don't include `<>` in their alphabet. Now with the regex `.*.*` we can check the existence of a word in the 'database' $s$. Better yet, we can substitute arbitrary characters of $w$ with a wildcard symbol `.`.

This gives a reduction from [*Lower bounds for high dimensional nearest neighbor search and related problems*](https://dl.acm.org/doi/abs/10.1145/301250.301330) by Borodin et. al. where it's shown that constant time queries with polynomial space is impossible.

A stronger conjecture is provided, which would answer your question negatively altogether:

> The common “wisdom” among researchers is that simultaneously getting $poly(nd)$ storage and $poly(d)$ search time is impossible. Moreover, it has been conjectured that either storage or search time must grow exponentially in $d$ (at least for certain values of $n$). This conjecture is known as the curse of dimensionality[19].
>
> [19] K. Clarkson. An algorithm for approximate closest-point queries. In Proc. of 10th SCG, pp.160–164, 1994.

Here $n$ is the number of strings and $d$ is the size of each string, thus $nd \sim |s|$.

> **Comments:**
> **username_5**: Should "reduction to" be "reduction from" in this answer?  
> **username_4**: @a3nm Yes, I always confuse the two :( The thing that you're reducing *from* is usually the *goal* of your argument, so in my mind it's our destination, and I'm likely to use 'to' wrong.  

---

### Answer by username_6 on 2021-06-15. Score: 3

It seems to me that your problem is very close to pattern matching in compressed text, which is an active area of research. It consists in searching given patterns in compressed strings, without decompressing them. It is then faster than parsing the strings.

I am not an expert, but the following seems to be a good reference:
*[Practical and flexible pattern matching over Ziv–Lempel compressed text](https://doi.org/10.1016/j.jda.2003.12.002)* by Gonzalo Navarro and Mathieu Raffinot.


---

### Answer by username_1 on 2021-06-21. Score: 1

I think this works:

The basic idea is that after reading $p\overset{u}{\to}q$ and $q\overset{v}{\to}r$ in the automaton, we add a transition $p\overset{u\cdot v}{\to}r$. Of course, we need to avoid testing equality of strings because that would already be too slow. This is where the DAG factorization comes in.

I write $\Sigma$ for the alphabet, call the input word / string $s\in \Sigma^\*$, and use a non-deterministic finite automaton $\mathcal A=(Q, \Sigma, \Delta, I, F)$ instead of the regular expression.

**Precomputation: Computing a DAG factorization of $s$**

A *tree factorization* is a finite (binary) tree (with a linear order on the children of each node) whose leaves are labeled by letters of the alphabet. Each node $n$ in a tree factorization $T$ represents a word $u\_n$ defined as follows:

* If $n$ is a leaf labeled with the letter $a$ then $u\_n=a$;
* If $n$ is an internal node with children $n\_1$ and $n\_2$ then $u\_n=u\_{n\_1}\cdot u\_{n\_2}$ where $\cdot$ denotes concatenation.

While it is slightly easier to reason about tree factorizations, to get a fast algorithm, we instead use a DAG (i.e. directed acyclic graph) factorization where children can be shared by several parents. A *DAG factorization* is a DAG (with a linear order on the successors of each node) such that has exactly one source (i.e. one node with no incoming edge), and such that each sink (i.e. node with no outgoing edge) is labeled by a letter $a\in \Sigma$.
Each node $n$ in a DAG factorization $T$ represents a word $u\_n$ defined as follows:

* If $n$ is a sink labeled with the letter $a$ then $u\_n=a$;
* It $n$ is not a sink and has children $n\_1,\dots, n\_j$, then $u\_n=u\_{n\_1}\cdot \dots \cdot u\_{n\_j}$.

A *DAG factorization* of a string $s$ is a DAG factorization $G$ such that its source $n$ represents the word $s$, i.e. $u\_n=s$.

The precomputation is just computing a DAG factorization of $s$, ideally the smallest possible. By [this answer](https://math.stackexchange.com/a/4179041/10385), we can build a DAG factorization $G$ based on a complete binary tree such that $$|G|=O\left(\frac{|s|}{\sqrt{\log |s|}}\right)$$ (where $|G|$ is the number of nodes in $G$).

This of course assumes that the alphabet is fixed. If the alphabet is not fixed, we can take an alphabet of size $|s|$ to build a word whose letters are all different, and the size of any DAG factorization of this string would have to contain all those letters as leaves, and hence be at least linear in $|s|$.

In the best case senario, $|G|$ is logarithmic in $|s|$. For example, when $s=a^{2^k}$, we can take a complete binary tree with nodes of depth $j$ labeled by $a^{2^j}$.

---

**Running an automaton on a DAG factorization**

Given a DAG factorization $G$ of $s\in \Sigma^\*$, and the input automaton $\mathcal A=(Q, \Sigma, \Delta, I, F)$, the algorithm runs by associating a transition relation $\Delta\_{n}\subseteq Q\times Q$ to each node $n$ of $G$ such that for each $p$ and $n$, $(p, u\_n, q) \in \Delta^\* \iff (p, q) \in \Delta\_n$, i.e. $\Delta\_n$ relates $p$ and $q$ if we can get from $p$ to $q$ by reading $u\_n$ in the automaton.

* For leaves, $\Delta\_n=\Delta$;
* For internal nodes $n$ with children $n\_1$ and $n\_2$, $$\Delta\_n= \Delta\_{n\_1} ; \Delta\_{n\_2}=\{(p,r):\exists r, (p,q) \in \Delta\_{n\_1}\text{ and }(q,r) \in \Delta\_{n\_w}\}$$

We represent those transitions relations by dictionaries. Checking whether $(p,q)\in \Delta\_{n\_1}$ and $(q,r)\in \Delta\_{n\_2}$ costs $O(\log |Q|^2)=O(\log |Q|)$, so by iterating over all triplets $(p,q,r)$, we can compute $\Delta\_{n\_1} ; \Delta\_{n\_2}$ in $O(|Q|^3\log |Q|)$. Since we visit each node once, the total runtime is therefore $$O(|G|\times |Q|^3\log |Q|)$$

If the automaton is deterministic, we can replace the iteration over $(p,q,r)$ by an iteration over $p$, so we get $$O(|G|\times |Q|\log |Q|)$$

---

**Conclusion**

Given a fixed alphabet $\Sigma$, and a word $s\in \Sigma^\*$, we precompute a DAG factorization $G$ of $s$ with a number of nodes $$|G|=O\left(\frac{|s|}{\sqrt{\log |s|}}\right)$$ Then, given a non-deterministic finite automaton $\mathcal A=(Q, \Sigma, \Delta, I, F)$, we check whether $s$ is accepted, i.e. whether there exists $p\in I$ and $q\in F$ such that $(p,s,q)\in\Delta^\*$, by first computing $\Delta\_n$ in time $$O(|G|\times |Q|^3\log |Q|)$$ and then checking whether there exists $p\in I$ and $q\in F$ such that $(p,q)\in\Delta\_n$ in time $O(|I|\times |F|\times \log |Q|)$. Since $|G|$ is sublinear in $|s|$, we get a total complexity sublinear in $|s|$:$$O\left(\frac{|s|}{\sqrt{\log |s|}}\times |Q|^3\log |Q|\right)$$

> **Comments:**
> **username_2**: What do you mean the induced tree of a DAG?  There might be multiple trees.  Do you require that all trees that are induced from the graph are tree factorizations?  
> **username_1**: @D.W. To get a unique induced tree, a DAG is indeed not enough, but asking for a unique source should make the induced tree unique. I redefined DAG factorization directly to make things clearer.  
> **username_5**: That's a pretty fun argument, but sorry I'm just missing something. The answer https://math.stackexchange.com/a/4179041 shows that there is a DAG factorization of the size that you claim, but I'm not sure of how you would actually construct the factorization -- given that as you say testing equality can be costly. Is it obvious how efficiently the DAG factorization can indeed be built? (That said it's true that the question asked for "polynomial-time precomputation" so I guess it's clear you could do it if you don't care about the polynomial degree.)  
> **username_1**: @a3nm What I mean by equality testing being costly is that if you test equality of some strings whose length is of the same order of magnitude as $|s|$, then you can't be sublinear, but the precomputation does not need to be sublinear so we can test string equality during the precomputation. To build the DAG for a word of size $2^k$, you can start by building the tree factorization that always splits the word in two subwords of equal size. Then, initialize a union-find structure on the nodes and mark two leaves as equivalent whenever they have the same letter  
> **username_1**: Then, build a matrix $A$ such that $A[d][j]$ is the equivalence class of the $j^\text{th}$ node at depth $d$.  Then, for each $j$ in decreasing order, sort $A[d]$ according to the lexicographical order pairs of the equivalence class of the left child, and the equivalence class of the right child. (This may require adding an integer label to the roots in the union-find structure in some languages, but in others the physical address would do) Then, for each adjacent nodes in $A[d]$, mark them as equivalent in the union-find structure if they have equivalent left and right children.  
> **username_1**: Finally, replace each node in the tree by its representant in the union-find structure. The cost of building the tree factorization $T$ is $O(|T|)$, i.e. $O(|s|\log |s|)$. The cost of building $A$ and the union-find structure is also $O(|T|)$ because it's $O(1)$ per node.  Since there are at most $2^d$ nodes of depths $d$, sorting $A[d]$ takes $O(2^d \times d)$ comparisons, and each comparison takes $O(\log (|T|^2))$, i.e. $O(\log (|T|))$, so we get $O(2^d \times d\times \log |T|)$. Merging by iterating over $A[d]$ takes $O(2^d \times \alpha(|T|))$.  
> **username_1**: So in total, I think this yields $O(|s| \log |s| \log (|s| \log |s|))$.  
> **username_5**: Thanks for the detailed explanation! Just wanted to check that the precomputation is not linear -- I agree it can be made close to linear. Just a simple thing I didn't understand in the argument -- why is $|T|$ in $O(|s| \log |s|)$? Isn't the initial $T$ (complete binary tree with $|s|$ leaves) of size $2|s|-1$, so $O(|s|)$?  
> **username_1**: @a3nm Yeah that's a mistake. Either I took a very loose approximation "width $\times$ height" because it did not change the total, or it's a missed copy-and-paste from the sorting complexity. And now that I look at it, the total complexity is probably better written $O(|s|(\log |s|)^2)$  

---

