It is well-known that deciding whether an NFA or a regular expression define a counter-free/star-free language is PSPACE-complete.
Does the problem become easier if I have a DFA as input? What's the complexity in this case?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
I've found it in the literature [1], it's PSPACE-complete even for DFAs.
Sang Cho, Dung T. Huynh
Finite-automaton aperiodicity is PSPACE-complete,
Theoretical Computer Science, Volume 88, Issue 1, 1991, Pages 99-116