Regular languages recognition in restricted models of computation
Jeudi 21 mai 2026, 14:00 à 15:00
salle de séminaires du département d'informatique
(ENS, Paris)
Testing membership in a formal language is a classical problem at the core of automata theory and theoretical computer science. At a high level, the goal is to represent a set of strings in a compact way that enables efficient recognition under limited computational resources. A prominent example is regular language recognition, which underlies substring search primitives in modern programming languages. Motivated by quick growth of data volume and noisy inputs, recent work has revisited regular language recognition in restricted models of computation, where algorithms operate with severe limitations on memory, passes over the input, or access to the data. In this talk, we survey recent advances in this direction, focusing in particular on streaming algorithms and property testing for regular language recognition. We will present key techniques, algorithmic results, lower bounds, and structural insights, and conclude with a discussion of open problems and research directions.