8
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Neal Young Jun 10 at 22:05
  • $\begingroup$ @NealYoung: yes, sorry for the mistake and thanks for pointing it out, I have edited it. $\endgroup$ – a3nm Jun 11 at 6:30
9
$\begingroup$

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 "combined complexity" 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 = \{ 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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Let us continue this discussion in chat. $\endgroup$ – Neal Young Jun 11 at 14:21
  • $\begingroup$ 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 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) $\endgroup$ – josinalvo Jun 11 at 15:00
  • 2
    $\begingroup$ @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)$. $\endgroup$ – Neal Young Jun 11 at 15:09
  • $\begingroup$ of course! thank you! $\endgroup$ – josinalvo Jun 16 at 1:40

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.