Talk:Deterministic acyclic finite state automaton

Trade-off between DAWG and trie

It seems to me that there is a complication in replacing a trie with a directed acyclic word graph, but this is not mentioned in the article. Specifically, allowing nodes to have multiple incoming edges results in nodes that inherently represent (or store) multiple keys (e.g. both desertion and desertification, as in the article's example). This forces these nodes to be buckets, in the same way that a hash table has buckets for hash collisions. These collisions introduce a bit of extra complexity when growing or shrinking this data structure. When, where, and how should paths in the graph be split (to reduce the number of collisions) or joined (to preserve the storage space benefit)? In short, what are the algorithms associated with this data structure? Can someone with access to the article's reference elaborate on this? JCarlos 04:39, 22 October 2007 (UTC)[reply]

I don't have access to the reference, and I just got linked here, but if I type the phrase "directed ac" into my Firefox search form, it helpfully pops up several useful phrases, such as "directed acyclic graph" and "directed acyclic word graph." I would imagine the search form is using one. 99.7.50.217 (talk) 05:49, 26 January 2010 (UTC)[reply]

Contradiction in opening paragraph

Am I missing something here? The opening paragraph seems to have an inherent contradiction (emphasis mine):

"... It is used to represent a set of strings and supports a constant time search operation. The lookup time is proportional to the length of the search string and is the same as an equivalent trie."

Not to mention the fact that a DAWG doesn't look like it would support a constant-time search operation. --ian (talk) 18:00, 4 December 2007 (UTC)[reply]

It's constant w.r.t. the number of words in the DAWG. --196.210.102.113 (talk) 11:22, 26 January 2008 (UTC)[reply]

Infixes?

If I'm reading the definition correctly, paths in DAWGs may also share infixes. Isn't that mentioned in the literature? Regards, Paradoctor (talk) 13:10, 21 November 2009 (UTC)[reply]