Graphs can be succinctly indexed for pattern matching in O(E^2 + V^{2.5}) time

Citation Author(s):
Nicola Cotumaccio
Submitted by:
Nicola Cotumaccio
Last updated:
5 March 2022 - 10:01am
Document Type:
Presentation Slides
Event:
Presenters:
Nicola Cotumaccio
Categories:
Keywords:

Abstract

For the first time we provide a \emph{succinct} pattern matching index for \emph{arbitrary} graphs that can be built \emph{in polynomial time}, while improving both space and query time bounds from [SODA 2021]. We show that, given an edge-labeled graph $G = (V, E)$, there exists a data structure of $|E /_{\le_G}|(\lceil \log|\Sigma|\rceil + \lceil\log q\rceil + 2)\cdot (1+o(1)) + |V /_{\le_G}|\cdot (1+o(1))$ bits which supports pattern matching on $G$ in $O(|P| \cdot q^2 \cdot \log(q\cdot |\Sigma|))$ time, where $G /_{\le_G} = (V /_{\le_G}, E /_{\le_G})$ is a quotient graph obtained by collapsing some nodes in $G$ and $q$ is the width of the \emph{maximum} co-lex relation on $G$.
Our results have relevant applications in automata theory: we can use our data structure to decide whether a string belongs to the language recognized by a given automaton, and we can capture the degree of nondeterminism of an NFA.

Graphs can be succinctly indexed for pattern matching in O(E^2 + V^{2.5}) time.pdf

Files

Graphs can be succinctly indexed for pattern matching in O(E^2 + V^{2.5}) time.pdf

(63)