Can we efficiently enumerate the words accepted by a DFA by order of increasing weight?

Question

Fix a deterministic finite automaton $A$ defining a regular language on the alphabet $\Sigma = \{0, 1\}$, and call the (Hamming) weight of a word $w \in \Sigma^*$ its number of $1$'s. Given a length $n \in \mathbb{N}$ (written in unary) as input, I want to enumerate all words of the language of $A$ of length $n$, by increasing weight (i.e., first all words of the smallest possible weight, enumerated in some arbitrary order; then all words of the second smallest possible weight, in some arbitrary order; etc., until all words of length $n$ in the language of $A$ have been produced). I'm interested in this in the context of enumeration algorithms, so let's say I want polynomial delay, i.e., the time to produce the next word is always bounded by some polynomial function of $n$. Of course, finding some word achieving the smallest possible weight is easy (make $n$ copies of the automaton and do a shortest path algorithm); the difficulty is in finding the next words, keeping in mind that you are not allowed to enumerate the same word multiple times. And of course, enumerating all words with polynomial delay is not complicated if you do not care about ordering them by weight: make $n$ copies, prune the useless states, and simply enumerate all paths exhaustively with a DFS.

Is anything known about the complexity of this problem? Can the enumeration be performed in PTIME (maybe only for some DFAs?), or can it be shown to be intractable?

I'm also interested in:

• A weighted variant, where instead of $n \in \mathbb{N}$ written in unary, I get as input an $n$-tuple of integers $w_1, \ldots, w_n$, and the weight of a word $u_1, \ldots, u_n$ is then $\sum_i u_i w_i$, i.e., I want to enumerate all words by increasing weight of their dot product with the input vector $w$. (The unweighted version above is the case where all values of the $n$-tuple are 1.) In this problem variant, if the numbers in the vector components are written in binary, it becomes NP-hard to decide if a certain weight can be achieved (this is the subset sum problem, already for the trivial automaton $A$ accepting $\Sigma^*$). But this does not imply that enumerating is hard.
• A combined complexity variant where the automaton is also given as input and not fixed. In this case, you might as well do directly the product of the automaton with $n$, so you can simply assume that the input is an acyclic DFA, or equivalently an OBDD. But I'm not aware either of algorithms to enumerate OBDD valuations in order of increasing weight.

Answer 1

EDIT: Added Lemma 2 which covers all cases asked about.

Lemma 1. Given a DFA with alphabet $\{0,1\}$ and an integer $n$, it is possible to enumerate all length-$n$ words in the language of the DFA, in order of non-decreasing number of 1's, with the time taken between each word and the next polynomial in $n$ and the size of the DFA.

Proof. Here's the algorithm. Fix an input DFA $M$ and integer $n$.

For each $k\in\{0,1,\ldots, n\}$ in increasing order, do the following:

1. Construct a new DFA $M_k$ with a state $(s, i, j)$ for each state $s$ in $M$ and $i, j \ge 0$ with $i+j\le n$. The new DFA $M_k$ simulates $M$, but uses the indices $i$ and $j$ to count, respectively, the number of 0's and 1's seen so far. Make $(s, 0, 0)$ the start state, where $s$ is the start state of $M$. Make each state $(s, i, j)$ an accepting state of $M_k$ if $s$ is an accepting state of $M$ and $i+j=n$ and $j=k$. So $$L(M_k) = \{w \in L(M) : w \text{ has length $n$ and $k$ ones}\}.$$ Note that $M_k$ is a directed acyclic graph whose size is polynomial in $n$ and the size of $M$.

2. Enumerate the words accepted by $M_k$ as follows. First delete all dead states (states not reachable from the start state, or from which no accept state can be reached). Find the lexicographically first path in the language of $M_k$ by starting at the start state, then traversing from each node to the next, taking a 0-edge if possible and otherwise a 1-edge. Stop upon reaching a start state, and output the path found. Next, repeat the following: let $p$ be the path just enumerated. Find the path $p'$ following $p$ in lexicographic order as follows. Take the last 0-edge $(u, w)$ on $p$ such that there is a 1-edge out of $u$, and replace that 0-edge edge and the remaining suffix of $p$ by the 1-edge (say, $(u, w')$) out of $u$ and the lexicographically first path from $w'$ to an accept state (computed as described above, taking 0-edges when possible). If there is no such edge $(u, w)$, stop.

Note that there are no dead states, so the algorithm can always find $p'$ as described above.

By inspection the time for Step 1 is polynomial in $n$ and the size of $M$, and each path enumerated in Step 2 is enumerated in time polynomial in $n$ and the size of $M$. The words in $L(M)$ of length $n$ are enumerated in order of increasing number of 1's (i.e., increasing value of $k$.) $~~\Box$

