Title: A Theory of (co-lex) Ordered Regular Languages

Abstract: NFAs are inherently unordered objects, but they represent regular languages on which one can very naturally define a total order: for example, the co-lexicographic order in which words are compared alphabetically from right to left. In this talk I will show that interesting things happen when one tries to map this total order to the states of an accepting NFA for the language: the resulting order of the states is a partial pre-order whose width p turns out to be an important parameter for NFAs and regular languages. For example, take the classic powerset determinization algorithm for converting an NFA of size n into an equivalent DFA: while a straightforward analysis shows that the size of the resulting DFA is at most 2^n, we prove that it is actually at most (n-p+1)*2^p. This implies that PSPACE-complete problems such as NFA equivalence or universality are actually easy on NFAs of small width p (the case p=1 – total order – is particularly interesting). Another implication of this theory is that we can compress NFAs to just O(log p) bits per transition while supporting fast membership queries in the substring closure of the language.

Biosketch: Nicola Prezza is an Associate professor at Ca’ Foscari University of Venice, Italy. He received a PhD in Computer Science from the University of Udine in 2017 with a thesis on dynamic compressed data structures. After that, he worked as post-doc researcher at the universities of Pisa and Copenhagen (DTU) and as Assistant professor at LUISS (Rome). His current research is focused on the relations existing between data structures, data compression, and regular languages. In 2018, he received the “Best Italian Young Researcher in Theoretical Computer Science” award from the Italian chapter of EATCS. In 2021, he won an ERC starting grant on the topic of regular language compression and indexing.