REVIEW 5 cited by
Suffixient Sets
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
abstract
We define a suffixient set for a text $T [1..n]$ to be a set $S$ of positions between 1 and $n$ such that, for any edge descending from a node $u$ to a node $v$ in the suffix tree of $T$, there is an element $s \in S$ such that $u$'s path label is a suffix of $T [1..s - 1]$ and $T [s]$ is the first character of $(u, v)$'s edge label. We first show there is a suffixient set of cardinality at most $2 \bar{r}$, where $\bar{r}$ is the number of runs in the Burrows-Wheeler Transform of the reverse of $T$. We then show that, given a straight-line program for $T$ with $g$ rules, we can build an $O (\bar{r} + g)$-space index with which, given a pattern $P [1..m]$, we can find the maximal exact matches (MEMs) of $P$ with respect to $T$ in $O (m \log (\sigma) / \log n + d \log n)$ time, where $\sigma$ is the size of the alphabet and $d$ is the number of times we would fully or partially descend edges in the suffix tree of $T$ while finding those MEMs.
Forward citations
Cited by 5 Pith papers
-
Comprehensive Analysis of Cellular Uplink Performance in a Dense Stadium Deployment
χ is reachable: every string admits an O(χ)-word substring-equation representation, computable in linear time, disproving the conjecture that χ is not reachable.
-
Solving Square-Submatrix Equation Systems
Any system of square-submatrix equality constraints on an m by n matrix can be solved in O(|E|+mn) time, giving optimal O(b+mn) decompression of 2D square macro schemes.
-
Testing Suffixient Sets
The authors introduce the SLPR array and use it to verify suffixiency and minimum suffixiency of a position subset in O(n) time.
-
Smallest Suffixient Sets: Effectiveness, Resilience, and Calculation
The smallest suffixient set size chi is bounded by twice the number of BWT runs, can be at most doubled by reversing the string, and is incomparable with most copy-paste repetitiveness measures.
-
Patching leaky tunnels in BWTs
A suffixient-set based index finds maximal exact matches in O(rho_P log m) time plus constant per suffix-tree edge, using O(rho_T + chi) space, when both text and pattern are run-length compressed.
Discussion (0). Continue with ORCID to comment.