10 papers · 1 filter
Fast Pattern Matching with Epsilon Transitions
Nicola Cotumaccio
In the String Matching in Labeled Graphs (SMLG) problem, we need to determine whether a pattern string appears on a given labeled graph or a given automaton. Under the Orthogonal V…
Improved Circular Dictionary Matching
Nicola Cotumaccio
The circular dictionary matching problem is an extension of the classical dictionary matching problem where every string in the dictionary is interpreted as a circular string: afte…
Encoding Co-Lex Orders of Finite-State Automata in Linear Space
Ruben Becker, Nicola Cotumaccio, Sung-Hwan Kim +2
The Burrows-Wheeler transform (BWT) is a string transformation that enhances string indexing and compressibility. Cotumaccio and Prezza [SODA '21] extended this transformation to n…
Enhanced Graph Pattern Matching
Nicola Cotumaccio
Pattern matching queries on strings can be solved in linear time by Knuth-Morris-Pratt (KMP) algorithm. In 1973, Weiner introduced the suffix tree of a string [FOCS 1973] and showe…
Space-time Trade-offs for the LCP Array of Wheeler DFAs
Nicola Cotumaccio, Travis Gagie, Dominik Köppl +1
Recently, Conte et al. generalized the longest-common prefix (LCP) array from strings to Wheeler DFAs, and they showed that it can be used to efficiently determine matching statist…
Prefix Sorting DFAs: a Recursive Algorithm
Nicola Cotumaccio
In the past thirty years, numerous algorithms for building the suffix array of a string have been proposed. In 2021, the notion of suffix array was extended from strings to DFAs, a…
Computing matching statistics on Wheeler DFAs
Alessio Conte, Nicola Cotumaccio, Travis Gagie +3
Matching statistics were introduced to solve the approximate string matching problem, which is a recurrent subroutine in bioinformatics applications. In 2010, Ohlebusch et al. [SPI…
Graphs can be succinctly indexed for pattern matching in time
Nicola Cotumaccio
For the first time we provide a succinct pattern matching index for arbitrary graphs that can be built in polynomial time, which requires less space and answers queries more effici…
Linear-time Minimization of Wheeler DFAs
Jarno Alanko, Nicola Cotumaccio, Nicola Prezza
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…
On Indexing and Compressing Finite Automata
Nicola Cotumaccio, Nicola Prezza
An index for a finite automaton is a powerful data structure that supports locating paths labeled with a query pattern, thus solving pattern matching on the underlying regular lang…