💻 computer science

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

This paper presents an algorithm that decides whether a visibly pushdown language belongs to the complexity class $\mathsf{AC}^0$ by either confirming its membership, proving it is $\mathsf{ACC}^0(m)$ -hard, or reducing it to a specific subclass of intermediate VPLs whose complexity status remains an open conjecture.

Original authors: Stefan Göller, Nathan Grosshans

Published 2026-08-12

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Stefan Göller, Nathan Grosshans

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to sort a massive pile of letters. Some letters are simple, like "A" or "B," and you can sort them quickly by just looking at the first few. Others are tricky, like nested Russian dolls: every time you see a "Call" letter, you must wait for a matching "Return" letter later in the pile to know what to do with it. In the world of computer science, these are called Visibly Pushdown Languages (VPLs). They are the rules that govern how computers handle things like matching parentheses in code or balancing tags in a webpage.

Now, imagine you want to know how "hard" it is for a computer to decide if a specific letter belongs in your pile. Some rules are so simple that a computer can check them almost instantly, using a tiny, flat circuit (like a single layer of logic gates). This super-fast category is called AC0. Other rules are trickier; they require the computer to build a deeper, more complex circuit, perhaps needing to count or check for patterns that repeat in specific ways. The big question for decades has been: "Can we look at a set of these nested rules and instantly tell if they are simple enough to be in AC0, or if they are too complex?" It's like trying to look at a recipe and knowing immediately if it can be cooked in a microwave or if it requires a slow oven.

This paper, written by Stefan Göller and Nathan Grosshans, dives deep into this mystery. They don't just say "some are easy, some are hard." They introduce a new, mysterious middle ground they call Intermediate VPLs. Think of these as the "Goldilocks" rules: they aren't obviously simple, but they aren't obviously impossible to simplify either. The authors prove that they have built a magical algorithm (a step-by-step recipe for a computer) that can take any set of these nested rules and sort them into three buckets:

The Easy Bucket: These are definitely in AC0 (super fast).
The Hard Bucket: These are definitely not in AC0 (they require complex circuits).
The Mystery Bucket: These are the "Intermediate" ones.

Here is the twist: the authors admit that for the "Mystery Bucket," they don't actually know the answer yet. They suspect that either all of these intermediate rules are easy, or none of them are. They can't prove which one is true, but they have proven that their algorithm can identify exactly which rules fall into this mystery category. If someone eventually solves the mystery of the intermediate rules, this algorithm will instantly solve the whole problem for every possible rule.

The Story of the Nested Dolls

To understand what the authors did, let's picture a computer as a very fast, very strict librarian. This librarian has to check if a string of letters (a "word") follows a specific set of rules. The rules are "visibly pushdown," meaning the librarian knows exactly when to push a letter onto a stack (like putting a book on a shelf) and when to pop it off, just by looking at the letter itself.

Call letters are like "Start a new chapter." The librarian puts a marker on the shelf.
Return letters are like "End the chapter." The librarian checks the shelf to see if the marker matches.
Internal letters are just text inside the chapter; they don't change the stack.

The goal is to see if the librarian can decide if a word is "good" (in the language) using a circuit that is very shallow (AC0). If the circuit is too deep, the computer takes too long.

The Three Buckets

The authors' main discovery is a new way to classify these rules. They found that for any set of rules, you can run their algorithm and get one of three answers:

1. The "Super Simple" Rules (AC0)
Some rules are so straightforward that the librarian doesn't even need to look at the whole stack. They can be checked with a tiny, flat circuit. The algorithm can prove this. For example, a rule that just says "count the number of 'A's and check if it's even" might fall here.

2. The "Too Complex" Rules (Not in AC0)
Some rules are inherently difficult. They require the computer to count in a way that a flat circuit simply cannot do. The algorithm can prove this too. It might say, "This rule is as hard as checking if a number is divisible by 3," which is known to be too hard for the super-fast AC0 circuits.

3. The "Intermediate" Rules (The Mystery)
This is the paper's biggest contribution. The authors found a specific type of rule that sits right in the middle. They call these Intermediate VPLs.
Imagine a rule that looks like this: "Start with a call, then do some internal stuff, then return. But here's the catch: the amount of 'stuff' you do on the way in must be different from the amount of 'stuff' you do on the way out, in a very specific, unbalanced way."

