Syntactic Complexities of Six Classes of Star-Free Languages
Janusz Brzozowski, Baiyu Li, David Liu · UWSpace (University of Waterloo) · 2012
The syntactic complexity of a regular language is the cardinality of its syntactic semigroup. The syntactic complexity of a subclass of regular languages is the maximal syntactic complexity of languages in that subclass, taken as a function of the state complexity $n$ of these languages. We study the syntactic complexity of six subclasses of star-free languages. We find a tight upper bound of $(n-1)!$ for finite/cofinite and reverse definite languages, and a lower bound of $\lfloor {\mathbf e}\cdot (n-1)!\rfloor$ for definite languages, where ${\mathbf e}$ is the base of the natural logarithms. We also find tight upper bounds for languages accepted by monotonic, partially monotonic and ``nearly monotonic'' automata. All these bounds are significantly lower than the bound $n^n$ for arbitrary regular languages. Also, witness languages reaching these bounds require alphabets that grow with $n$. The syntactic complexity of arbitrary star-free languages remains open.