Visibly Counter Languages and the Structure of NC1


We extend the familiar program of understanding circuit complexity in terms of regular languages to visibly counter languages. Like the regular languages, the visibly counter languages are NC1- complete. We investigate what the visibly counter languages in certain constant depth circuit complexity classes are. We have initiated this in a previous work for AC0. We present characterizations and decidability results for various logics and circuit classes. In particular, our approach yields a way to understand TC0, where the regular approach fails.

Proceedings of Mathematical Foundations of Computer Science (MFCS) 2015