Return to Answer

While the algorithm above is fine, it may use exponential space, while this problem for DFAs should be polynomial time equivalent to (the complement of) the universality problem for NFAs. This makes it PSPACE-complete (according to this answer: http://mathoverflow.net/questions/24343/emptiness-and-determinization-of-nfas/24422#24422). The problem here for regular expressions or NFAs might be even harder, since a minimal DFA might have exponentially many states.

This problem for DFAs $\leq^p \overline{\mathrm{NFA-UNIV}}$:

Given a DFA $M$ with alphabet $\Sigma$, first compute $\overline{M}$ (DFA for $\overline{L(M)}$) by switching final and non final states, let $\delta$ be its transition function. Now construct an NFA $N$ with the same states, alphabet $\{a\}$ and transition function $\delta'$ s.t.

$$ \delta'(z,a) = \{z' \mid \exists b: \delta(z,b) = z'\}$$

If $N$ accepts a word $a^l$ then $\overline{M}$ accepts a word of length $l$ and $M$ does not accept all words of length $l$. So there is an $l$ s.t. $M$ accepts all words of length $l$ if and only if $L(N)\neq\{a\}^*$.

$\overline{\mathrm{NFA-UNIV}} \leq^p $ this problem for DFAs:

For the other direction we use the same names but the construction is carried out in the opposite way. W.l.o.g. we assume $N$ has only one initial state. Let $\Sigma$ be the alphabet of $N$ and $k$ maximal s.t. $\exists z,a: k = |\delta'(z,a)|$. The alphabet of $\overline{M}$ is now $\Sigma \times \{1,\dots,k\}$ and if $\delta'(z,a) = \{z_{i_1},\dots,z_{i_m}\}$ we define $$\delta(z,(a,j))=\begin{cases}z_{i_j}&j\leq m \\ E & \text{else}\end{cases}$$ where $E$ is some special new error state (i.e. non final and $\forall a: \delta(E,a)=E$). Now a path form the initial state to a final state in $N$ maps to such a path in $\overline{M}$ (and vice versa). Finally we define $M$ by switching final and non final states of $\overline{M}$.

While the algorithm above is fine, it may use exponential space, while this problem for DFAs should be polynomial time equivalent to (the complement of) the universality problem for NFAs. This makes it PSPACE-complete (according to this answer: https://mathoverflow.net/questions/24343/emptiness-and-determinization-of-nfas/24422#24422). The problem here for regular expressions or NFAs might be even harder, since a minimal DFA might have exponentially many states.

This problem for DFAs $\leq^p \overline{\mathrm{NFA-UNIV}}$:

Given a DFA $M$ with alphabet $\Sigma$, first compute $\overline{M}$ (DFA for $\overline{L(M)}$) by switching final and non final states, let $\delta$ be its transition function. Now construct an NFA $N$ with the same states, alphabet $\{a\}$ and transition function $\delta'$ s.t.

$$ \delta'(z,a) = \{z' \mid \exists b: \delta(z,b) = z'\}$$

If $N$ accepts a word $a^l$ then $\overline{M}$ accepts a word of length $l$ and $M$ does not accept all words of length $l$. So there is an $l$ s.t. $M$ accepts all words of length $l$ if and only if $L(N)\neq\{a\}^*$.

$\overline{\mathrm{NFA-UNIV}} \leq^p $ this problem for DFAs:

For the other direction we use the same names but the construction is carried out in the opposite way. W.l.o.g. we assume $N$ has only one initial state. Let $\Sigma$ be the alphabet of $N$ and $k$ maximal s.t. $\exists z,a: k = |\delta'(z,a)|$. The alphabet of $\overline{M}$ is now $\Sigma \times \{1,\dots,k\}$ and if $\delta'(z,a) = \{z_{i_1},\dots,z_{i_m}\}$ we define $$\delta(z,(a,j))=\begin{cases}z_{i_j}&j\leq m \\ E & \text{else}\end{cases}$$ where $E$ is some special new error state (i.e. non final and $\forall a: \delta(E,a)=E$). Now a path form the initial state to a final state in $N$ maps to such a path in $\overline{M}$ (and vice versa). Finally we define $M$ by switching final and non final states of $\overline{M}$.

While the algorithm above is fine, it may use exponential space, while this problem for DFAs should be polynomial time equivalent to (the complement of) the universality problem for NFAs. This makes it PSPACE-complete (according to this answer: http://mathoverflow.net/questions/24343/emptiness-and-determinization-of-nfas/24422#24422). The problem here for regular expressions or NFAs might be even harder, since a minimal DFA might have exponentially many states.

This problem for DFAs $\leq^p \overline{\mathrm{NFA-UNIV}}$:

Given a DFA $M$ with alphabet $\Sigma$, first compute $\overline{M}$ (DFA for $\overline{L(M)}$) by switching final and non final states, let $\delta$ be its transition function. Now construct an NFA $N$ with the same states, alphabet $\{a\}$ and transition function $\delta'$ s.t.

$$ \delta'(z,a) = \{z' \mid \exists b: \delta(z,b) = z'\}$$

If $N$ accepts a word $a^l$ then $\overline{M}$ accepts a word of length $l$ and $M$ does not accept all words of length $l$. So there is a $l$ s.t. $M$ accepts all words of length $l$ if and only if $L(N)\neq\{a\}^*$.

$\overline{\mathrm{NFA-UNIV}} \leq^p $ this problem for DFAs:

For the other direction we use the same names but the construction is carried out in the opposite way. W.l.o.g. we assume $N$ has only one initial state. Let $\Sigma$ be the alphabet of $N$ and $k$ maximal s.t. $\exists z,a: k = |\delta'(z,a)|$. The alphabet of $\overline{M}$ is now $\Sigma \times \{1,\dots,k\}$ and if $\delta'(z,a) = \{z_{i_1},\dots,z_{i_m}\}$ we define $$\delta(z,(a,j))=\begin{cases}z_{i_j}&j\leq m \\ E & \text{else}\end{cases}$$ where $E$ is some special new error state (i.e. non final and $\forall a: \delta(E,a)=E$). Now a path form the initial state to a final state in $N$ maps to such a path in $\overline{M}$ (and vice versa). Finally we define $M$ by switching final and non final states of $\overline{M}$.

While the algorithm above is fine, it may use exponential space, while this problem for DFAs should be polynomial time equivalent to (the complement of) the universality problem for NFAs. This makes it PSPACE-complete (according to this answer: http://mathoverflow.net/questions/24343/emptiness-and-determinization-of-nfas/24422#24422). The problem here for regular expressions or NFAs might be even harder, since a minimal DFA might have exponentially many states.

This problem for DFAs $\leq^p \overline{\mathrm{NFA-UNIV}}$:

Given a DFA $M$ with alphabet $\Sigma$, first compute $\overline{M}$ (DFA for $\overline{L(M)}$) by switching final and non final states, let $\delta$ be its transition function. Now construct an NFA $N$ with the same states, alphabet $\{a\}$ and transition function $\delta'$ s.t.

$$ \delta'(z,a) = \{z' \mid \exists b: \delta(z,b) = z'\}$$

If $N$ accepts a word $a^l$ then $\overline{M}$ accepts a word of length $l$ and $M$ does not accept all words of length $l$. So there is an $l$ s.t. $M$ accepts all words of length $l$ if and only if $L(N)\neq\{a\}^*$.

$\overline{\mathrm{NFA-UNIV}} \leq^p $ this problem for DFAs:

For the other direction we use the same names but the construction is carried out in the opposite way. W.l.o.g. we assume $N$ has only one initial state. Let $\Sigma$ be the alphabet of $N$ and $k$ maximal s.t. $\exists z,a: k = |\delta'(z,a)|$. The alphabet of $\overline{M}$ is now $\Sigma \times \{1,\dots,k\}$ and if $\delta'(z,a) = \{z_{i_1},\dots,z_{i_m}\}$ we define $$\delta(z,(a,j))=\begin{cases}z_{i_j}&j\leq m \\ E & \text{else}\end{cases}$$ where $E$ is some special new error state (i.e. non final and $\forall a: \delta(E,a)=E$). Now a path form the initial state to a final state in $N$ maps to such a path in $\overline{M}$ (and vice versa). Finally we define $M$ by switching final and non final states of $\overline{M}$.

This problem for DFAs should be polynomial time equivalent to (the complement of) the universality problem for NFAs, which is PSPACE-complete (according to this answer: http://mathoverflow.net/questions/24343/emptiness-and-determinization-of-nfas/24422#24422). The problem here for regular expressions or NFAs might be even harder.

This problem for DFAs $\leq^p \overline{\mathrm{NFA-UNIV}}$:

Given a DFA $M$ with alphabet $\Sigma$, first compute $\overline{M}$ (DFA for $\overline{L(M)}$) by switching final and non final states, let $\delta$ be its transition function. Now construct an NFA $N$ with the same states, alphabet $\{a\}$ and transition function $\delta'$ s.t.

$$ \delta'(z,a) = \{z' \mid \exists b: \delta(z,b) = z'\}$$

If $N$ accepts a word $a^l$ then $\overline{M}$ accepts a word of length $l$ and $M$ does not accept all words of length $l$. So there is a $l$ s.t. $M$ accepts all words of length $l$ if and only if $L(N)\neq\{a\}^*$.

$\overline{\mathrm{NFA-UNIV}} \leq^p $ this problem for DFAs:

For the other direction we use the same names but the construction is carried out in the opposite way. W.l.o.g. we assume $N$ has only one initial state. Let $\Sigma$ be the alphabet of $N$ and $k$ maximal s.t. $\exists z,a: k = |\delta'(z,a)|$. The alphabet of $\overline{M}$ is now $\Sigma \times \{1,\dots,k\}$ and if $\delta'(z,a) = \{z_{i_1},\dots,z_{i_m}\}$ we define $$\delta(z,(a,j))=\begin{cases}z_{i_j}&j\leq m \\ E & \text{else}\end{cases}$$ where $E$ is some special new error state (i.e. non final and $\forall a: \delta(E,a)=E$). Now a path form the initial state to a final state in $N$ maps to such a path in $\overline{M}$ (and vice versa). Finally we define $M$ by switching final and non final states of $\overline{M}$.

While the algorithm above is fine, it may use exponential space, while this problem for DFAs should be polynomial time equivalent to (the complement of) the universality problem for NFAs. This makes it PSPACE-complete (according to this answer: http://mathoverflow.net/questions/24343/emptiness-and-determinization-of-nfas/24422#24422). The problem here for regular expressions or NFAs might be even harder, since a minimal DFA might have exponentially many states.

This problem for DFAs $\leq^p \overline{\mathrm{NFA-UNIV}}$:

Given a DFA $M$ with alphabet $\Sigma$, first compute $\overline{M}$ (DFA for $\overline{L(M)}$) by switching final and non final states, let $\delta$ be its transition function. Now construct an NFA $N$ with the same states, alphabet $\{a\}$ and transition function $\delta'$ s.t.

$$ \delta'(z,a) = \{z' \mid \exists b: \delta(z,b) = z'\}$$

If $N$ accepts a word $a^l$ then $\overline{M}$ accepts a word of length $l$ and $M$ does not accept all words of length $l$. So there is a $l$ s.t. $M$ accepts all words of length $l$ if and only if $L(N)\neq\{a\}^*$.

$\overline{\mathrm{NFA-UNIV}} \leq^p $ this problem for DFAs:

For the other direction we use the same names but the construction is carried out in the opposite way. W.l.o.g. we assume $N$ has only one initial state. Let $\Sigma$ be the alphabet of $N$ and $k$ maximal s.t. $\exists z,a: k = |\delta'(z,a)|$. The alphabet of $\overline{M}$ is now $\Sigma \times \{1,\dots,k\}$ and if $\delta'(z,a) = \{z_{i_1},\dots,z_{i_m}\}$ we define $$\delta(z,(a,j))=\begin{cases}z_{i_j}&j\leq m \\ E & \text{else}\end{cases}$$ where $E$ is some special new error state (i.e. non final and $\forall a: \delta(E,a)=E$). Now a path form the initial state to a final state in $N$ maps to such a path in $\overline{M}$ (and vice versa). Finally we define $M$ by switching final and non final states of $\overline{M}$.