These rules are Quasi-Counterfree: They don't have simple repeating loops that make them easy to predict.
They are Weakly Length-Synchronous but not Length-Synchronous: This is a fancy way of saying the "in" and "out" parts of the rule are related, but not in a perfectly proportional way (like 1-to-1).

The authors proved that if your rule falls into this "Intermediate" bucket, their algorithm can tell you exactly what kind of intermediate rule it is. They can even show you a specific, simple example of an intermediate rule (like a specific grammar with a start symbol $S$ that can turn into $ack-1Sb1$ or $acl-1Sb2$) that is mathematically equivalent to your complex rule.

The Big Guess

Here is where it gets exciting. The authors don't know if these "Intermediate" rules are actually in the "Super Simple" bucket or the "Too Complex" bucket.

The Conjecture: They guess that either all intermediate rules are simple, or all of them are complex. There is no mix.
The Implication: If this guess is true, then their algorithm is actually a complete solution! It would mean we can finally decide for any visibly pushdown language whether it is in AC0 or not. We just need to solve the mystery of the intermediate ones.

Why This Matters

Before this paper, we knew how to check simple rules and we knew how to prove some rules were too hard. But we had a blind spot for these "Intermediate" rules. We didn't know if they were secretly easy or secretly hard.

The authors also showed that their method works for a special, simpler type of rule called Visibly Counter Languages (which are like VPLs but with only one type of stack marker). This confirms and improves upon previous work by other scientists (Krebs et al.), showing that their new method is a powerful general tool.

The Bottom Line

Göller and Grosshans didn't just solve the whole puzzle; they built a perfect map of the puzzle. They showed us exactly where the easy pieces are, exactly where the impossible pieces are, and exactly where the mysterious middle pieces are. They even gave us a specific shape for those middle pieces.

They are confident that their algorithm works perfectly to sort any rule into these three categories. They are also confident that the "Intermediate" rules are a distinct, well-defined group. However, they are not confident yet about the final fate of that middle group. They suspect it's an "all or nothing" situation, but until someone proves that, the question of whether these specific intermediate rules are in AC0 remains one of the great unsolved mysteries of computer science.

In short: We now have a tool that can tell us if a rule is easy, hard, or "mysteriously in-between." And if we ever figure out the mystery of the "in-between," we will have solved the entire problem for every possible rule in this class.

Technical Summary: The AC0-Complexity of Visibly Pushdown Languages

Problem Statement

This paper addresses the question of determining which visibly pushdown languages (VPLs) belong to the circuit complexity class AC0 (languages decidable by constant-depth, polynomial-size circuits with unbounded fan-in AND, OR, and NOT gates). While it is well-established that regular languages in AC0 are characterized by aperiodic syntactic monoids, and that visibly counter languages (a subclass of VPLs) have a decidable AC0 membership, the general case for VPLs remained open. Specifically, the authors identify a gap in understanding regarding a specific subclass of VPLs called intermediate VPLs, for which the community was previously unaware of any containment or non-containment results in AC0 or ACC0.

The core problem is to provide an effective algorithm that, given a deterministic visibly pushdown automaton (DVPA), decides whether its language is in AC0, is hard for a specific modular counting class (ACC0(m)), or belongs to a specific structural class (intermediate VPLs) whose complexity status is currently conjectural.

Methodology

The authors employ algebraic automata theory, specifically revisiting and refining the concept of Ext-algebras (originally introduced by Czarnetzki et al.) and utilizing Green's relations from semigroup theory.

Refinement of Ext-Algebras: The paper corrects inaccuracies in the definition of Ext-algebra morphisms found in prior literature (specifically regarding the condition for freeness). They rigorously establish the properties of the syntactic Ext-algebra for VPLs, proving its minimality and the correspondence between VPLs and languages recognized by finite Ext-algebras.
Structural Decomposition: The authors introduce new structural properties for VPLs:
- Quasi-aperiodicity: A property of the syntactic morphism related to the absence of non-trivial groups in specific contexts.
- (Weak) Length-Synchronicity: Properties concerning the ratio of lengths of call and return segments in the contexts generating the language.
Logical Characterization: For languages that are both length-synchronous and quasi-aperiodic, the authors construct FO[+] (first-order logic with addition) formulas. They define "approximate matchings" and "evaluation languages" to show that such languages are definable in FO[+], which implies membership in AC0.
Hardness Reductions: For languages failing these conditions, the authors construct constant-depth reductions from known hard problems (such as EQUALITY for TC0-hardness and MODm for ACC0(m)-hardness) to the target VPL, proving they are not in AC0.

