Quotient Complexity of Star-Free Languages

Janusz Brzozowski, Bo Liu

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 the bound for reversal is $2^n-1$.

Introduction

In automata theory, quotient complexity (or state complexity) serves as a fundamental metric for the structural complexity of a regular language, representing the size of its minimal deterministic finite automaton (DFA). While the worst-case complexity bounds for operations on general regular languages are well-established, research often focuses on whether these bounds decrease for specific subclasses. This paper investigates star-free languages—those definable without the Kleene star, using only boolean operations and concatenation. Despite their inability to perform modulo counting, we explore whether they can still achieve the maximal complexity of general regular languages.

Methodology

The study employs a constructive mathematical approach to establish tight upper bounds. To prove a bound is tight, the authors construct specific "witness" star-free languages that reach the theoretical maximum state count after an operation.

A critical component of this methodology is the construction of aperiodic automata. Since star-free languages correspond to automata without non-trivial permutations (loops that count), the authors utilize non-decreasing transformations to ensure aperiodicity. Standard NFA-to-DFA subset constructions are analyzed for operations like concatenation, star, and reversal to determine the reachability and distinguishability of state subsets. Furthermore, the authors utilized the GAP (Groups, Algorithms, Programming) software package to verify these bounds for small state counts, identifying specific edge cases where general regular language bounds do not apply.

Key Results

Boolean Operations

For boolean operations such as union, intersection, and symmetric difference, the quotient complexity for star-free languages with $m$ and $n$ states is $mn$. This matches the bound for general regular languages. The construction typically involves a product automaton where each state is a pair from the operand DFAs.

Concatenation (Product)

The tight bound for the concatenation of two star-free languages with $m$ and $n$ states is $(m-1)2^n + 2^{n-1}$, provided $n \geq 3$. This result is significant as it demonstrates that the structural restrictions of star-free languages do not lower the complexity of the product operation compared to general regular languages.

Star and Reversal

The Kleene star operation on a star-free language with $n$ states yields a tight bound of $2^{n-1} + 2^{n-2}$ for quaternary alphabets, again matching the general case.

Reversal is the primary exception where the bound differs. For star-free languages, the bound is $2^n - 1$, whereas it is $2^n$ for general regular languages. The aperiodicity of the automaton ensures that the "all-states" subset in the reversal construction is always unreachable, effectively shaving off one state from the maximum possible complexity.

Conclusion

This research reveals that star-free languages, despite their "counter-free" nature, are almost as complex as general regular languages in terms of state complexity. The ability to perform "threshold counting" (e.g., "at least $k$ occurrences") allows these languages to reach the same exponential peaks for most operations. The slight reduction in the reversal bound highlights a subtle structural constraint imposed by aperiodicity. Future work may explore whether these bounds can be achieved with smaller alphabet sizes, such as binary or ternary alphabets.

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 the bound for reversal is 2^n-1.
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},
}

Loading related content...

Figure