My Presentations
In this page you can find a selection of presentations given by me
New Entropy Measures with Applications to the XBWT
Event: Workshop DSB 2026
Venue: Ca' Foscari University of Venice, Italy
Date: 18/02/2026
Description: Entropy quantifies the number of bits required to store objects under certain assumptions. While this is a well established concept for strings, in the context of tries the state-of-the-art regarding entropies is less developed. The standard trie worst-case entropy considers the tries with a fixed nodes and alphabet size, however it does not account for the symbol distribution. In this work, we introduce new entropy measures - worst-case and empirical - exploiting information on the edge-labels. We show their reachability through an extension of arithmetic coding to tries, as well as the design of efficient trie indexes compressed to their empirical entropy.
Analysing New Entropy Measures for Tries
Event: Conference SPIRE 2025
Venue: City St George's, University of London, United Kingdom
Date: 10/09/2025
Description: We introduce new entropy measures for tries taking into account the distribution of the edge labels. To do that, we computed the total number of tries with a given symbol distribution and we derived the corresponding worst-case entropy formula. We have also used this result to introduce an empirical entropy formula for tries. These entropy formulas can be easily reached through the XBWT in analogous way as happens for the FM-index of a string. We observe that the only (worst-case) entropy formula that existed before this work did not exploit any information concerning the distribution of the edge labels.
Encoding Co-Lex Orders of Finite-State Automata in Linear Space
Event: Conference CPM 2025
Venue: Bicocca University, Milan, Italy
Date: 17/06/2025
Description: Co-Lex orders are partial orders of an automaton states useful for compressing and indexing automata. Despite their usefulness, the state-of-the-art algorithm to compute them runs in quadratic time w.r.t. the number of transitions in the NFA. This is a major limitation for big data applications, where only near linear time algorithms can be run. However, the best represention for these co-lex orders require a quadratic number of bits: too much for the desired time complexity. We solve this issue by proposing the first linear space encoding for these orders.
Indexing Finite-State Automata Using Forward-Stable Partitions
Event: Conference SPIRE 2024
Venue: Puerto Vallarta, Jalisco, Mexico
Date: 23/09/2024
Description: An index on a finite-state automaton is a data structure able to locate specific patterns on its regular language. To develop such a data structure, researchers have recently introduced an extension of the original Burrows-Wheeler transform for arbitrary automata. This transformation works through a co-lex order, that is a partial order of the automaton states consistent with the strings reaching them. In this paper, we introduce a new class of co-lex orders and we show it outperforms all the existing other classes in terms of spatial and time efficiency.