The ${\mathsf{AC}}^0$-Complexity Of Visibly Pushdown Languages

Stefan Göller, Nathan Grosshans

We study the question of which visibly pushdown languages (VPLs) are in the complexity class ${\mathsf{AC}}^0$ and how to effectively decide this question. Our contribution is to int…