Complexity of NFA to DFA minimization with binary threshold

Question

What is the complexity of the following problem?

Given an NFA $A$ and a number $k\in \mathbb{N}$ in binary encoding, does there exist a DFA $B$ with at most $k$ states such that $L(A)=L(B)$?

Specifically, is it known whether this is PSPACE-complete or EXPTIME-complete?

This is the decision version of NFA to DFA minimization, but the size bound is given in binary. It's well known that if $k$ is given in unary, the problem is PSPACE-complete (by e.g., reduction from NFA universality).

The problem is clearly in EXPTIME: we can determinize $A$ to obtain an equivalent DFA of exponential size, and then minimize it. However, this method cannot be brought down to PSPACE, since the minimal output may indeed be of exponential size.

My intuition says this should be EXPTIME-complete, but I did not see any research on that.

Answer 1

The problem is in PSPACE, hence is PSPACE-complete.

DFA minimization is in NL; see Theorem 2.1 of [S. Cho and D.T. Huynh. The Parallel Complexity of Finite-State Automata Problems. Information and Computation, 97, 1-22 (1992)]

NL is contained in polyL (deterministic polylogarithmic space).

The subset construction can be implemented by a PSPACE transducer, i.e., a Turing machine whose work tape is PSPACE-bounded. Its output (on an extra tape) will be exponential in general.

By composing the PSPACE transducer with the polyL-machine in the standard space-efficient way (involving the (re-)computation of any bit the polyL-machine requires), we (even) get a PSPACE transducer that given an NFA computes a minimal equivalent DFA.