Directed acyclic word graph

For the US Department of Defense review panel, see Deputy’s Advisory Working Group.

For the dictionary data structure that is sometimes called a DAWG, see Deterministic acyclic finite state automaton.

In computer science, a directed acyclic word graph (DAWG) is a data structure that represents the set of suffixes of a string. As its name implies, a DAWG takes the form of a directed acyclic graph.

See also

• GADDAG
• Suffix array
• Suffix tree

References

• Inenaga, S.; Hoshino, H.; Shinohara, A.; Takeda, M.; Arikawa, S. (2001), "On-line construction of symmetric compact directed acyclic word graphs", Proc. 8th Int. Symp. String Processing and Information Retrieval, 2001. SPIRE 2001, pp. 96–110, doi:10.1109/SPIRE.2001.989743, ISBN 0-7695-1192-9 .
• Crochemore, Maxime; Vérin, Renaud (1997), "Direct construction of compact directed acyclic word graphs", Combinatorial Pattern Matching, Lecture Notes in Computer Science, Springer-Verlag, pp. 116–129, doi:10.1007/3-540-63220-4_55 .
• Epifanio, Chiara; Mignosi, Filippo; Shallit, Jeffrey; Venturini, Ilaria (2004), "Sturmian graphs and a conjecture of Moser", in Calude, Cristian S.; Calude, Elena; Dineen, Michael J., Developments in language theory. Proceedings, 8th international conference (DLT 2004), Auckland, New Zealand, December 2004, Lecture Notes in Computer Science 3340, Springer-Verlag, pp. 175–187, ISBN 3-540-24014-4, Zbl 1117.68454 
• Do, H.H.; Sung, W.K. (2011), "Compressed Directed Acyclic Word Graph with Application in Local Alignment", Computing and Combinatorics, Lecture Notes in Computer Science 6842, Springer-Verlag, pp. 503–518, doi:10.1007/978-3-642-22685-4_44, ISBN 978-3-642-22684-7