Descriptional Complexity of Models for Regular Languages

11^th November 2025, 13:00
Luca Prigioniero
Loughborough University

Abstract

Finite automata are classical machines used to recognise regular languages. However, a variety of alternative models are also known to characterise this class. In many cases, these alternative devices can represent regular languages much more concisely than classical recognisers.

In this talk, I will present an overview of such models and their capacity to capture regular languages in a compact way. I will focus on selected devices and their properties, discussing recent results as well as open problems in the area.