2
$\begingroup$

The following may contain errors. It is precisely because I am not sure I understand the topic that I am asking questions. I do not have books about it and could not find an adequate reference on the web.

I am discussing a problem regarding an enumeration of strings that should be in amortized constant delay. From what I understood (but understanding that is part of my question), this means that the average time taken for each answer should be independent of the size of the answer, so that the total cost is $O(n)$ where $n$ is the number of answers.

My discussion partner went on to assert (I believe) that amortized constant delay is possible for enumerating the strings accepted by a trie, but not for enumerating the paths of a DAG. And I am at loss to see a significant difference, since proper use of a stack should let me explore the DAG as if it had been exploded into a trie (by duplicating whatever is below a merge vertex).

The only real difference I can see is that the accepting nodes of a trie can be labeled with a single symbol identifier characterizing the accepted word (turning the trie into a Moore machine) so that the total cost is only a traversal of the trie, with single step output of the symbol label when traversing an accepting node.

Such labeling identification is not possible for a DFA structured as a DAG, since an accepting node can correspond to different paths. The only way to name paths is to describe them in extenso (or nearly so: enough to disambiguate merges), so that the cost of the output by itself is already something like $O(n\times s)$ where $s$ is the size of the longest path, thus entailing the same time cost just for doing the output.

Where do I err, and what is the accepted wisdom and knowledge on this topic? Pointers to web references are useful too.

$\endgroup$
8
  • $\begingroup$ Taking 'answer' to mean the output of a single element of the enumeration, I believe that amortized constant delay does not address the average time taken for one such answer but the average time between 2 consecutive outputs. in a trie that would be constant for one would have to backtrack to the most recent node with some successor edge not yet visited. thus in total there would be one $O(n)$ DFS required for the output of at max $n$ strings in a trie of $n$ nodes. $\endgroup$
    – collapsar
    Apr 2, 2014 at 13:09
  • $\begingroup$ @collapsar Thanks. The point of the discussion I mention is that complexity was not with respect to the size of the trie or whatever other structure is used, but with respect to the number and size of the answers, as well as some other initial parameters. And in such a case, I do not see that there is any difference between the trie and an acyclic DFA that does the same job (other than the naming trick I suggest in the question). My discussion partner is asserting that "It's not known how to enumerate source,sink-paths in a dag with constant delay". Does this refer to something real? $\endgroup$
    – babou
    Apr 2, 2014 at 13:33
  • $\begingroup$ The way I understand the problem, constant amortized delay mandates that all structures needed for bookkeeping of the enumeration elements processed need to be maintained in (average) constant time. for tries that's granted. however, i don't see an obvious solution in the dag case. i have a reference presenting an optimal st-path enumeration algorithm showcasing the issue ... $\endgroup$
    – collapsar
    Apr 2, 2014 at 17:54
  • $\begingroup$ ... Lemma 4.3, p.1891 referring to Algorithm 1, p.1888 shows the total cost of their recursion tree for the maintenance of a bookkeeping data structure is the sum of the lengths of all st-paths. caveat: i'm not well-versed in interpreting research-level papers so i may have missed/misunderstood some aspects. $\endgroup$
    – collapsar
    Apr 2, 2014 at 17:54
  • $\begingroup$ @collapsar Seems paper never considers directed graphs. Assume (no generality loss) the graph has a unique start node (root). You push it on a stack. For each node on the stack, if accepting print the path found in the stack. Then if outgoing edges, choose 1, say e, and memorize the others with the node on stack. Then push e and the node at the other end. After processing a leaf (no outgoing edge), pop top node and edge, and go down the next edge of the node on top of stack as before. If no next edge, pop again. This walks all paths from root to accepting nodes, and has the path in the stack. $\endgroup$
    – babou
    Apr 2, 2014 at 19:32

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.