You are not logged in | Log in

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.