"Descriptional Complexity of Models for Regular Languages"

No próximo dia 9 de fevereiro, pelas 14h30 na sala FC1 004 do DM FCUP,  Luca Prigioniero irá dar uma palestra intitulada "Descriptional Complexity of Models for Regular Languages".


A palestra é organizada pelo DCC-FCUP e pelo CMUP-"Semigrupos, Autómatos e Linguagens" e é aberta a todos os interessados.


Short Bio:

Luca received his B.Sc. degree in 2014, followed by his M.Sc. degree in 2016, and completed his Ph.D. in 2020, all in Computer Science from Università degli Studi di Milano. In 2019 he obtained a research fellowship at Justus-Liebig-Universität Gießen. Subsequently, in 2020, he returned to Università degli Studi di Milano, where he was a postdoctoral researcher until 2023. In the same year, he joined the Department of Computer Science at Loughborough University, UK, as a lecturer.

His research interests include formal languages, automata theory and theoretical computer science. Specifically, he investigates computational models characterizing the class of regular languages and having succinct descriptions. On the other hand, his research activity focuses on the study of reversible formal models (from the descriptional complexity point of view) and their computations.



"Descriptional Complexity of Models for Regular Languages"




Finite automata are classical machines that recognise regular languages. However, many other devices characterising this class are known. These alternative models may represent regular languages in a significantly more concise way than classical recognisers. In this talk I will present an overview of old and recent results on formal systems for regular languages from a descriptional complexity point of view, that is by considering the relationships between the sizes of such devices.