💻 computer science

The complexity of downward closures of indexed languages

This paper resolves the open question regarding the complexity of computing downward closures for indexed languages by establishing triply and quadruply exponential upper bounds for non-deterministic and deterministic automata, respectively, alongside matching lower bounds, achieved through a novel method that transforms indexed grammars into context-free ones using semigroup-based word summaries.

Original authors: Richard Mandel, Corto Mascle, Georg Zetzsche

Published 2026-05-28

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Richard Mandel, Corto Mascle, Georg Zetzsche

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 have a massive, infinitely complex library of stories. Some stories are short, some are millions of pages long, and some follow rules so complicated that a normal computer can't even read them. In the world of computer science, these stories are called Indexed Languages. They are like a super-charged version of the standard "Context-Free" languages (which power things like programming code syntax), but they have an extra layer of complexity: a "stack of stacks."

Think of a normal stack like a stack of plates. You can add a plate or take one off. An Indexed Language is like having a stack of entire plate towers. You can add a whole tower, or take a whole tower off. This makes the system incredibly powerful but also incredibly hard to analyze.

The Problem: The "Downward Closure"

The authors of this paper are interested in a specific way of simplifying these massive libraries. They call it the Downward Closure.

Imagine you have a very long sentence: "The quick brown fox jumps over the lazy dog."
The "downward closure" of this sentence is the collection of all possible shorter sentences you can make by deleting letters, but keeping the order.

"The fox jumps" is in the closure.
"Quick dog" is in the closure.
"Dog quick" is not (because the order changed).

Why do we care? Because the original library might be infinite and impossible to process. But the "Downward Closure" (the set of all possible sub-stories) is always Regular. In computer speak, this means it can be described by a simple, finite machine (like a basic flowchart). It's a way of taking a chaotic, infinite mess and turning it into a neat, manageable list of patterns.

The Big Question: We knew we could turn these complex Indexed Languages into simple lists (Downward Closures). But we didn't know how big that list would be. Would it be a list the size of a phone book? A list the size of the entire internet? Or a list so big it would take longer to write than the age of the universe?

The Discovery: A Triple-Exponential Explosion

The authors, Mandel, Mascle, and Zetzsche, finally solved this mystery. They proved that to turn an Indexed Language into its simple Downward Closure, the resulting machine can be triply exponential in size.

Let's break down what "triply exponential" means using a metaphor:

Linear: If you have 10 items, you need 10 boxes.
Exponential: If you have 10 items, you need $2^{10}$ (1,024) boxes.
Doubly Exponential: If you have 10 items, you need $2^{2^{10}}$ (over a million billion) boxes.
Triply Exponential: If you have 10 items, you need $2^{2^{2^{10}}}$ boxes. This number is so vast it is almost impossible to comprehend. It's like trying to count every grain of sand on every beach on Earth, then doing that for every grain of sand on every beach on every beach...

The authors showed that for Indexed Languages, the "Downward Closure" machine is roughly this huge. They also proved you can't do better than this; the machine must be this big for certain languages.

How They Did It: The "Summary" Trick

How do you compress a stack of towers into a simple list without losing the ability to recognize patterns?

The authors used a clever trick from a branch of math called Semigroup Theory. Imagine you are reading a very long story, but you only care about the "vibe" of the story, not every single word.

If a story repeats a specific pattern over and over (like a chorus in a song), you don't need to write down the whole chorus every time. You can just write "Chorus" and move on.
The authors created a mathematical "summary" for the stacks. Instead of tracking every single "plate" or "tower" in the stack, they replaced long sequences of identical patterns with a single summary symbol.

They showed that even though the stacks are infinite, you can replace them with these summaries. Once you do that, the complex "Indexed Grammar" becomes a simpler "Context-Free Grammar" (a standard type of computer grammar). Then, they used existing methods to turn that simpler grammar into the final Downward Closure machine.

The Result: A New Record

Before this paper, people knew the problem was solvable, but they didn't know the cost.

The Upper Bound: They built a method to create the machine, and it takes triply exponential time and space.
The Lower Bound: They also built a specific, tricky language that forces any machine to be at least triply exponential in size.

This means they found the exact "price tag" for this problem. It's not just "hard"; it's "triple-exponentially hard."

They also applied this to two other questions:

Comparison: If you have two complex languages, can you tell if their "Downward Closures" are the same? The answer is yes, but it's a co-3-NEXP-complete problem. In plain English: It's a puzzle that is incredibly difficult to solve, right at the edge of what computers can theoretically handle in a reasonable timeframe.
Pumping Threshold: They proved that the longest word you can generate in a finite Indexed Language before it starts repeating patterns is also triply exponential.

Summary

Think of Indexed Languages as a giant, infinite maze. The "Downward Closure" is a map of all the possible shortcuts through that maze.

Old Knowledge: We knew a map existed.
New Knowledge: We now know that for the most complex mazes, the map is so huge it would take a computer longer to draw than the universe has existed.
The Method: The authors found a way to shrink the maze down to a manageable size by summarizing the repeating parts, allowing them to draw the map and prove exactly how big it has to be.

They didn't just guess; they built the map and proved that no smaller map could possibly work.

Technical Summary: The Complexity of Downward Closures of Indexed Languages

Problem Statement

The paper addresses the computational complexity of constructing downward closures for indexed languages. The downward closure of a language $L$ , denoted $L^\downarrow$ , is the set of all scattered subwords of words in $L$ . By Higman's Lemma, $L^\downarrow$ is always a regular language, making it a crucial regular over-approximation used in the verification of infinite-state systems (e.g., higher-order model checking, asynchronous programs, and lossy channel systems).

