2
$\begingroup$

Let $A$ be a DFA over a finite alphabet $ \Sigma$. Find an algorithm that indicates if $A$ accepts a palindrome and give the complexity of this algorithm.

Here is my solution:

If we denote $^t A$ the transpose of the finite automaton then in order to see if $A$ accepts a palindrome we need to look at the product automaton of $A$ and $^t A$ and find if this product automaton accepts a word. If yes then this is word is a palindrome.

Finding the transpose of a finite automaton takes $O(|V|)$ where $V$ is the number of transition of our finite automaton. Take the product of $A$ and its transpose takes $O(|V|^2)$. And looking if an automaton accept a word takes $O(|V|^{|S|})$, where $|S|$ is the number of states of our finite automaton. So the final complexity I get for the algorithm I described above is: $$O(|V|^{3 + 2|S|})$$

Now my question is:

Is it possible to improve the complexity? And is it possible to give a proof (using I guess adversary argument) to prove that there isn't a better algorithm (in the sense of complexity) to find if a finite automaton accepts a palindrome?

$\endgroup$
2
$\begingroup$

You can solve this in $O(n^2)$, where $n$ is the number of states in the original DFA (or NFA), using your idea. Compute the product automaton of the original automaton and its reverse. The new automaton contains $O(n^2)$ states. As to the number of edges, in the original DFA, each state has $|\Sigma|$ outgoing edges, and in its reverse, there are $|\Sigma|n$ transitions overall. Let us denote by $a(q)$ the number of outgoing transitions from $q$ in the original DFA, and by $b(q)$ the number in the reverse DFA. Using $Q$ for the set of states, the total number of transitions in the product automaton is $$ \sum_{q_1,q_2 \in Q} a(q_1) b(q_2) = \sum_{q_1,q_2 \in Q} |\Sigma| b(q_2) = |\Sigma| n \sum_{q_2 \in Q} b(q_2) = |\Sigma|^2 n^2. $$ Assuming $|\Sigma|$ is constant, this is $O(n^2)$. Now check whether some final state is reachable from some initial state, using BFS/DFS, in time $O(n^2)$.

We can prove an essentially matching lower bound given SETH. Recall that SETH states that for every $\epsilon > 0$ there is $k$ such that $k$-SAT cannot be solved in time $O(2^{(1-\epsilon) n})$, where $n$ is the number of variables. We will show how to reduce $k$-SAT to your problem.

Given a $k$-SAT formula $\phi$ with $n$ variables and $m = O(n^k)$ clauses, consider the following language $L$ of all words of the form $\alpha x \beta \gamma y \delta$, where:

  1. $|\alpha| = |\beta| = |\gamma| = |\delta| = n/2$, $|x| = |y| = m$.
  2. We think of $\alpha$ as an assignment for the first $n/2$ variables. If $x_i = 0$ then $\alpha$ must satisfy the $i$th clause.
  3. We think of $\beta$ as an assignment for the last $n/2$ variables. If $y^R_i = y_{m+1-i} = 1$ then $\beta$ must satisfy the $i$th clause.

Any word in $L \cap L^R$ must be of the form $\alpha x \beta \beta^R x^R \alpha^R$, and so by construction $\alpha\beta$ satisfies $\phi$. Conversely, if $\alpha\beta$ satisfies $\phi$, then we can choose $x$ so that the corresponding word is in $L \cap L^R$, Hence $\phi$ is satisfiable iff $L \cap L^R$ is non-empty.

How many states do we need to accept $L$? We can read and store $\alpha$ using $O(2^{n/2})$ many states. Therefore using $O(2^{n/2} m)$ states, we can verify the second condition (on $\alpha x$). Similarly, we can verify the third condition (on $\beta y$) using $O(2^{n/2} m)$ more states. Verifying the first condition takes $O(n+m)$ more states, for a grand total of $O(2^{n/2} m) = O(2^{n/2 + o(1)})$ states.

If your problem could be solve in time $O(N^{2-\delta})$ (where $N$ is the number of states in the input automaton), then we would get an algorithm for $k$-SAT running in time $O(2^{(1-\delta/2)n + o(1)})$, and so obtain a contradiction if $\delta/2 \geq \epsilon$. This shows that assuming SETH, your problem cannot be solved in $O(N^{2-\delta)}$ for any $\delta > 0$.

$\endgroup$
  • $\begingroup$ I don’t see any $O(1)$ in the answer. $\endgroup$ – Yuval Filmus Feb 28 at 19:24
  • 1
    $\begingroup$ Assuming the alphabet is fixed, the number of transitions only differs from the number of states by a constant factor. $\endgroup$ – Yuval Filmus Mar 3 at 16:07
  • 1
    $\begingroup$ If you have multiple initial states, add a new initial state with epsilon transitions to all of them. $\endgroup$ – Yuval Filmus Mar 3 at 16:08
  • $\begingroup$ I don't see why the number of transitions only differs from the number of states by a constant. I mean each state can have a transition to every other state in an NFA. And in this case the number of transitions is : $O(n^2)$... and not $O(n)$ $\endgroup$ – Thinking Mar 3 at 17:21
  • 1
    $\begingroup$ This can't really happen since the NFA is not arbitrary – it's obtained from a DFA by reversing all arrows. See my updated answer. $\endgroup$ – Yuval Filmus Mar 3 at 19:07
1
$\begingroup$

You can solve this problem in polynomial time. For simplicity let's assume the DFA has a single accepting state. If it has multiple you can just run this algorithm for each accepting state until you return $\text{YES}$ or every accepting state has been unsuccessfully tried and we return $\text{NO}$. Let $\text{goto}(x, s) = y$ indicate that there is a transition from state $x$ to state $y$ on symbol $s$.

We use a meet in the middle strategy. We have a tuple $(b, e)$ where $b$ is the state reached from the beginning, and $e$ is the state reached from the end.

We build a list of these tuples. Initially we have only one such tuple $(b, e) = (\text{init}, \text{accept})$. Then as long as our list has a tuple that hasn't been expanded before, we expand tuple $(b, e)$ by adding all $(b', e')$ to the list for each possible symbol $s$ where $\text{goto}(b, s) = b'$ and $\text{goto}(e', s) = e$.

We return $\text{YES}$ if we have added $(x, x)$ to the list, or $(x, y)$ where some $s$ exists such that $\text{goto}(x, s) = y$. The former case indicates an even length palindrome, the latter an odd length palindrome.

Why is this polynomial time? Hint: there are only $|S|^2$ possible tuples $(b, e)$ we ever need to expand.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.