Slice closures of indexed languages and word equations with counting constraints

Laura Ciobanu, Georg Zetzsche

Introduction

Indexed languages, introduced by Alfred Aho in 1968, represent a significant class of formal languages positioned between context-free and context-sensitive languages. They are equivalent to the languages recognized by second-order pushdown automata and are intrinsically linked to higher-order recursion schemes (HORS), which are vital for the verification of functional programs. While basic decision problems such as emptiness are decidable for indexed languages, "counting properties"—which involve tracking the exact number of occurrences of different symbols—have remained largely intractable for decades.

The Challenge of Counting in Indexed Languages

The difficulty in analyzing counting properties stems from the fact that most non-regular counting properties for indexed languages are undecidable. For instance, determining whether every execution trace in a system modeled by an indexed language maintains a specific balance (e.g., an equal number of "requests" and "responses") was a long-standing open problem. Specifically, Naoki Kobayashi posed a question in 2013 regarding whether one could decide if every word in an indexed language contains an equal number of specific characters. This paper provides the first known decidable counting properties for this class, effectively answering Kobayashi's challenge.

Methodology: Slice Closures and Saturation

The authors address these challenges by introducing a framework based on slice closures. A "slice" is a set of vectors characterized by a specific geometric property: if vectors $u$, $u+v$, and $u+w$ are members of the set, then $u+v+w$ must also be included. Slices are particularly useful because they are structured enough to be semilinear—meaning they can be described by Presburger arithmetic—yet general enough to preserve affine invariants (linear relationships between letter counts).

The Saturation Procedure

The core technical contribution is a saturation algorithm designed to compute the smallest slice containing the Parikh image (the vector of letter counts) of an indexed language. The procedure involves:

  1. Fixpoint Characterization: The authors developed a new method to describe the Parikh images of sentential forms in an indexed grammar as a fixpoint of a specific derivation operator ($D$). A major technical hurdle was that indexed grammars use stacks of index symbols; the authors successfully abstracted these into the fixpoint operator by focusing on terminals and non-terminals.
  2. Iterative Application: The algorithm iteratively applies this derivation operator and immediately computes the slice closure of the resulting set.
  3. Termination via Ascending Chain Condition: The algorithm is guaranteed to terminate because slices satisfy an ascending chain condition, preventing an infinite sequence of strictly increasing slices.
  4. Effective Semilinearity: The final output is a semilinear representation of the language's Parikh image under slice closure, allowing for the use of first-order theory of addition to solve constraints.

Key Results and Implications

The theoretical framework yields several breakthrough results in formal language theory and logic:

  • Resolution of Kobayashi’s Question: The paper proves that it is indeed decidable whether every word $w$ in an indexed language $L \subseteq \{a, b\}^*$ satisfies the condition $|w|_a = |w|_b$.
  • Word Equations with Counting Constraints: By leveraging the fact that solution sets of word equations with rational constraints are EDT0L languages (a subclass of indexed languages), the authors extend their results to word equations. They demonstrate the decidability of finding solutions where specific counting constraints are violated (e.g., $|X|_a \neq |Y|_a$). This is the first decidability result for word equations involving this type of counting constraint.
  • Affine Invariants: The method effectively captures all linear relationships between letter counts that hold for every word in the language.

Limitations and Future Directions

While this work marks a significant advancement, it leaves open several questions. The complexity of the saturation algorithm is not explicitly bounded and is expected to be extremely high, potentially reaching Ackermannian levels due to the nature of indexed languages. Furthermore, while the results apply to order-2 indexed languages, it remains to be seen if these techniques can be generalized to higher-order recursion schemes (order 3 and above). Finally, the problem of deciding polynomial constraints (e.g., $|w|_a = |w|_b^2$) remains an open challenge for the formal language theory community.

Summary updated

BibTeX
@inproceedings{ciobanu2024slice,
  author = {Laura Ciobanu and Georg Zetzsche},
  title = {{Slice closures of indexed languages and word equations with counting constraints}},
  booktitle = {LICS},
  year = {2024},
  url = {https://openreview.net/forum?id=0OXb7XgXUu},
}
Figure