一句话：给出判定可见下推语言是否在 AC^0 中或 ACC^0(m)-难的算法，并引入中间 VPL 子类。
本文研究哪些可见下推语言（VPL）属于电路复杂度类 AC^0，以及如何有效判定该问题。作者引入单转 VPL 的一个新子类——中间 VPL，其 AC^0 成员性此前完全不清楚。主要结果是一个算法：输入可见下推自动机，准确输出三种情形之一：该语言属于 AC^0；存在 m≥2 使其为 ACC^0(m)-难，从而不在 AC^0；或该语言常数深度等价于有限个互不相交的中间 VPL 之并。第三种情形还可有效计算 k≠l，使具体中间 VPL L(S→ε | ac^{k-1} S b_1 | ac^{l-1} S b_2) 常数深度可归约到该语言。作者猜想所有中间 VPL 要么都在 AC^0，要么都不在。作为推论，对可见计数器语言可有效判定 AC^0 成员性，推广了 Krebs 等人的结果。证明重访 Ext-代数，并利用 Green 关系。
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\geq 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\not=l$ such that the concrete intermediate VPL $L(S\rightarrow \varepsilon\mid a c^{k-1} S b_1\mid ac^{l-1}Sb_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.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@article{GollerG26,
title = {The $\mathsf{AC}^0$-Complexity Of Visibly Pushdown Languages},
author = {Stefan Göller and Nathan Grosshans},
journal = {Logical Methods in Computer Science},
volume = {Volume 22, Issue 3},
year = {2026},
doi = {10.46298/lmcs-22(3:5)2026}
}