Finite-automaton aperiodicity is PSPACE-complete (Q809608)

The following three algorithmical problems are investigated. Given a minimum-state deterministic finite automaton M, is the language L(M) 1) a star-free language (a language expressible through regular expressions without *-operation)? 2) a dot-depth language? 3) a piecewise testable language? It is shown that Problem 1 is PSPACE-complete, and Problems 2 and 3 are logspace complete for NLOG. This solves the open problem from \textit{J. Stern} [Inf. Control 66, 163-176 (1985; Zbl 0603.68059)], where a polynomial space algorithm for Problem 1 and polynomial time algorithms for Problems 2 and 3 are presented.