Regular expression star-freeness is PSPACE-complete (Q2763598)

Star-free languages form a subclass of regular languages: They are obtained from the finite languages by a finite number of applications of the operations of union, complement and product. By Schützenberger's theorem [\textit{M. P. Schützenberger}, J. Inf. Control 8, 190-194 (1965; Zbl 0131.02001)] a regular expression is star-free iff it is recognized by an aperiodic DFA (deterministic finite automaton). [\textit{J. Stern}, J. Inf. Control 66, 163-176 (1985; Zbl 0603.68059)] proved that the problem of deciding whether a DFA is aperiodic is \textbf{Co-NP}-hard and belongs to \textbf{PSPACE}. [\textit{S.~Cho} and \textit{D.~T.~Huynh}, Theor. Comput. Sci. 88, 99-116 (1991; Zbl 0733.68038)] strengthened Stern's result by showing that this problem is in fact \textbf{PSPACE}-complete. Here it is proved that the problem of deciding if a regular expression denotes a star-free language is \textbf{PSPACE}-complete.NEWLINENEWLINEFor the entire collection see [Zbl 0977.00022].