Parikh Images of Regular Languages: Complexity and Applications

Anthony Widjaja ToarXiv 2010 · OpenReview

Abstract

We show that the Parikh image of the language of an NFA with $n$ states over an alphabet of size $k$ can be described as a finite union of linear sets with at most $k$ generators and total size $2^{O(k^2 \log n)}$, i.e., polynomial for all fixed $k \ge 1$. Previously, it was not known whether the number of generators could be made independent of $n$, and best upper bounds on the total size were exponential in $n$. Furthermore, we give an algorithm for performing such a translation in time $2^{O(k^2 \log(kn))}$. Our proof exploits a previously unknown connection to the theory of convex sets, and establishes a normal form theorem for semilinear sets, which is of independent interests. To complement these results, we show that our upper bounds are tight and that the results cannot be extended to context-free languages. We give four applications: (1) a new polynomial fragment of integer programming, (2) precise complexity of membership for Parikh images of NFAs, (3) an answer to an open question about polynomial PAC-learnability of semilinear sets, and (4) an optimal algorithm for LTL model checking over discrete-timed reversal-bounded counter systems.

Introduction

In formal language theory, the Parikh image of a language provides a commutative abstraction of strings, mapping them to vectors of natural numbers that represent the frequency of each character. For example, in an alphabet $\{a, b\}$, the strings "aabb" and "abab" both map to the vector $(2, 2)$. Parikh’s Theorem (1966) established that the Parikh images of both regular and context-free languages are semilinear sets—finite unions of linear sets (essentially lattices or grids in $k$-dimensional space).

While the existence of these semilinear representations has been known for decades, a significant "succinctness gap" persisted. Standard translations from a Non-deterministic Finite Automaton (NFA) with $n$ states to a semilinear set often resulted in an exponential explosion in size. This paper bridges that gap, providing a new Normal Form Theorem that leverages convex geometry to achieve polynomial-sized representations for fixed alphabet sizes.

The Succinctness Gap and Geometric Innovation

The primary challenge in automata theory was determining whether the number of generators in a linear set could be decoupled from the number of states ($n$) in the NFA. Previous results, such as the Chrobak-Martinez Theorem, solved this for single-letter alphabets ($k=1$), but the general case for $k > 1$ remained open.

This research introduces a novel approach by shifting the perspective from graph-theoretic path analysis to convex geometry. The proof relies on several key geometric pillars:

  1. Caratheodory’s Theorem: This classic result states that any point in a $d$-dimensional convex cone can be represented as a linear combination of at most $d$ generators. By treating the Parikh image as a collection of points in $k$-dimensional space, the author decomposes the space into "sub-cones."
  2. Geometric Decomposition: The Parikh image is partitioned into regions where the number of generators required depends only on the dimension $k$, not the complexity of the automaton's state graph.
  3. Minimal Vectors: By defining a specific partial order on vectors within these cones, the author identifies a set of "minimal" vectors that serve as the offsets for the linear sets.
  4. Constructive Algorithm: The paper provides a dynamic programming algorithm that computes these minimal vectors and generators in $2^{O(k^2 \log(kn))}$ time, making the theoretical bounds computationally accessible.

Key Theoretical Results

The core contribution is the proof that an NFA with $n$ states over $k$ letters can be described as a union of linear sets with at most $k$ generators and a total size of $2^{O(k^2 \log n)}$. For any fixed $k$, this representation is polynomial in $n$.

Furthermore, the author establishes the tightness of these bounds, proving that the quadratic bound on the size of offsets is essentially optimal and that the number of linear sets must grow as $\Omega(n^{k-1})$. Crucially, the paper also demonstrates a divergence for Context-Free Languages (CFLs); the efficiency found in regular languages cannot be extended to CFLs, which may require an exponential number of linear sets even for a single-letter alphabet.

Applications

The succinctness of this new representation has immediate implications across several domains of computer science:

  • Integer Programming (IP): The results identify a new polynomial-time fragment of IP. Specifically, checking the feasibility of $Ax = b$ is solvable in polynomial time for a fixed number of rows, even when $b$ is provided in binary.
  • PAC-Learnability: The paper resolves a long-standing open question by proving that semilinear sets in any fixed dimension are "Probably Approximately Correct" (PAC) learnable in polynomial time (assuming unary encoding for numbers).
  • Formal Verification: The author provides an optimal algorithm for LTL model checking over reversal-bounded counter systems. This reduces the complexity of the verification process from double-exponential to single-exponential in the number of states.

Conclusion and Future Work

By establishing a connection between automata theory and convex set theory, this work provides a definitive answer to the complexity of Parikh images for regular languages. While the results offer a polynomial advantage for fixed alphabet sizes, the complexity remains exponential in $k$. Future research may explore whether these "Normal Form" efficiencies can be extended to purely binary-encoded automata or if further optimizations can mitigate the impact of large alphabet sizes.

Summary updated

Abstract

We show that the Parikh image of the language of an NFA with n states over an alphabet of size k can be described as a finite union of linear sets with at most k generators and total size 2^{O(k^2 log n)}, i.e., polynomial for all fixed k >= 1. Previously, it was not known whether the number of generators could be made independent of n, and best upper bounds on the total size were exponential in n. Furthermore, we give an algorithm for performing such a translation in time 2^{O(k^2 log(kn))}. Our proof exploits a previously unknown connection to the theory of convex sets, and establishes a normal form theorem for semilinear sets, which is of independent interests. To complement these results, we show that our upper bounds are tight and that the results cannot be extended to context-free languages. We give four applications: (1) a new polynomial fragment of integer programming, (2) precise complexity of membership for Parikh images of NFAs, (3) an answer to an open question about polynomial PAC-learnability of semilinear sets, and (4) an optimal algorithm for LTL model checking over discrete-timed reversal-bounded counter systems.
BibTeX
@misc{to2010parikh,
  author = {Anthony Widjaja To},
  title = {{Parikh Images of Regular Languages: Complexity and Applications}},
  year = {2010},
  eprint = {1002.1464},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1002.1464},
}
Figure