An Approach to Computing Downward Closures

Georg Zetzsche

Abstract

This paper presents a breakthrough general method for computing the downward closure of word languages. By reducing the problem to a "simultaneous unboundedness property" (SUP), we demonstrate that downward closures are computable for several complex language classes. Most notably, we provide the first such result for indexed languages (those accepted by order-2 pushdown automata), which previously lacked a known construction for their downward closures.

Introduction

In formal language theory, the downward closure of a language $L$ (denoted $L\downarrow$) is the set of all possible subwords formed by deleting letters from words in $L$. Higman's Lemma guarantees that for any language, the downward closure is a regular language, implying it can be represented by a finite automaton. However, the existence of such an automaton does not imply its computability. For many complex language classes, computing this automaton has remained an open problem for decades. Downward closures are vital for system verification, particularly when modeling "lossy channels" where messages can be dropped; their computability allows for deciding equivalence between systems under unreliable conditions.

Methodology: Reduction to the Simultaneous Unboundedness Problem

The primary contribution of this work is a reduction proving that for any language class closed under rational transductions (a full trio), computing the downward closure is equivalent to solving the Simultaneous Unboundedness Problem (SUP). The SUP asks: Given a language $L \subseteq a_1^* \dots a_n^*$, can we find words in $L$ that contain arbitrarily many occurrences of each letter $a_i$ in the specified order?

To prove this is sufficient for indexed languages, the author employs a sophisticated chain of grammar transformations:

  1. Triple Construction: A standard tool to ensure closure under transductions.
  2. Interval and Productive Grammars: Refining the grammar so each non-terminal derives words within specific "intervals" and contributes to the final output.
  3. Breadth-Boundedness: Limiting the number of active non-terminals in any sentential form.
  4. Scattered Context Grammars: Transforming the indexed grammar into a finite-index scattered context grammar, a class known to have "semilinear" properties that make the SUP decidable.
A derivation tree in an indexed grammar, illustrating the stack-like behavior of indices (f, g) during the generation of the word 'abab'.

Key Insights and Theoretical Implications

A central "aha moment" is the reduction to SUP, which simplifies a complex construction problem (building an automaton) into a simpler decision problem (checking for unboundedness). While researchers typically use Parikh images (which count letter frequencies) as an abstraction, many interesting languages like indexed languages do not have semilinear Parikh images. This work shows that downward closures are a more robust abstraction because they are always regular, even when Parikh images are non-semilinear.

A surprising finding (Proposition 7) is the "blind counter trap": adding even a simple "blind counter" to an order-2 pushdown automaton makes reachability undecidable. This highlights a fundamental difference between downward closures and Parikh images, as the latter are preserved when adding such counters, whereas the former's computability is not guaranteed.

Results

The paper establishes several key results in the field:

  • Theorem 1: For any full trio, downward closures are computable if and only if the SUP is decidable.
  • Indexed Languages: Computability of downward closures for indexed languages (order-2 higher-order pushdown automata) is proven for the first time.
  • Matrix Languages: A new proof is provided for the computability of downward closures for matrix languages.
  • Decidability of Separability: The results imply that for these classes, it is now decidable whether two languages can be separated by a "piecewise testable" language.

Conclusion

While the proposed method is general, it currently functions as a "brute-force" approach involving the enumeration of regular expressions. Consequently, the computational complexity is likely very high. Future work may involve finding more efficient, direct algorithms for specific classes or extending this approach to higher-order pushdown automata (order-3 and beyond).

Summary updated

BibTeX
@inproceedings{zetzsche2015approach,
  author = {Georg Zetzsche},
  title = {{An Approach to Computing Downward Closures}},
  booktitle = {ICALP},
  year = {2015},
  doi = {10.1007/978-3-662-47666-6\_35},
}
Figure