Circuits complexity and regular languages

Speaker(s)

Charles Paperman

Affiliation

Uniwersytet Warszawski

Date

March 11, 2015, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

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.

---