QUOTIENT COMPLEXITY OF STAR-FREE LANGUAGES

Janusz Brzozowski, Bo Liu

TL;DR

This paper investigates the "quotient complexity" (a measure of how complex a regular language is) for a specific subset of regular languages called "star-free languages." The authors demonstrate that for most common operations (like union, intersection, and concatenation), star-free languages exhibit the same worst-case complexity as general regular languages, with a few notable exceptions for product and reversal.

What Problem Does This Paper Address?

The paper delves into the realm of formal language theory, specifically focusing on the complexity of regular languages. A key concept is "quotient complexity," which, for a given language, is the number of distinct "left quotients" it has. Think of left quotients as different ways to "slice" the language based on prefixes. The authors are interested in how complex operations (like combining two languages) become when applied to languages within a particular subclass: star-free languages. Star-free languages are those that can be constructed from finite languages using only boolean operations (union, intersection, complement) and concatenation, but not the Kleene star operation (which allows for repetition). This restriction makes them simpler in some ways, and the question arises: does this simplification lead to lower complexity bounds for operations compared to general regular languages?

Methods

The core of the paper involves constructing specific star-free languages and analyzing their quotient complexity under various operations. The authors leverage the concept of "quotient automata," which are minimal deterministic finite automata (DFAs) whose state complexity is equivalent to the quotient complexity of the language. They construct these automata for their witness languages and then analyze the resulting automata for operations like union, intersection, product, and star. For proving upper bounds, they often rely on known results for general regular languages and show that these bounds are also achievable by star-free languages. For product and reversal, they introduce specific automaton constructions and use inductive arguments to establish reachability and distinguishability of states, which directly translates to quotient complexity.

Datasets

Not discussed in the paper. The paper deals with theoretical constructs (languages and automata) rather than empirical data.

Key Insights and Ideas

  • Star-free languages are surprisingly "regular" in complexity: For many common operations (union, intersection, difference, symmetric difference), star-free languages don't offer a complexity advantage over general regular languages. This is a significant finding, as one might expect the restriction on the Kleene star to simplify things more broadly.
  • Product and reversal are where star-free languages show differences: The paper highlights that for the product operation, the bounds for star-free languages can be lower than for general regular languages, though they still meet specific tight bounds. Reversal also shows a distinct bound for star-free languages.
  • The power of specific constructions: The authors ingeniously construct specific star-free languages (often using alphabets of size 2, 3, or 4) to demonstrate that the theoretical upper bounds for quotient complexity are indeed achievable. These constructions are crucial for proving the tightness of the bounds.
  • Aperiodic automata are key: Star-free languages are characterized by having aperiodic minimal DFAs (automata that don't perform non-trivial permutations of states). This property is implicitly used in the constructions and analysis.

Key Results

  • Boolean Operations (Union, Intersection, Difference, Symmetric Difference): The tight upper bound for these operations on star-free languages is $mn$, the same as for general regular languages.
  • Concatenation (Product): The tight upper bound for the product of two star-free languages $K$ and $L$ with quotient complexities $m$ and $n$ is $(m-1)2^n + 2^n - 1$. This is a specific bound that is met by certain star-free languages. There are also specific results for smaller alphabets and cases like $n=2$.
  • Star Operation: The tight bound for the star of a star-free language $L$ with quotient complexity $n$ is $2^{n-1} + 2^{n-3} - 1$ for $n \ge 3$. For smaller $n$, different bounds apply.
  • Reversal: For star-free languages, the tight bound for reversal is $2^n - 1$, which is slightly better than the general regular language bound of $2^n$.

Limitations and Future Work

  • Specific cases for product: The paper notes that for $n=2$, the bound for the product of star-free languages is 4, which is better than the general bound of 6. However, they also mention that a bound of $3m-2$ is achieved for certain cases, and they don't know if a bound of $3m-1$ can be reached.
  • Unary languages: The paper dedicates a section to unary languages (languages over a single-letter alphabet), noting that their complexity behavior is "special" and differs from the general case for most operations.
  • Open questions: The authors explicitly state that they do not know whether a specific bound ($3m-1$) for the product of star-free languages can be reached. They also mention that they have verified with computational tools (GAP) that certain bounds cannot be reached for small values of $n$.
  • Further exploration of specific subclasses: The paper's findings suggest that exploring the complexity of operations on other subclasses of regular languages could yield interesting results.

Summary updated

Abstract

The quotient complexity, also known as state complexity, of a regular language is the number of distinct left quotients of the language. The quotient complexity of an operation is the maximal quotient complexity of the language resulting from the operation, as a function of the quotient complexities of the operands. The class of star-free languages is the smallest class containing the finite languages and closed under boolean operations and concatenation. We prove that the tight bounds on the quotient complexities of union, intersection, difference, symmetric difference, concatenation and star for star-free languages are the same as those for regular languages, with some small exceptions, whereas 2 n -1 is a lower bound for reversal.
BibTeX
@article{brzozowski2012quotient,
  author = {Janusz Brzozowski and Bo Liu},
  title = {{QUOTIENT COMPLEXITY OF STAR-FREE LANGUAGES}},
  journal = {International Journal of Foundations of Computer Science},
  year = {2012},
  doi = {10.1142/s0129054112400515},
}
Figure