Lemma 2. Given an instance of the "weighted" variant in the post, it is possible to enumerate all length-$n$ words in the language of the DFA, in order of non-decreasing weight, with the time taken between each word and the next polynomial in $n$ and the size of the DFA.

Proof. By a construction similar to Step 1 of the algorithm in the proof of Lemma 1, the problem reduces to the following problem. Given an edge-weighted DAG $G=(V,E)$ and two nodes $s$ and $t$, enumerate all paths from $s$ to $t$, in order of increasing path weight, taking time polynomial in the size of the DAG between enumerated paths.

Here is an algorithm for that problem. (Note: the data maintained by the algorithm will be become exponentially large, but this will be okay each additional path will still be enumerated in polynomial time.)

Observation 1. Let $P_v$ denote the paths from $s$ to $v$. For $v\ne s$, $$P_v = \bigcup_{u:(u,v)\in E}\{ p \circ (u, v) : p \in P_u \},$$ where $\circ$ denotes concatenation. Consider $P_v$ ordered by increasing path weight. In this order, consider only the paths that end in a given edge $(u, v)\in E$. Let these paths be $$p_1 \circ (u, v),~p_2 \circ (u, v), ~\ldots, ~p_\ell \circ (u, v).$$ Then $p_1, p_2, \ldots, p_\ell$ are the paths in $P_u$, ordered by increasing path weight.

For each vertex $v$ and index $i$, let $P_v(i)$ denote the $i$th in $P_v$, ordered by path weight. We will build an enumerator of $P_v$ that enumerates the $s$-$v$ paths in order $P_v(1), P_v(2), \ldots$, that is, by increasing path weight. At any given time, each enumerator $P_v$ will have so far enumerated $P_v(1), P_v(2), \ldots, P_v(i_v)$ for some $i_v$. It will support two operations:

1. Increment. Enumerate the next path $P_v(i_v+1)$ in the sequence and increase $i_v$ by one.

2. Query. Given an index $i\le i_v$, return the cost of the $i$th path in the sequence, i.e., the cost of $P_v(i)$.

The overall algorithm will simply repeatedly increment the enumerator for $P_t$ to enumerate all its paths in order. It remains to describe how to implement the enumerator $P_v$ for any given $v\ne s$ to support the two operations above.

$P_v$ will record (in an array), for each path $P_v(i)$ that it has already enumerated (i.e., $i\le i_v$), the cost of that path. This will let it perform the query operation in constant time.

To support the increment operation, following Observation 1, $P_v$ will maintain, for each edge $(u, v)$ into $v$, the index $j_{uv}$ such that the most recent path that ends in edge $(u, v)$ that it has enumerated is $P_u(j_{uv})\circ (u, v)$. (Hence, $\sum_u j_{uv}$ equals $i_v$, the number of paths that $P_v$ has enumerated so far.)

