BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Nicola Prezza (Università Ca' Foscari Venezia) DTSTART:20251126T140000Z DTEND:20251126T150000Z DTSTAMP:20260423T052924Z UID:FLAT/15 DESCRIPTION:Title: Fr om text indexing to regular language indexing\nby Nicola Prezza (Unive rsità Ca' Foscari Venezia) as part of One FLAT World Seminar\n\n\nAbstra ct\nSince the invention of suffix sorting (in particular\, of suffix trees ) in the 70's\, the problem of indexed pattern matching has been heavily s tudied in the literature. This problem has a natural language-theoretic in terpretation: given a string $S$\, build a (linear-space) data structure a nswering membership queries in the substring closure of $S$. This interpre tation was recently made more interesting by several works showing that su ffix sorting can be naturally extended to some nonlinear structures\, nota bly labeled trees and de Bruijn graphs. This line of work culminated in th e invention of Wheeler automata\, a class of NFAs admitting efficient and elegant solutions to a large number of hard problems on automata (includin g membership). In this talk\, I will first give an introduction to the ric h theory of Wheeler automata and Wheeler languages. I will then show how t hese ideas can be generalized to arbitrary NFAs\, comparing this solution to other existing approaches for indexing arbitrary regular languages.\n LOCATION:https://researchseminars.org/talk/FLAT/15/ END:VEVENT END:VCALENDAR