While the computability of downward closures for indexed languages (equivalent to order-2 pushdown automata or 2-PDAs) was established in 2015 via a general algorithm based on well-quasi-orderings, the complexity bounds for this construction remained an open problem. Specifically, it was unknown whether a primitive-recursive construction existed, and no upper or lower bounds on the size of the resulting automata were known. Prior to this work, the best known lower bound for the size of a non-deterministic finite automaton (NFA) for the downward closure of an indexed language was doubly exponential, and the complexity of decision problems like downward closure inclusion and equivalence was known to be at least co-2-NEXP-hard.

Methodology

The authors resolve this open problem by providing tight (asymptotically matching) upper and lower bounds. Their approach relies on a novel algebraic abstraction of stack contents to transform indexed grammars into context-free grammars (CFGs) while preserving the downward closure.

1. Productivity and Annotation

The construction begins by ensuring the input indexed grammar is productive (every sentential form can derive a terminal word). The authors introduce an annotated version of the grammar where stack symbols are paired with sets of non-terminals that can derive terminal words from that stack configuration. This prevents the generation of "dead" terms that cannot contribute to the language, a property essential for preserving the downward closure during subsequent transformations.

2. The Stack Monoid and Summaries

The core technical innovation involves finite semigroup theory. The authors define a stack monoid $M$ (a finite monoid of Boolean matrices) that encodes the behavior of stack operations (pushing and popping) relative to the grammar's non-terminals.

Summaries: They utilize recent advances in semigroup theory (specifically results by Jecker and Gimbert et al.) to compute summaries of arbitrarily long stack words. A summary is a compressed representation of a stack word that retains enough information to determine the outcome of push/pop operations with respect to the monoid $M$ .
Pumping and Skipping: The authors introduce two new derivation rules, pump and skip, which allow the extension and reduction of stack infixes that map to the same idempotent element in the monoid. They prove that these rules do not alter the downward closure of the language.
Compression: By applying these rules, they show that any stack content can be compressed into a summary of bounded size (exponential in the size of the grammar). This compression effectively loses information about the exact stack content but preserves the downward closure.

3. Reduction to Context-Free Grammars

Using these summaries, the authors construct a context-free grammar (CFG) $G_{CFG}$ that simulates the original indexed grammar $G$ . In $G_{CFG}$ , the stack contents of the indexed grammar are replaced by their summaries.

The non-terminals of $G_{CFG}$ are triples $(A, X, \sigma)$ , where $A$ is a non-terminal, $X$ is a set of non-terminals, and $\sigma$ is a feasible summary.
Push and pop operations in the original grammar are simulated by operations on summaries (using the push and pop relations defined on the monoid).
The authors prove that $L(G_{CFG})^\downarrow = L(G)^\downarrow$ .

4. Complexity Analysis

Since the size of a summary is bounded exponentially in the size of the grammar, the resulting CFG $G_{CFG}$ has a doubly exponential size. Existing algorithms for computing downward closures of CFGs yield an NFA of exponential size relative to the CFG. Consequently, the composition yields an NFA for $L(G)^\downarrow$ of triply exponential size.

For deterministic finite automata (DFA), the standard subset construction applied to the triply exponential NFA results in a quadruply exponential upper bound.

Key Contributions and Results

Upper Bounds

NFA Size: Given an indexed grammar of size $n$ , an NFA for its downward closure can be computed in triply exponential time and has size at most triply exponential ( $O(\exp_3(n))$ ).
DFA Size: A DFA for the downward closure can be constructed with size at most quadruply exponential ( $O(\exp_4(n))$ ).
Decision Problems: The downward closure inclusion ( $L_1^\downarrow \subseteq L_2^\downarrow$ ) and equivalence ( $L_1^\downarrow = L_2^\downarrow$ ) problems for indexed languages are co-3-NEXP-complete.

Lower Bounds

The authors provide matching lower bounds, proving the tightness of their upper bounds:

NFA Lower Bound: There exists a family of indexed grammars of polynomial size such that any NFA for their downward closure requires at least triply exponential states. This is achieved by constructing a grammar that generates the language $\{a^{\exp_3(n)}\}$ .
DFA Lower Bound: There exists a family of indexed grammars such that any DFA for their downward closure requires at least quadruply exponential states.
Pumping Threshold: The results imply that the pumping threshold for indexed grammars (the maximum length of a word in a finite indexed language of size $n$ ) grows at least triply exponentially, correcting a previous claim of a doubly exponential bound found in the literature.

Significance

The paper settles a long-standing open problem regarding the complexity of downward closures for indexed languages.

Tight Bounds: It establishes that the complexity is strictly higher than for context-free languages (which are doubly exponential for NFAs) but lower than the general tower of exponentials often associated with higher-order systems of order $k > 2$ . The jump from doubly to triply exponential for indexed languages (order-2) is unexpected given the linear growth of complexity for other problems (like emptiness) with respect to the order of the pushdown automaton.
Algorithmic Feasibility: It confirms that a primitive-recursive construction exists, resolving the question of whether the problem is merely computable or effectively constructible within a specific complexity class.
Methodological Advance: The technique of using semigroup-based summaries to compress stack contents while preserving downward closures offers a new tool for analyzing higher-order systems, potentially applicable to broader classes of infinite-state systems.

The authors emphasize that their results are derived from a constructive transformation of indexed grammars to CFGs, leveraging the algebraic properties of the stack monoid to manage the unbounded nature of the stacks in a way that preserves the subword structure essential for downward closures.