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

Abstract

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 introduce a particular subclass of one-turn VPLs, called intermediate VPLs, for which the raised question is entirely unclear: to the best of our knowledge our research community is unaware of containment or non-containment in ${\mathsf{AC}}^0$ for any language in our newly introduced class. Our main result states that there is an algorithm that, given a visibly pushdown automaton, correctly outputs exactly one of the following: that its language $L$ is in ${\mathsf{AC}}^0$, some $m\ge 2$ such that $L$ is ${\mathsf{ACC}}^0(m)$-hard (implying that $L$ is not in ${\mathsf{AC}}^0$), or a finite disjoint union of intermediate VPLs that $L$ is constant-depth equivalent to. In the latter of the three cases one can moreover effectively compute $k,l\in {\mathbb{N}}_{>0}$ with $k\ne l$ such that the concrete intermediate VPL $L(S\to \epsilon \mid a{c}^{k-1}S{b}_1\mid a{c}^{l-1}S{b}_2)$ is constant-depth reducible to the language $L$. Due to their particular nature we conjecture that either all intermediate VPLs are in ${\mathsf{AC}}^0$ or all are not. As a corollary of our main result we obtain that in case the input language is a visibly counter language our algorithm can effectively determine if it is in ${\mathsf{AC}}^0$ - hence our main result generalizes a result by Krebs et al. stating that it is decidable if a given visibly counter language is in ${\mathsf{AC}}^0$ (when restricted to well-matched words). For our proofs we revisit so-called Ext-algebras (introduced by Czarnetzki et al.), which are closely related to forest algebras (introduced by Bojańczyk and Walukiewicz), and use Green's relations.