Nondeterministic state complexity of star-free languages (Q442152)

The class of star-free languages is a relevant subclass of regular languages, which can be described in terms of regular expressions, extended to include all boolean operators, but without Kleene star. Properties of this class have been widely investigated in the literature. In particular, concerning \textit{descriptional complexity}, the field of investigation where this paper can be classified, a recent interesting result shows that the exponential state gap between nondeterministic and deterministic finite automata can be achieved even restricting to star-free languages [\textit{H. Bordihn}, \textit{M. Holzer} and \textit{M. Kutrib}, Theor.\ Comput.\ Sci.\ 410, No. 35, 3209--3222 (2009; Zbl 1173.68030)].NEWLINENEWLINEThe paper investigates the nondeterministic state complexity of the basic operations on star-free languages. A similar investigation for the deterministic case has been done in [\textit{J. Brzozowski} and \textit{B. Liu}, Int.\ J.\ Found.\ Comput.\ Sci.\ 23, No. 6, 1261--1276 (2012; Zbl 1272.68206)]. It is shown that the lowed bounds which are known for those operations on regular languages can be achieved even restricting to star-free languages, namely, the nondeterministic state complexities of those operations remain the same restricting to star-free languages. The case of unary star-free languages, namely, star-free languages defined over a one letter alphabet, is also considered. Only one relevant difference with respect to the general case is discovered: the complementation of unary star-free languages uses a quadratic number of states, while the same operation in the general case requires exponentially many states.