CACrown ArchivesThe cinema collection
EN/FR
Search
Menu
Research dossier · General Reference

Deterministic acyclic finite state automaton

computer data structure that represents a finite set of strings

Cross-disciplinary reference desk with index cards, atlas, dictionary and catalogue
General referenceInterpretive dossier study · Crown Archives visual atlas
Record originEnglish Wikipedia
Text licenseCC BY-SA 4.0
Source revisionAug 29, 2026
Entity authorityQ17008992 ↗
Source-derived summary

In computer science, a deterministic acyclic finite state automaton (DAFSA),

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.

DAFSA is the rediscovery of a data structure called Directed Acyclic Word Graph (DAWG), although the same name had already been given to a different data structure which is related to suffix automaton.

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 represented by the DAFSA are formed by the symbols on paths in the graph from the source vertex to any sink vertex (a vertex with no outgoing edges). In fact, a deterministic finite state automaton is acyclic if and only if it recognizes a finite set of strings.

History

Blumer et al first defined terminology Directed Acyclic Word Graph (DAWG) in 1983. Appel and Jacobsen used the same naming for a different data structure in 1988. Independent of earlier work, Daciuk et al rediscovered the latter data structure in 2000 but called it DAFSA.

Comparison to tries

By allowing the same vertices to be reached by multiple paths, a DAFSA may use significantly fewer vertices than the strongly related trie data structure. Consider, for example, the four English words "tap", "taps", "top", and "tops".

Editorial summary

This brief starts where responsible research should: with the source description of “Deterministic acyclic finite state automaton” as computer data structure that represents a finite set of strings. Everything that follows is an evidence route, not borrowed authority.

Editorial reviewA practical starting point whose main value is the path it opens into stronger specialist and primary sources. The current lead gives the account dated anchors—1983, 1988, 2000—that can be checked directly. The selected authority fields contribute no independent date. The account is most persuasive where Deterministic, acyclic and finite can be independently traced.
Editorial analysis

Why this record matters

The subject matters to the general reference register because the source frames it as computer data structure that represents a finite set of strings. Its deeper value depends on whether names, dates, institutions and citations support that framing.

Evidence profile

Named sources, stable identifiers and responsible institutions provide the strongest route from overview to verifiable evidence. The source revision retrieved here is dated Aug 29, 2026. The linked authority identifier is Q17008992. None of the 0 selected statements returned an explicit reference. The first chronological checks are 1983, 1988 and 2000.

Critical limits

A concise general-reference account can conceal disagreements about scope, terminology or the weight assigned to individual sources. The source lead contains qualifying language; that uncertainty should survive quotation, summary and reuse. Authority statements aid reconciliation but still require their own references, qualifiers and ranks to be checked.

How to read it

Use the entry as an orientation point, then follow its citations and revision history. Names, dates and institutional relationships should be checked against the original record.

Best used for
  • Subject orientation
  • Search vocabulary
  • Locating named sources
Verify next

The closest primary source, responsible institution and strongest cited specialist reference.

Three-step research path

  1. Establish the record: confirm the title “Deterministic acyclic finite state automaton”, its source revision and the description used here.
  2. Expand the search: follow Deterministic acyclic finite state automaton primary sources, Deterministic acyclic finite state automaton archive and Deterministic research across catalogues and specialist indexes.
  3. Test the account: compare the strongest cited source with the responsible institution’s current record and note any disagreement.

Questions for further research

  1. Which source most directly establishes the central claim about “Deterministic acyclic finite state automaton”?
  2. Which cited source is closest to the event, object or claim?
  3. What terminology or title could unlock a more precise catalogue search?
Subject index

Search terms from this dossier

Source & attribution

This entry incorporates text from “Deterministic acyclic finite state automaton” on English Wikipedia. Contributors are listed in the page history. Text is available under the Creative Commons Attribution-ShareAlike 4.0 License. Selected authority identifiers and statements are retrieved from Wikidata under CC0; their references and qualifiers remain part of the verification path.