5 papers
A Myhill-Nerode Theorem for Generalized Automata, with Applications to Pattern Matching and Compression
Nicola Cotumaccio
The model of generalized automata, introduced by Eilenberg in 1974, allows representing a regular language more concisely than conventional automata by allowing edges to be labeled…
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…
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…