Finite-automaton aperiodicity is PSPACE-complete. (English) Zbl 0733.68038

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 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.


68Q25 Analysis of algorithms and problem complexity
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q45 Formal languages and automata


Zbl 0603.68059
Full Text: DOI


[1] Cho, S.; Huynh, D.T., The parallel complexity of finite state automata problems, () · Zbl 0755.68051
[2] Hardy, G.H.; Wright, E.M., An introduction to the theory of numbers, (), 343 · Zbl 0020.29201
[3] Hopcroft, J.; Ullman, J., Introduction to automata theory, languages, and computation, (1979), Addison-Wesley Reading, MA · Zbl 0426.68001
[4] Immerman, N., Nondeterministic space is closed under complement, SIAM J. comput., 17, 935-938, (1988) · Zbl 0668.68056
[5] Kozen, D., Lower bounds for natural proof systems, Proc. 18th IEEE ann. symp. on foundations of comput. sci., 254-266, (1977)
[6] Savitch, W.J., Relationship between nondeterministic and deterministic tape complexities, J. comput. system. sci., 4, 177-192, (1970) · Zbl 0188.33502
[7] Schützenberger, M.P., On finite monoids having only trivial subgroups, Inform. and control, 8, 190-194, (1965) · Zbl 0131.02001
[8] Simon, I., Piecewise testable events, (), 214-222
[9] Stern, J., Complexity of some problems from the theory of automata, Inform. and control, 66, 163-176, (1985) · Zbl 0603.68059
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.