Nie jesteś zalogowany | Zaloguj się

Circuits complexity and regular languages

Prelegent(ci)
Charles Paperman
Afiliacja
Uniwersytet Warszawski
Termin
11 marca 2015 14:15
Pokój
p. 5870
Seminarium
Seminarium „Teoria automatów”

I will talk about classical and recent developments on the subject: "Deciding the membership of regular languages in circuits complexity classes". This question is deeply interwoven with the algebraic characterization of classes of regular languages defined by logical fragments. I will finally present some (partial) results on the poorly understood linear classes.