4 papers
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 (co-lex) Ordering Automata
Giovanna D'Agostino, Nicola Cotumaccio, Alberto Policriti +1
The states of a deterministic finite automaton A can be identified with collections of words in Pf(L(A)) -- the set of prefixes of words belonging to the regular language accepted…
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…