Encoding of finite automata in Intersection Non-Emptiness problem

Question

The intersection non-emptiness problem is defined as follows:

Given a list of deterministic finite automata as input, the goal is to determine whether or not their associated regular languages have a non-empty intersection. In other, the goal is to determine if there exists a string that is accepted by all of the automata in the list.

This problem is PSPACE-complete.

Under which encodings of the list of finite automata is the intersection non-emptiness problem PSPACE-complete?

For instance, would the encoding consisting of bit-strings of the form $q_1 \# a \# q_2 \#$ representing transition $\delta(q_1,a) = q_2$ yield PSPACE-completeness? I'm assuming that the states take $\log_2(n)$ bits and the tape symbols $\log_2 |\Sigma|$ bits to represent.

Edit

I could also choose to encode each state with $n$ bits and each letter with $|\Sigma|$ bits. Would the problem still be PSPACE-complete in this case?

Answer 1

Short Answer

The encoding doesn't seem to affect the problem's complexity.

Longer Answer

By changing the encoding, you are varying how the input size for the problem relates to the alphabet size, the number of automata, and the number of states per automaton.

If $c$ denotes the alphabet size, $k$ denotes the number of automata, and $m$ denotes the number of states per automaton, then under all reasonable encodings that I can think of, the input size will remain at least $max\{c, k, m\}$ and at most $p(c, k, m)$ for some multivariate polynomial $p$.

Therefore, using the typical PSPACE algorithm for the DFA intersection problem (along with potentially translating the input encoding) will still use at most polynomial space in terms of the new encoding's input size. Similarly, the typical reduction for PSPACE-hardness will still yield a polynomial sized input for the DFA intersection problem under the new input encoding.

It follows that the new variant of the problem is still PSPACE-complete.

Unary Automata

This question could be more interesting if we consider Unary DFA's (or other special subclasses of automata). Unary DFA's are much simpler taking the form of "pans" or "balloons". Their state diagrams are essentially directed cycles with a directed path attached to them. A natural improvement to encode such automata is to just list the path length in binary, the cycle length in binary, and binary labels for their final states. Without many final states, such an encoding could be logarithmic in size instead of linear.

The intersection problem for Unary DFA's is NP-complete as seen by related results in Meyer and Stockmeyer (1973) and Galil (1976). So it might be interesting to ask whether the encoding for unary DFA's affects the problem's complexity. However, as far as I can tell, even though the encoding can sometimes greatly affect the size of each automaton, it doesn't seem to change the NP-completeness of the problem.

Answer 2

The problem remains PSPACE complete under any reasonable encoding of the DFAs, regardless of whether their states are encoded in unary or binary.

The fundamental reason for this is that the transition function has to be encoded as either a list of transitions or as a list of transition-matrices (or some equivalent notion), and this representation is already $O(|Q|\cdot |\Sigma|)$ (where $Q$ is the state space and $|\Sigma|$ is the alphabet). Therefore, including $\Sigma$ as a list of $|\Sigma|$ binary strings, or encoding just $|\Sigma|$ and inferring this list implicitly is polynomially equivalent.

This doesn't really have anything to do with the particular problem of DFA intersection emptiness, it's true in general for algorithms on DFAs and NFAs (unless you restrict to algorithms in very low complexity classes, where you cannot afford this polynomial translation between encodings).