Is counting the words in a finite regular language #P-complete?

Question

Almost the exact same question was asked here, but nobody proved or cited its #P-completeness! I found this question because I proved it is #P-complete (proof below), and the proof was trivial, but I couldn't find it anywhere on the web or in the discussion on that question! (One person commented "I suspect it is #P-complete".) So either my proof is wrong, which you can judge for yourself, or the result is novel, which I would think is highly unlikely. Which is it?

---

Proof:

Consider the set of regular expressions formed by the union and concatenation of symbols from $(\Sigma\cup{.}),ドル where $\Sigma$ is an alphabet and $.$ is a symbol for any $l\in\Sigma$. I will show that #SAT reduces in $O(mn)$ time to counting the number of strings that satisfy such a regex, where $m$ is the number of clauses and $n$ is the number of variables in the given formula $\varphi$.

The reduction is very simple. First, reduce #SAT to #UNSAT by noting that if $\varphi$ has $n$ variables, then $\#\text{SAT}(\varphi) = 2^n - \#\text{UNSAT}(\varphi)$. So now we have to count the number of falsifying assignments of the variables of $\varphi$.

To falsify $\varphi,ドル it suffices to falsify just one clause. We therefore want to find $$\left|\bigcup \limits_{C\in\varphi}F(C)\right|$$ where $F(C)$ is the set of assignments of literals that falsify $C$.

We thus write a regex representing the language of falsifying assignments for each clause. Using $\Sigma = \{0,1\},ドル and letting $r_i$ be the $i^{th}$ symbol of a regex $r,ドル the regex for the language of assignments that falsify a clause $C$ is $$ r_i = \begin{cases} 0 & \text{if } x_i\in C \\ 1 & \text{if } \overline{x_i}\in C \\ . & \text{otherwise} \end{cases} $$

We then take the union of the regexes for each clause $C\in\varphi$. For example, if $\varphi = (x_1\vee \overline{x_2}\vee x_3) \wedge (x_1\vee x_3\vee \overline{x_4})\wedge (\overline{x_1}\vee \overline{x_4})$ we would have $r = $010.|0.01|1..1, where | denotes union.

The construction yields a union of $m$ strings, each of $n$ symbols. Thus the reduction takes $O(mn)$ time and the size of the regex-counting instance is polynomial in the size of the formula. Further, any regular expression that uses only concatenation, dot, and union represents a finite regular language (specifically, there is no Kleene star). So since we can solve #SAT by counting strings that satisfy such a regex, we can say that counting the words in a finite language is #P-complete.

• Chao Xu: "Almost the exact same question" they are very different. Your languages are finite.
• Marzio De Biasi: @ChaoXu: but if it is #P-complete for finite languages, then the problem "Given an NFA, count the number of matching words of length $k$" (the linked problem) is #P-complete when $k$ is given in unary ... so the two questions are not so different. However it seems a known result (see for example: dl.acm.org/citation.cfm?id=313803). Note that the problem is in P for deterministic finite automata.
• Huck Bennett: @ChaoXu: How? I actually spent awhile thinking about this issue before Marzio's comment which is (I think) completely right.
• Elliot Gorokhovsky: @ChaoXu its equivalent, just take $n$ larger than the largest word in the language. In my problem $n$ is known as the number of variables of $\varphi$.
• Mikhail Rudoy: It's also interesting to look at the problem "Given an NFA, count the number of matching words of length $k$" when k is given in binary. This problem is PSPACE-hard. I say this based on the proof that deciding equivalence of two regular expressions is PSPACE-hard. In that reduction, one reg-ex was constructed to accept all strings, and the other to accept all strings that are not valid rejecting computation histories of PSPACE machine M on input w. Using that second regular expression and taking $k$ to be the length of a computation history of M on w makes this other problem PSPACE-hard too.

Answer 1

See this paper: Counting the size of regular sequences of given length is #P-complete: S. Kannan, Z. Sweedyk, and S. R. Mahaney. Counting and random generation of strings in regular languages. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 551–557, 1995.