Key Contributions

1. Introduction of Intermediate VPLs

The paper defines a new subclass of VPLs called intermediate VPLs. These are languages that are:

Quasi-counterfree (their syntactic morphism is quasi-aperiodic).
Generated by vertically visibly pushdown grammars where the set of contexts $\{(u, v) \mid S \Rightarrow^* uSv\}$ is weakly length-synchronous but not length-synchronous.
A concrete example is the language generated by $S \to \epsilon \mid a c^{k-1} S b_1 \mid a c^{l-1} S b_2$ where $k \neq l$ .

The authors note that existing techniques (such as the switching lemma or polynomial method) do not appear sufficient to determine if these languages are in AC0 or not.

2. The Main Algorithmic Result

The central theorem provides an algorithm that, given a DVPA $A$ , outputs exactly one of the following:

$L(A) \in AC0$ : The language is in AC0.
Hardness: There exists an $m \ge 2$ such that $L(A)$ is ACC0(m)-hard (implying $L(A) \notin AC0$ ).
Intermediate Case: $L(A)$ is constant-depth equivalent ( $=_{cd}$ ) to a finite disjoint union of intermediate VPLs. In this case, the algorithm effectively computes parameters $k, l \in \mathbb{N}_{>0}$ ( $k \neq l$ ) such that the concrete intermediate language $L_{k,l}$ is constant-depth reducible to $L(A)$ .

3. Decidability for Visibly Counter Languages

As a corollary, the authors show that for visibly counter languages (VPLs accepted by automata using only one stack symbol), the algorithm can effectively determine membership in AC0. This generalizes a previous result by Krebs et al., which was restricted to well-matched words.

Results and Complexity Classification

The paper establishes a trichotomy for the complexity of VPLs based on their syntactic Ext-algebra:

Case 1: Not Weakly Length-Synchronous.
If the language is not weakly length-synchronous, it is TC0-hard (and thus not in AC0). This is proven by reducing the EQUALITY problem to the language.
Case 2: Not Quasi-Aperiodic.
If the syntactic morphism is not quasi-aperiodic, the language is ACC0(m)-hard for some $m \ge 2$ . This is proven by reducing the MODm problem.
Case 3: Quasi-Aperiodic and Length-Synchronous.
If the language is both quasi-aperiodic and length-synchronous, it is in FO[+] and therefore in AC0.
Case 4: The Intermediate Case.
If the language is quasi-aperiodic and weakly length-synchronous but not length-synchronous, it falls into the intermediate category. The paper conjectures that either all intermediate VPLs are in AC0 or none are.

Conjecture 2.10: Either all intermediate VPLs are in AC0 or all are not.
The authors state that if this conjecture holds, combined with their main algorithm, it would yield a complete decision procedure for AC0 membership for all VPLs.

Significance and Claims

The paper claims to provide the first effective characterization of the AC0-complexity of VPLs, moving beyond the known results for regular languages and visibly counter languages.

Theoretical Gap: It highlights a specific "blind spot" in current complexity theory regarding intermediate VPLs, where standard proof techniques (robustness, switching lemma, polynomial method) fail to yield results.
Algebraic Tooling: By fixing the definition of Ext-algebra morphisms and rigorously proving their properties (freeness, minimality), the paper establishes a robust algebraic framework for analyzing VPL complexity.
Decidability: The primary contribution is the existence of an algorithm that effectively classifies any given VPL into one of three categories: in AC0, hard for a modular counting class, or structurally equivalent to an intermediate VPL.

The authors remain modest regarding the final resolution of the intermediate case, explicitly stating that their result reduces the open problem of "Are all VPLs in AC0 decidable?" to the conjecture about the uniform complexity of intermediate VPLs. They do not claim to have resolved the status of intermediate VPLs themselves, but rather to have isolated them as the sole remaining obstacle to a full decision procedure.