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.