The following may contain errors. It is precisely because I am notsure I understand the topic that I am asking questions. I do not havebooks about it and could not find an adequate reference on the web.I am discussing a problem regarding an enumeration of strings thatshould be in amortized constant delay. From what I understood (butunderstanding that is part of my question), this means that the averagetime taken for each answer should be independent of the size of theanswer, so that the total cost is $O(n)$ where $n$ is the number ofanswers.My discussion partner went on to assert (I believe) that amortizedconstant delay is possible for enumerating the strings accepted by atrie, but not for enumerating the paths of a DAG. And I am at loss tosee a significant difference, since proper use of a stack should letme explore the DAG as if it had been exploded into a trie (byduplicating whatever is below a merge vertex).The only real difference I can see is that the accepting nodes of atrie can be labeled with a single symbol identifier characterizing the accepted word (turning the trieinto a Moore machine) so that the total cost is only a traversal ofthe trie, with single step output of the symbol label when traversing anaccepting node.Such labeling identification is not possible for a DFA structured as a DAG, since anaccepting node can correspond to different paths. The only way to namepaths is to describe them in extenso (or nearly so: enough to disambiguate merges), so that the costof 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 costjust 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.
What is hiding behind amortized constant delay enumeration?
complexity theory;graphs;strings;amortized analysis;enumeration