Talk:Deterministic acyclic finite state automaton

	This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.ComputingWikipedia:WikiProject ComputingTemplate:WikiProject ComputingComputing
???	This article has not yet received a rating on Wikipedia's content assessment scale.
???	This article has not yet received a rating on the project's importance scale.

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]

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]

Diagram incorrect

In the DAWG on the right (in the diagram), I am pretty sure the O and the A would need to have separate nodes, and not simply be differently labeled links to the same node. Both O and A would link to the same P node and S node though. —Preceding unsigned comment added by 67.169.75.188 (talk) 04:11, 25 March 2011 (UTC)[reply]

No, I'm pretty sure the diagram is correct. –Justin Force 23:59, 25 April 2012 (UTC)[reply]

Badly Named?

Technically its a letter or character graph not a "word graph" ? Because the adjacent is expressed between nodes composed of letters of characters? — Preceding unsigned comment added by 216.239.45.4 (talk) 19:52, 7 July 2011 (UTC)[reply]

Conflation of two distinct data structures

This article seems to conflate two related but distinct data structures: according to DADS, a DAWG is either a DFA that represents suffixes of a string, or a minimal DFA that represents a set of strings (called a "dictionary" or DAFSA by Daciuk et al.). The article describes the latter, but the references mostly pertain to the former. Qwertyus (talk) 12:00, 25 December 2012 (UTC)[reply]

Fixed by moving and editing directed acyclic word graph to the current article, then recreating the other article by moving some content there. Qwertyus (talk) 12:35, 25 December 2012 (UTC)[reply]