<p><strong>Short Answer</strong></p>
<p>The encoding doesn't seem to affect the problem's complexity.</p>
<p><strong>Longer Answer</strong></p>
<p>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.</p>
<p>If <span class="math-container">$c$</span> denotes the alphabet size, <span class="math-container">$k$</span> denotes the number of automata, and <span class="math-container">$m$</span> denotes the number of states per automaton, then under all reasonable encodings that I can think of, the input size will remain at least <span class="math-container">$max\{c, k, m\}$</span> and at most <span class="math-container">$p(c, k, m)$</span> for some multivariate polynomial <span class="math-container">$p$</span>.</p>
<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.</p>
<p>It follows that the new variant of the problem is still PSPACE-complete.</p>
<p><strong>Unary Automata</strong></p>
<p>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 &quot;pans&quot; or &quot;balloons&quot;.  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.</p>
<p>The intersection problem for Unary DFA's is NP-complete as seen by related results in <a href="https://dl.acm.org/doi/10.1145/800125.804029" rel="nofollow noreferrer">Meyer and Stockmeyer (1973)</a> and <a href="https://dl.acm.org/doi/10.1007/BF00263744" rel="nofollow noreferrer">Galil (1976)</a>.  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.</p>

CC BY-SA 4.0
2023-01-04T08:32:22.880Z
It might also be worth noting that the DFA intersection problem is still PSPACE-complete even if the DFA's are small.  In other words, if you are given $n$ DFA's each with at most $\log(n)$ states.  An argument for this can be found in Theorem 7 here: http://michaelwehar.com/documents/mwehar_INE_5_9_14.pdf
Michael Wehar
CC BY-SA 4.0
2023-01-04T08:18:01.293Z
2023-01-04T08:28:43.230Z
2023-01-04T08:28:43.230Z
Michael Wehar
<p>The problem remains PSPACE complete under any reasonable encoding of the DFAs, regardless of whether their states are encoded in unary or binary.</p>
<p>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 <span class="math-container">$O(|Q|\cdot |\Sigma|)$</span> (where <span class="math-container">$Q$</span> is the state space and <span class="math-container">$|\Sigma|$</span> is the alphabet). Therefore, including <span class="math-container">$\Sigma$</span> as a list of <span class="math-container">$|\Sigma|$</span> binary strings, or encoding just <span class="math-container">$|\Sigma|$</span> and inferring this list implicitly is polynomially equivalent.</p>
<p>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).</p>

CC BY-SA 4.0
2023-01-03T13:35:05.567Z
2023-01-03T13:35:05.567Z
Shaull
<p>The intersection non-emptiness problem is defined as follows:</p>
<blockquote>
<p>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.</p>
</blockquote>
<p>This problem is PSPACE-complete.</p>
<p>Under which encodings of the list of finite automata is the intersection non-emptiness problem PSPACE-complete?</p>
<p>For instance, would the encoding consisting of bit-strings of the form <span class="math-container">$q_1 \# a \# q_2 \#$</span> representing transition <span class="math-container">$\delta(q_1,a) = q_2$</span> yield PSPACE-completeness? I'm assuming that the states take <span class="math-container">$\log_2(n)$</span> bits and the tape symbols <span class="math-container">$\log_2 |\Sigma|$</span> bits to represent.</p>
<p><strong>Edit</strong></p>
<p>I could also choose to encode each state with <span class="math-container">$n$</span> bits and each letter with <span class="math-container">$|\Sigma|$</span> bits. Would the problem still be PSPACE-complete in this case?</p>

CC BY-SA 4.0
2023-01-03T11:28:12.513Z
The problem would be PSPACE complete basically under any reasonable encoding - like what you suggest. You can make it harder by encoding the automata in some very convoluted way, which would render their parsing difficult, or make it easy by encoding the automata with padding. But these are unnatural ways.
Shaull
CC BY-SA 4.0
2023-01-03T14:58:45.807Z
Regarding your edit, assuming $n$ is the number of states, encoding each state and each letter in unary as you suggest doesn't make a difference, as it only increases the input size by a polynomial amount.
Neal Young
<cc.complexity-theory><automata-theory>
Encoding of finite automata in Intersection Non-Emptiness problem
user1868607
# Encoding of finite automata in Intersection Non-Emptiness problem

(Asked by: username_0 on 2023-01-03)

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?

**Tags:** cc.complexity-theory, automata-theory
> **Comments:**
> **username_1**: The problem would be PSPACE complete basically under any reasonable encoding - like what you suggest. You can make it harder by encoding the automata in some very convoluted way, which would render their parsing difficult, or make it easy by encoding the automata with padding. But these are unnatural ways.  
> **username_2**: Regarding your edit, assuming $n$ is the number of states, encoding each state and each letter in unary as you suggest doesn't make a difference, as it only increases the input size by a polynomial amount.  

---

## 2 answers

### Answer by username_3 on 2023-01-04. Score: 1 | Accepted answer

**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)](https://dl.acm.org/doi/10.1145/800125.804029) and [Galil (1976)](https://dl.acm.org/doi/10.1007/BF00263744). 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.

> **Comments:**
> **username_3**: It might also be worth noting that the DFA intersection problem is still PSPACE-complete even if the DFA's are small.  In other words, if you are given $n$ DFA's each with at most $\log(n)$ states.  An argument for this can be found in Theorem 7 here: http://michaelwehar.com/documents/mwehar_INE_5_9_14.pdf  

---

### Answer by username_1 on 2023-01-03. Score: 5

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


---

