Directed Acyclic Word Graph (other)
Directed acyclic word graph (DAWG) may refer to two related, but distinct, automata constructions in computer science: * Deterministic acyclic finite state automaton, a data structure that represents a finite set of strings * Suffix automaton, a finite automaton that functions as a suffix index {{dab ...
[...More Info...]       [...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  

Deterministic Acyclic Finite State Automaton
In computer science, a deterministic acyclic finite state automaton (DAFSA),Jan Daciuk, Stoyan Mihov, Bruce Watson and Richard Watson (2000). Incremental construction of minimal acyclic finite state automata. Computational Linguistics 26(1):3-16. also called a directed acyclic word graph (DAWG; though that name also refers to a related data structure that functions as a suffix index) is a data structure that represents a set of strings, and allows for a query operation that tests whether a given string belongs to the set in time proportional to its length. Algorithms exist to construct and maintain such automata, while keeping them minimal. A DAFSA is a special case of a finite state recognizer that takes the form of a directed acyclic graph with a single source vertex (a vertex with no incoming edges), in which each edge of the graph is labeled by a letter or symbol, and in which each vertex has at most one outgoing edge for each possible letter or symbol. The strings represe ...
[...More Info...]       [...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]