<p>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.</p>
<p>The only two properties that we will be using are :</p>
<p>(1) The problem is self-reducible, in the sense that if I am given an
automaton <span class="math-container">$A$</span> and <span class="math-container">$u \in \{0,1\}^*$</span>, I can construct an automaton <span class="math-container">$A'$</span>
in polynomial time which recognizes exactly the words <span class="math-container">$u^{-1}L(A) :=
\{w\mid uw \in L(A)\}$</span>.</p>
<p>(2) Computing the minimum weight element is tractable: given an automaton
<span class="math-container">$A$</span> and a weighting function <span class="math-container">$W : L_n(A) \rightarrow \mathbb{Z}$</span> on
<span class="math-container">$L_n(A) = \{w \in L(A) \mid |w|=n\}$</span>, one can compute <span class="math-container">$\min_{w \in
L_n(A)} W(w)$</span> in polynomial time.</p>
<h1>Rough idea</h1>
<p>The algorithm is a &quot;classical&quot; flashlight approach that is guided by
the weighting function. Here is the rough idea:</p>
<p>Compute the smallest weight <span class="math-container">$W_0$</span> of words in <span class="math-container">$0^{-1}L_n(A)$</span> and <span class="math-container">$W_1$</span>
of words in <span class="math-container">$1^{-1}L_n(A)$</span> (if one of these two languages is empty,
set <span class="math-container">$W_i = \infty$</span>). If <span class="math-container">$W_0 \leq W_1$</span>, proceed now to find the
smallest weight of <span class="math-container">$W_{00} = (00)^{-1}L_n(A)$</span> and <span class="math-container">$W_{01} =
(01)^{-1}L_n(A)$</span>. If <span class="math-container">$W_1&lt;W_0$</span>, compute <span class="math-container">$W_{10} = (10)^{-1}L_n(A)$</span> and <span class="math-container">$W_{11}
= (1)^{-1}L_n(A)$</span>.</p>
<p>Keep on setting a prefix of the word, always choosing the one leading
to the smallest possible weight, until you have fixed <span class="math-container">$n$</span> letters and
hence reached a word <span class="math-container">$w \in L_n(A)$</span> with minimal weight <span class="math-container">$M$</span>.</p>
<p>Now, each time you have fixed a letter, you have chosen it over another
one because <span class="math-container">$M$</span> was smaller than the minimum weight you could have had
if you had chosen differently. This gives you a set of possible
weights <span class="math-container">$S$</span>. Let <span class="math-container">$M'$</span> be the value in <span class="math-container">$S$</span> that is the closest to <span class="math-container">$M$</span>
(<span class="math-container">$M' \geq M$</span> ; it could be equal). Backtrack to a choice leading to a
word of weight <span class="math-container">$M'$</span>. Repeat until you have found all words in
<span class="math-container">$L_n(A)$</span>.</p>
<p>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 <span class="math-container">$O(n
\times Q)$</span> between two solutions where <span class="math-container">$Q$</span> is the time needed to find the
smallest weight of words with a given prefix.</p>
<h1>A more formal take</h1>
<p>Our goal is to enumerate <span class="math-container">$L_n(A)$</span> by increasing order of weights.</p>
<p>We say that a prefix <span class="math-container">$w$</span> is <em>extendable</em> if there exists <span class="math-container">$u$</span> such that
<span class="math-container">$w.u \in L_n(A)$</span>. Given an extendable prefix <span class="math-container">$w$</span>, we denote by <span class="math-container">$W(w)
:= \min_{wu \in L_n(A)} W(wu)$</span>.</p>
<p>We enumerate <span class="math-container">$L_n(A)$</span> by exploring extendable prefixes.</p>
<p>First, we need a  priority queue <span class="math-container">$Q$</span> that is initialized empty.</p>
<p>We use the following way to explore extendable prefixes. We start with
the empty prefix. Now let <span class="math-container">$w$</span> be an extendable prefix. We explore the
prefixes as follows:</p>
<p><strong>Strict prefix</strong>: if <span class="math-container">$w$</span> has length <span class="math-container">$&lt;n$</span>, then we use property (1) above to decide
whether <span class="math-container">$w0$</span> and <span class="math-container">$w1$</span> are extendable (by definition of extendable,
at least one of them is extendable).</p>
<p>If exactly one of them <span class="math-container">$w'$</span> is extendable, explore <span class="math-container">$w'$</span>.</p>
<p>Otherwise, compute <span class="math-container">$W(w0)$</span> and <span class="math-container">$W(w1)$</span> using (2) and (1)
combined. If <span class="math-container">$W(w0) \leq W(w1)$</span>, add <span class="math-container">$w1$</span> with priority <span class="math-container">$W(w1)$</span> in
the priority queue <span class="math-container">$Q$</span> and explore <span class="math-container">$w0$</span>. Otherwise add <span class="math-container">$w0$</span> to the
queue and explore <span class="math-container">$w1$</span>.</p>
<p><strong>Full prefix</strong>: if <span class="math-container">$w$</span> has length <span class="math-container">$n$</span>, then it is in <span class="math-container">$L_n(A)$</span>.</p>
<p>Output <span class="math-container">$w$</span>.</p>
<p>If <span class="math-container">$Q$</span> is empty, finish. Otherwise, extract the minimum extendable
prefix <span class="math-container">$w'$</span> from <span class="math-container">$Q$</span> and explore <span class="math-container">$w'$</span>.</p>
<p><strong>Lemma 1</strong>: This algorithm has polynomial delay.</p>
<p><em>Proof</em>: 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 <span class="math-container">$n$</span> explorations, it outputs a solution.</p>
<p><strong>Lemma 2</strong>: The algorithm outputs every word in <span class="math-container">$L_n(A)$</span>.</p>
<p><em>Proof</em>: We can show that if a prefix <span class="math-container">$w$</span> is explored then all
extensions of <span class="math-container">$w$</span> are outputted. This is easily seen by induction on
<span class="math-container">$n-|w|$</span>.</p>
<p><strong>Lemma 3</strong>: The algorithm outputs word in increasing order.</p>
<p><em>Proof</em>: 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 <span class="math-container">$w$</span>, its weight is smaller than the minimum of
<span class="math-container">$Q$</span>. This part could be made more formal but here is why it works: one
can easily see that the weight of <span class="math-container">$w$</span> is the weight of the extendable
prefix <span class="math-container">$w'$</span> that was extracted before from <span class="math-container">$Q$</span>. So all elements that
were in <span class="math-container">$Q$</span> at this point have a bigger weight than <span class="math-container">$w$</span>. Every element
that have been added to <span class="math-container">$Q$</span> during the exploration of <span class="math-container">$w'$</span> have a
weight bigger than <span class="math-container">$W(w') = W(w)$</span>, which is what we wanted.</p>
<h1>Possible extensions</h1>
<p>I have &quot;defined&quot; 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 <span class="math-container">$X := x_1,\dots,x_n$</span> such
as OBDDs, FBDDs, or even more generally DNNFs (in this case, I interpret
assignment <span class="math-container">$\tau \in \{0,1\}^X$</span> as a word <span class="math-container">$\tau(x_1) \dots
\tau(x_n)$</span>. Observe that the order we choose on <span class="math-container">$X$</span> 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)).</p>

CC BY-SA 4.0
2021-04-22T21:25:45.230Z
2021-04-23T08:13:54.730Z
2021-04-23T08:13:54.730Z
holf
<p><em>EDIT: Added Lemma 2 which covers all cases asked about.</em></p>
<p><strong>Lemma 1.</strong>  <em>Given a DFA with alphabet <span class="math-container">$\{0,1\}$</span> and an integer <span class="math-container">$n$</span>, it is possible to enumerate all length-<span class="math-container">$n$</span> 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 <span class="math-container">$n$</span> and the size of the DFA.</em></p>
<p><em>Proof.</em>  Here's the algorithm.  Fix an input DFA <span class="math-container">$M$</span> and integer <span class="math-container">$n$</span>.</p>
<p>For each <span class="math-container">$k\in\{0,1,\ldots, n\}$</span> in increasing order, do the following:</p>
<ol>
<li><p>Construct a new DFA <span class="math-container">$M_k$</span> with a state <span class="math-container">$(s, i, j)$</span> for each state <span class="math-container">$s$</span> in <span class="math-container">$M$</span> and <span class="math-container">$i, j \ge 0$</span> with <span class="math-container">$i+j\le n$</span>.  The new DFA <span class="math-container">$M_k$</span> simulates <span class="math-container">$M$</span>, but uses the indices <span class="math-container">$i$</span> and <span class="math-container">$j$</span> to count, respectively, the number of 0's and 1's seen so far.  Make <span class="math-container">$(s, 0, 0)$</span> the start state, where <span class="math-container">$s$</span> is the start state of <span class="math-container">$M$</span>. Make each state <span class="math-container">$(s, i, j)$</span> an accepting state of <span class="math-container">$M_k$</span> if <span class="math-container">$s$</span> is an accepting state of <span class="math-container">$M$</span> and <span class="math-container">$i+j=n$</span> and <span class="math-container">$j=k$</span>. So <span class="math-container">$$L(M_k) = \{w \in L(M) : w \text{ has length $n$ and $k$ ones}\}.$$</span>  Note that <span class="math-container">$M_k$</span> is a directed acyclic graph whose size is polynomial in <span class="math-container">$n$</span> and the size of <span class="math-container">$M$</span>.</p>
</li>
<li><p>Enumerate the words accepted by <span class="math-container">$M_k$</span> 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 <span class="math-container">$M_k$</span> 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 <span class="math-container">$p$</span> be the path just enumerated.  Find the path <span class="math-container">$p'$</span> following <span class="math-container">$p$</span> in lexicographic order as follows.  Take the last 0-edge <span class="math-container">$(u, w)$</span> on <span class="math-container">$p$</span> such that there is a 1-edge out of <span class="math-container">$u$</span>, and replace that 0-edge edge and the remaining suffix of <span class="math-container">$p$</span> by the 1-edge (say, <span class="math-container">$(u, w')$</span>) out of <span class="math-container">$u$</span> and the lexicographically first path from <span class="math-container">$w'$</span> to an accept state (computed as described above, taking 0-edges when possible).  If there is no such edge <span class="math-container">$(u, w)$</span>, stop.</p>
</li>
</ol>
<p>Note that there are no dead states, so the algorithm can always find <span class="math-container">$p'$</span> as described above.</p>
<p>By inspection the time for Step 1 is polynomial in <span class="math-container">$n$</span> and the size of <span class="math-container">$M$</span>, and each path enumerated in Step 2 is enumerated in time polynomial in <span class="math-container">$n$</span> and the size of <span class="math-container">$M$</span>.  The words in <span class="math-container">$L(M)$</span> of length <span class="math-container">$n$</span> are enumerated in order of increasing number of 1's (i.e., increasing value of <span class="math-container">$k$</span>.)  <span class="math-container">$~~\Box$</span></p>
<p><strong>Lemma 2.</strong>  <em>Given an instance of the &quot;weighted&quot; variant in the post, it is possible to enumerate all length-<span class="math-container">$n$</span> 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 <span class="math-container">$n$</span> and the size of the DFA.</em></p>
<p><em>Proof.</em> By a construction similar to Step 1 of the algorithm in the proof of Lemma 1, the problem reduces to the following problem.  <em>Given an edge-weighted DAG <span class="math-container">$G=(V,E)$</span> and two nodes <span class="math-container">$s$</span> and <span class="math-container">$t$</span>, enumerate all paths from <span class="math-container">$s$</span> to <span class="math-container">$t$</span>, in order of increasing path weight, taking time polynomial in the size of the DAG between enumerated paths.</em></p>
<p>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.)</p>
<p><em>Observation 1.</em>
Let <span class="math-container">$P_v$</span> denote the paths from <span class="math-container">$s$</span> to <span class="math-container">$v$</span>.  For <span class="math-container">$v\ne s$</span>,
<span class="math-container">$$P_v = \bigcup_{u:(u,v)\in E}\{ p \circ (u, v) : p \in P_u \},$$</span>
where <span class="math-container">$\circ$</span> denotes concatenation.  Consider <span class="math-container">$P_v$</span> ordered by increasing path weight.  In this order, consider only the paths that end in a given edge <span class="math-container">$(u, v)\in E$</span>.  Let these paths be
<span class="math-container">$$p_1 \circ (u, v),~p_2 \circ (u, v), ~\ldots, ~p_\ell \circ (u, v).$$</span>
<em>Then <span class="math-container">$p_1, p_2, \ldots, p_\ell$</span> are the paths in <span class="math-container">$P_u$</span>, ordered by increasing path weight.</em></p>
<p>For each vertex <span class="math-container">$v$</span> and index <span class="math-container">$i$</span>, let <span class="math-container">$P_v(i)$</span> denote the <span class="math-container">$i$</span>th in <span class="math-container">$P_v$</span>, ordered by path weight. We will build an <em>enumerator</em> of <span class="math-container">$P_v$</span> that enumerates the <span class="math-container">$s$</span>-<span class="math-container">$v$</span> paths in order <span class="math-container">$P_v(1), P_v(2), \ldots$</span>, that is, by increasing path weight.  At any given time, each enumerator <span class="math-container">$P_v$</span> will have so far enumerated <span class="math-container">$P_v(1), P_v(2), \ldots, P_v(i_v)$</span> for some <span class="math-container">$i_v$</span>. It will support two operations:</p>
<ol>
<li><p><strong>Increment.</strong> Enumerate the next path <span class="math-container">$P_v(i_v+1)$</span> in the sequence and increase <span class="math-container">$i_v$</span> by one.</p>
</li>
<li><p><strong>Query.</strong> Given an index <span class="math-container">$i\le i_v$</span>, return the cost of the <span class="math-container">$i$</span>th path in the sequence, i.e., the cost of <span class="math-container">$P_v(i)$</span>.</p>
</li>
</ol>
<p>The overall algorithm will simply repeatedly increment the enumerator for <span class="math-container">$P_t$</span> to enumerate all its paths in order.  It remains to describe how to implement the enumerator <span class="math-container">$P_v$</span> for any given <span class="math-container">$v\ne s$</span> to support the two operations above.</p>
<p><span class="math-container">$P_v$</span> will record (in an array), for each path <span class="math-container">$P_v(i)$</span> that it has already enumerated (i.e., <span class="math-container">$i\le i_v$</span>), the cost of that path.  This will let it perform the query operation in constant time.</p>
<p>To support the increment operation, following Observation 1, <span class="math-container">$P_v$</span> will maintain, for each edge <span class="math-container">$(u, v)$</span> into <span class="math-container">$v$</span>, the index <span class="math-container">$j_{uv}$</span> such that the most recent path that ends in edge <span class="math-container">$(u, v)$</span> that it has enumerated is <span class="math-container">$P_u(j_{uv})\circ (u, v)$</span>.  (Hence, <span class="math-container">$\sum_u j_{uv}$</span> equals <span class="math-container">$i_v$</span>, the number of paths that <span class="math-container">$P_v$</span> has enumerated so far.)</p>
<p>By Observation 1, the next path <span class="math-container">$P_v(i_v+1)$</span> in the sequence is the cheapest of the following paths:
<span class="math-container">$$P_u(j_{uv}+1) \circ (u, v) \text{ such that } (u,v) \in E.$$</span>
The enumerator will find this path by calling each enumerator <span class="math-container">$P_u$</span> for <span class="math-container">$(u, v)\in E$</span>, to find the cost of <span class="math-container">$P_u(j_{uv}+1)$</span>.  Having found the best path, say <span class="math-container">$P_{u'}\circ (u', v)$</span>, it will increment <span class="math-container">$j_{u'v}$</span>, and in the case that <span class="math-container">$j_{u'v} = i_{u'}$</span> (the best path uses the most recent path enumerated by <span class="math-container">$P_{u'}$</span>), it will increment <span class="math-container">$P_{u'}$</span> (have it enumerate its next path), ensuring that <span class="math-container">$i_{u'}$</span> is at least <span class="math-container">$j_{u'v}+1$</span>.  This way, each cost query to <span class="math-container">$P_v$</span> can be done in constant time.</p>
<p>Note that any given call to <span class="math-container">$P_t$</span> results in each enumerator <span class="math-container">$P_u$</span> being incremented at most once total, even though increments can propagate and  several enumerators <span class="math-container">$P_v$</span> could in principle ask <span class="math-container">$P_u$</span> to increment.  This is because, during any given call to <span class="math-container">$P_t$</span>, for a given enumerator <span class="math-container">$P_u$</span>, we can assume by induction (on distance to <span class="math-container">$t$</span>) that each of its &quot;parents&quot; <span class="math-container">$P_v$</span> (with <span class="math-container">$(u,v)\in E$</span>) is incremented at most once during the call to <span class="math-container">$P_t$</span>.  So, once <span class="math-container">$P_u$</span> is incremented once during the call, its <span class="math-container">$i_u$</span> has increased by one, which is the most that any parent could need.</p>
<p>(Alternatively, we could proceed in rounds <span class="math-container">$r=1,2,\ldots$</span>, and in round <span class="math-container">$r$</span> have <em>every</em> enumerator <span class="math-container">$P_u$</span> increment by one, producing <span class="math-container">$P_u(r)$</span>.  Because <span class="math-container">$P_v(i) = P_u(i') \circ (u, v)$</span> where <span class="math-container">$(u,v)\in E$</span> and <span class="math-container">$i' \le i$</span>, this would suffice.  It would still be polynomial time, but not as efficient.)  <span class="math-container">$~~\Box$</span></p>
<p><em>EDIT 2: Code for the algorithm (on DAGs) in the proof is <a href="https://replit.com/@nealyoung/MarriedImmaculateDeprecatedsoftware" rel="nofollow noreferrer">here</a>.</em></p>

CC BY-SA 4.0
2020-06-11T14:21:09.257Z
Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/109197/discussion-between-neal-young-and-a3nm).
Neal Young
CC BY-SA 4.0
2020-06-11T15:00:35.330Z
I am a bit confused about step 1 of lemma 1. Did we not need it to be polinomial in the input? (at least it seems so according to https://en.wikipedia.org/wiki/Polynomial_delay) I think it creates a structure that is linear-size with n (and the input has size log(n) in bits)
josinalvo
CC BY-SA 4.0
2020-06-11T15:09:23.920Z
@josinalvo, the post stipulated that $n$ is given in unary, so has encoding size $n$.  This seems  reasonable given that each item enumerated has size $n$, so it would not be possible to even output one item in time polylog$(n)$.
Neal Young
CC BY-SA 4.0
2020-06-16T01:40:54.590Z
of course! thank you!
josinalvo
CC BY-SA 4.0
2021-04-21T18:14:46.850Z
From a discussion with @holf, let me point out here an important point, that we had realized in chat (https://chat.stackexchange.com/rooms/109197/discussion-between-neal-young-and-a3nm): *almost everything asked in the original question is trivial*. You can just make copies of the automata instantiated to only produce words of length $n$ and of each possible weight. The only challenging case, where the number of possible weights is not polynomial, is the weighted variant (first bullet point) and with weights given in binary. In this case only, you need the algorithm in Neal's answer above.
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2021-04-22T11:42:47.833Z
In the weighted variant case, don't we need to do some initialization first ? Otherwise, the first time we want to increment $P_t$, it seems to me that we cannot call $P_u(j_{uv}+1)$ in constant time.
M.Monet
CC BY-SA 4.0
2021-04-22T11:45:54.950Z
Also, from what I understand, Neal's algorithm would also work for unambiguous finite automata, no? (Simply because we are outputting the paths, and each accepted word has at most one path). I am wondering if a similar approach could be used for https://cstheory.stackexchange.com/q/48815/38111
M.Monet
CC BY-SA 4.0
2021-04-22T19:45:44.357Z
@M.Monet, yes, we need to initialize $P_v(1)$ when we first create $P_v$.  Assuming all "incoming" enumerators are already initialized, I think this can be done in poly time (just use the method for increment, noting $j_{uv}=0$ for all $u$.)  And yes, I don't see any problem with using this to enumerate all words in the language of an unambiguous NFA, in order of increasing weight, with poly-delay between the words.
Neal Young
CC BY-SA 4.0
2020-06-10T22:31:28.457Z
2021-04-22T19:52:39.533Z
2021-04-22T19:52:39.533Z
Neal Young
<p>Fix a deterministic finite automaton <span class="math-container">$A$</span> defining a regular language on the alphabet <span class="math-container">$\Sigma = \{0, 1\}$</span>, and call the (Hamming) <em>weight</em> of a word <span class="math-container">$w \in \Sigma^*$</span> its number of <span class="math-container">$1$</span>'s. Given a length <span class="math-container">$n \in \mathbb{N}$</span> (written in unary) as input, I want to enumerate all words of the language of <span class="math-container">$A$</span> of length <span class="math-container">$n$</span>, 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 <span class="math-container">$n$</span> in the language of <span class="math-container">$A$</span> have been produced). I'm interested in this in the context of <a href="https://en.wikipedia.org/wiki/Enumeration_algorithm" rel="noreferrer">enumeration algorithms</a>, 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 <span class="math-container">$n$</span>. Of course, finding some word achieving the smallest possible weight is easy (make <span class="math-container">$n$</span> 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 <span class="math-container">$n$</span> copies, prune the useless states, and simply enumerate all paths exhaustively with a DFS.</p>

<p><strong>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?</strong></p>

<p>I'm also interested in:</p>

<ul>
<li>A <em>weighted</em> variant, where instead of <span class="math-container">$n \in \mathbb{N}$</span> written in unary, I get as input an <span class="math-container">$n$</span>-tuple of integers <span class="math-container">$w_1, \ldots, w_n$</span>, and the <em>weight</em> of a word <span class="math-container">$u_1, \ldots, u_n$</span> is then <span class="math-container">$\sum_i u_i w_i$</span>, i.e., I want to enumerate all words by increasing weight of their dot product with the input vector <span class="math-container">$w$</span>. (The unweighted version above is the case where all values of the <span class="math-container">$n$</span>-tuple are 1.) In this problem variant, if the numbers in the vector components are written in binary, it becomes NP-hard to <em>decide</em> if a certain weight can be achieved (this is the <a href="https://en.wikipedia.org/wiki/Subset_sum_problem" rel="noreferrer">subset sum problem</a>, already for the trivial automaton <span class="math-container">$A$</span> accepting <span class="math-container">$\Sigma^*$</span>). But this does not imply that enumerating is hard.</li>
<li>A <em>combined complexity</em> 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 <span class="math-container">$n$</span>, so you can simply assume that the input is an acyclic DFA, or equivalently an <a href="https://en.wikipedia.org/wiki/Binary_decision_diagram" rel="noreferrer">OBDD</a>. But I'm not aware either of algorithms to enumerate OBDD valuations in order of increasing weight.</li>
</ul>

CC BY-SA 4.0
2020-06-10T22:05:21.133Z
In the paragraph on the weighted variant, you wrote *"if the numbers .. are written in unary, it becomes NP-hard... (this is the subset-sum problem)..*"  Did you mean "written in *binary*"?  Unary subset sum is not NP-hard, is it?
Neal Young
CC BY-SA 4.0
2020-06-11T06:30:18.790Z
@NealYoung: yes, sorry for the mistake and thanks for pointing it out, I have edited it.
Antoine Amarilli 'a3nm'
<cc.complexity-theory><reference-request><automata-theory><dfa><enumeration>
Can we efficiently enumerate the words accepted by a DFA by order of increasing weight?
Antoine Amarilli 'a3nm'
# Can we efficiently enumerate the words accepted by a DFA by order of increasing weight?

(Asked by: username_0 on 2020-06-10)

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](https://en.wikipedia.org/wiki/Enumeration_algorithm), 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](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Binary_decision_diagram). But I'm not aware either of algorithms to enumerate OBDD valuations in order of increasing weight.

**Tags:** cc.complexity-theory, reference-request, automata-theory, dfa, enumeration

> **Comments:**
> **username_1**: In the paragraph on the weighted variant, you wrote *"if the numbers .. are written in unary, it becomes NP-hard... (this is the subset-sum problem)..*"  Did you mean "written in *binary*"?  Unary subset sum is not NP-hard, is it?  
> **username_0**: @NealYoung: yes, sorry for the mistake and thanks for pointing it out, I have edited it.  

---

## 2 answers

### Answer by username_1 on 2020-06-10. Score: 10 | Accepted answer

*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](https://replit.com/@nealyoung/MarriedImmaculateDeprecatedsoftware).*

> **Comments:**
> **username_1**: Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/109197/discussion-between-neal-young-and-a3nm).  
> **username_3**: I am a bit confused about step 1 of lemma 1. Did we not need it to be polinomial in the input? (at least it seems so according to https://en.wikipedia.org/wiki/Polynomial_delay) I think it creates a structure that is linear-size with n (and the input has size log(n) in bits)  
> **username_1**: @username_3, the post stipulated that $n$ is given in unary, so has encoding size $n$.  This seems  reasonable given that each item enumerated has size $n$, so it would not be possible to even output one item in time polylog$(n)$.  
> **username_3**: of course! thank you!  
> **username_0**: From a discussion with @username_2, let me point out here an important point, that we had realized in chat (https://chat.stackexchange.com/rooms/109197/discussion-between-neal-young-and-a3nm): *almost everything asked in the original question is trivial*. You can just make copies of the automata instantiated to only produce words of length $n$ and of each possible weight. The only challenging case, where the number of possible weights is not polynomial, is the weighted variant (first bullet point) and with weights given in binary. In this case only, you need the algorithm in Neal's answer above.  
> **username_4**: In the weighted variant case, don't we need to do some initialization first ? Otherwise, the first time we want to increment $P_t$, it seems to me that we cannot call $P_u(j_{uv}+1)$ in constant time.  
> **username_4**: Also, from what I understand, Neal's algorithm would also work for unambiguous finite automata, no? (Simply because we are outputting the paths, and each accepted word has at most one path). I am wondering if a similar approach could be used for https://cstheory.stackexchange.com/q/48815/38111  
> **username_1**: @username_4, yes, we need to initialize $P_v(1)$ when we first create $P_v$.  Assuming all "incoming" enumerators are already initialized, I think this can be done in poly time (just use the method for increment, noting $j_{uv}=0$ for all $u$.)  And yes, I don't see any problem with using this to enumerate all words in the language of an unambiguous NFA, in order of increasing weight, with poly-delay between the words.  

---

### Answer by username_2 on 2021-04-22. Score: 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, 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 $, 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)).


---

