The recently introduced class of Wheeler graphs, inspired by the Burrows-Wheeler
Transform (BWT) of a given string, admits an efficient index data structure for searching for …

We pose the fine-grained hardness hypothesis that the textbook algorithm for the NFA
Acceptance problem is optimal up to subpolynomial factors, even for dense NFAs and fixed …

The states of a finite-state automaton 𝒩 can be identified with collections of words in the
prefix closure of the regular language accepted by 𝒩. But words can be ordered, and among …

The problem of aligning a sequence to a walk in a labeled graph is of fundamental
importance to Computational Biology. For an arbitrary graph G=(V, E) and a pattern P of …

In recent years, several compressed indexes based on variants of the Burrows–Wheeler
transform have been introduced. Some of these are used to index structures far more …

Suffix trees are an important data structure at the core of optimal solutions to many
fundamental string problems, such as exact pattern matching, longest common substring …

Exact string matching in labeled graphs is the problem of searching paths of a graph G=(V,
E) such that the concatenation of their node labels is equal to a given pattern string P [1. m] …

Motivation Aligning reads to a variation graph is a standard task in pangenomics, with
downstream applications such as improving variant calling. While the vg toolkit [Garrison et …

Aligning a sequence to a walk in a labeled graph is a problem of fundamental importance to
Computational Biology. For finding a walk in an arbitrary graph with| E| edges that exactly …

The problem of matching (exactly or approximately) a pattern P to a walk in an edge labeled
graph G=(V, E), denoted PMLG, has received increased attention in recent years. Here we …