Postdoctoral Researcher.
Link: https://researchportal.helsinki.fi/en/persons/nicola-cotumaccio

AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

We show that the ideas behind some of the most important data structures for compressing and indexing strings — such as the suffix array, the Burrows-Wheeler Transform and the FM-index — are much more general and provide a new approach to studying automata and regular languages, which retrospectively explains the impact of these data structures. We classify all automata and all regular languages by their propensity to be sorted. Our classification represents a useful parameterization simultaneously for diverse automata-related measures: (i) the encoding bit-complexity of automata/labeled graphs, (ii) the complexity of operations on regular languages (e.g. membership) and on labeled graphs (e.g. pattern matching), (iii) the complexity of NFA determinization by the powerset-construction algorithm.

Nidhi Rathi

+49 681 9325 1134

--email hidden

Zoom

897 027 2575

passcode not visible

logged in users only