By Observation 1, the next path $P_v(i_v+1)$ in the sequence is the cheapest of the following paths: $$P_u(j_{uv}+1) \circ (u, v) \text{ such that } (u,v) \in E.$$ The enumerator will find this path by calling each enumerator $P_u$ for $(u, v)\in E$, to find the cost of $P_u(j_{uv}+1)$. Having found the best path, say $P_{u'}\circ (u', v)$, it will increment $j_{u'v}$, and in the case that $j_{u'v} = i_{u'}$ (the best path uses the most recent path enumerated by $P_{u'}$), it will increment $P_{u'}$ (have it enumerate its next path), ensuring that $i_{u'}$ is at least $j_{u'v}+1$. This way, each cost query to $P_v$ can be done in constant time.

Note that any given call to $P_t$ results in each enumerator $P_u$ being incremented at most once total, even though increments can propagate and several enumerators $P_v$ could in principle ask $P_u$ to increment. This is because, during any given call to $P_t$, for a given enumerator $P_u$, we can assume by induction (on distance to $t$) that each of its "parents" $P_v$ (with $(u,v)\in E$) is incremented at most once during the call to $P_t$. So, once $P_u$ is incremented once during the call, its $i_u$ has increased by one, which is the most that any parent could need.

(Alternatively, we could proceed in rounds $r=1,2,\ldots$, and in round $r$ have every enumerator $P_u$ increment by one, producing $P_u(r)$. Because $P_v(i) = P_u(i') \circ (u, v)$ where $(u,v)\in E$ and $i' \le i$, this would suffice. It would still be polynomial time, but not as efficient.) $~~\Box$

EDIT 2: Code for the algorithm (on DAGs) in the proof is here.

Answer 2

After discussing it further with a3nm, I propose an algorithm that is different than Neal's algorithm and works in a more general setting. The approach gives polynomial delay algorithm but it uses exponential space.

The only two properties that we will be using are :

(1) The problem is self-reducible, in the sense that if I am given an automaton $A$ and $u \in \{0,1\}^*$, I can construct an automaton $A'$ in polynomial time which recognizes exactly the words $u^{-1}L(A) := \{w\mid uw \in L(A)\}$.

(2) Computing the minimum weight element is tractable: given an automaton $A$ and a weighting function $W : L_n(A) \rightarrow \mathbb{Z}$ on $L_n(A) = \{w \in L(A) \mid |w|=n\}$, one can compute $\min_{w \in L_n(A)} W(w)$ in polynomial time.

Rough idea

The algorithm is a "classical" flashlight approach that is guided by the weighting function. Here is the rough idea:

Compute the smallest weight $W_0$ of words in $0^{-1}L_n(A)$ and $W_1$ of words in $1^{-1}L_n(A)$ (if one of these two languages is empty, set $W_i = \infty$). If $W_0 \leq W_1$, proceed now to find the smallest weight of $W_{00} = (00)^{-1}L_n(A)$ and $W_{01} = (01)^{-1}L_n(A)$. If $W_1<W_0$, compute $W_{10} = (10)^{-1}L_n(A)$ and $W_{11} = (1)^{-1}L_n(A)$.

Keep on setting a prefix of the word, always choosing the one leading to the smallest possible weight, until you have fixed $n$ letters and hence reached a word $w \in L_n(A)$ with minimal weight $M$.

Now, each time you have fixed a letter, you have chosen it over another one because $M$ was smaller than the minimum weight you could have had if you had chosen differently. This gives you a set of possible weights $S$. Let $M'$ be the value in $S$ that is the closest to $M$ ($M' \geq M$ ; it could be equal). Backtrack to a choice leading to a word of weight $M'$. Repeat until you have found all words in $L_n(A)$.

Of course, you have to maintain some kind of binary tree structure with all choices that you made, and with a queue to quickly jump to the right node of the tree. I will try to make it more formal in the next section. But observe that if you can do this, you have a delay of $O(n \times Q)$ between two solutions where $Q$ is the time needed to find the smallest weight of words with a given prefix.

A more formal take

Our goal is to enumerate $L_n(A)$ by increasing order of weights.

We say that a prefix $w$ is extendable if there exists $u$ such that $w.u \in L_n(A)$. Given an extendable prefix $w$, we denote by $W(w) := \min_{wu \in L_n(A)} W(wu)$.

We enumerate $L_n(A)$ by exploring extendable prefixes.

First, we need a priority queue $Q$ that is initialized empty.

We use the following way to explore extendable prefixes. We start with the empty prefix. Now let $w$ be an extendable prefix. We explore the prefixes as follows:

Strict prefix: if $w$ has length $<n$, then we use property (1) above to decide whether $w0$ and $w1$ are extendable (by definition of extendable, at least one of them is extendable).

If exactly one of them $w'$ is extendable, explore $w'$.

Otherwise, compute $W(w0)$ and $W(w1)$ using (2) and (1) combined. If $W(w0) \leq W(w1)$, add $w1$ with priority $W(w1)$ in the priority queue $Q$ and explore $w0$. Otherwise add $w0$ to the queue and explore $w1$.

Full prefix: if $w$ has length $n$, then it is in $L_n(A)$.

Output $w$.

If $Q$ is empty, finish. Otherwise, extract the minimum extendable prefix $w'$ from $Q$ and explore $w'$.

Lemma 1: This algorithm has polynomial delay.

Proof: It is easy to see as exploring an given prefix is PTIME from (1) and (2). Then it proceeds to explore a longer prefix. So after at most $n$ explorations, it outputs a solution.

Lemma 2: The algorithm outputs every word in $L_n(A)$.

Proof: We can show that if a prefix $w$ is explored then all extensions of $w$ are outputted. This is easily seen by induction on $n-|w|$.

Lemma 3: The algorithm outputs word in increasing order.

Proof: It is clear that the first word outputted by the algorithm has the smallest possible weight. Now we have to show that after outputting a word $w$, its weight is smaller than the minimum of $Q$. This part could be made more formal but here is why it works: one can easily see that the weight of $w$ is the weight of the extendable prefix $w'$ that was extracted before from $Q$. So all elements that were in $Q$ at this point have a bigger weight than $w$. Every element that have been added to $Q$ during the exploration of $w'$ have a weight bigger than $W(w') = W(w)$, which is what we wanted.

Possible extensions

I have "defined" both properties on automata (observe that I do not need determinism for both properties to hold) but this can easily be lifted to other kind of data structures, especially data structures representing Boolean functions on variables $X := x_1,\dots,x_n$ such as OBDDs, FBDDs, or even more generally DNNFs (in this case, I interpret assignment $\tau \in \{0,1\}^X$ as a word $\tau(x_1) \dots \tau(x_n)$. Observe that the order we choose on $X$ is not really important here either for the result to hold. The result may also work with weighting functions that are more general than the ones considered by a3nm in the original question (as long as you have tractability of property (2)).