La complexité en états d'opérations régulières

Abstract

Dans un premier temps, nous présentons les opérations 1-uniformes et les modificateurs qui permettent de lier des opérations sur des langages avec des opérations agissant sur des automates finis déterministes. Ensuite, nous parlons des automates monstres qui ont la particularité d’avoir de grands alphabets. Une méthode permettant de calculer la complexité en états en utilisant les modificateurs et les monstres sera donnée et appliquée. Finalement, nous abordons une classe particulière de modificateurs, ceux-ci sont appelés modificateurs amicaux et nous calculons la complexité en états maximale d’opérations amicales.