Matching statistics were introduced to solve the approximate string matching problem, which is a recurrent subroutine in bioinformatics applications. In 2010, Ohlebusch et al. [SPIRE 2010] proposed a time and space efficient algorithm for computing matching statistics which relies on some components of a compressed suffix tree - notably, the longest common prefix (LCP) array. In this paper, we show how their algorithm can be generalized from strings to Wheeler deterministic finite automata. Most importantly, we introduce a notion of LCP array for Wheeler automata, thus establishing a first clear step towards extending (compressed) suffix tree functionalities to labeled graphs.

Wheeler DFAs (WDFAs) are a sub-class of finite-state automata which is playing an important role in the emerging field of compressed data structures: as opposed to general automata, WDFAs can be stored in just$\log\sigma+O(1)$bits per edge,$\sigma$being the alphabet's size, and support optimal-time pattern matching queries on the substring closure of the language they recognize. An important step to achieve further compression is minimization. When the input$\mathcal{A}$is a general deterministic finite-state automaton (DFA), the state-of-the-art is represented by the classic Hopcroft's algorithm, which runs in$O(\vert \mathcal{A}\vert \log\vert \mathcal{A}\vert )$time. This algorithm stands at the core of the only existing minimization algorithm for Wheeler DFAs, which inherits its complexity. In this work, we show that the minimum WDFA equivalent to a given input WDFA can be computed in linear$O(\vert \mathcal{A}\vert )$time. When run on de Bruijn WDFAs built from real DNA datasets, an implementation of our algorithm reduces the number of nodes from 14% to 51% at a speed of more than 1 million nodes per second.

For the first time we provide a succinct pattern matching index for arbitrary graphs that can be built 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$\vert E/_{\leq G}\vert (\lceil\log\vert \Sigma\vert \rceil+\lceil\log q\rceil+2)\cdot(1+o(1))+\vert V/_{\leq G}\vert \cdot(1+o(1))$bits which supports pattern matching on$G$in$O(\vert P\vert \cdot q^{2}\cdot\log(q\cdot\vert \Sigma\vert))$time, where$G/_{\leq G}=(V/_{\leq G}, E/_{\leq G})$is a quotient graph obtained by collapsing some nodes in$G$and$q$is the width of the 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.