Suffix automaton: Difference between revisions

Revision as of 20:27, 7 November 2020

Revision as of 09:58, 8 November 2020

Line 9:

}}

In [[computer science]], athe '''suffix automaton''' is the smallest partial [[deterministic finite automaton]] that recognizes the set of [[Substring|suffixes]] of a given [[String (computer science)|string]] <math>S=s_1 s_2 \dots s_n</math>. The [[state graph]] of a suffix automaton is called a directed acyclic word graph (DAWG), a term that is also sometimes used for any [[deterministic acyclic finite state automaton]]. Less formally, the suffix automaton of a string <math>S</math> is the [[directed acyclic graph]] with a dedicated initial vertex and a set of "final" vertices, such that:

# Its [[Arc (graph theory)|arcs]] are tagged with [[Character (computing)|letters]];

Line 15:

# for every suffix of <math>S</math> there exists a path from initial vertex to some final vertex such that the [[concatenation]] of letters on the path forms this suffix;

# it has the least number of vertices among all graphs defined by the properties above.

Speaking in the terms of [[automata theory]], a suffix automaton is the [[Minimal automaton|minimal]] partial [[deterministic finite automaton]] that recognizes the set of [[Substring|suffixes]] of a given [[String (computer science)|string]] <math>S=s_1 s_2 \dots s_n</math>. The [[state graph]] of a suffix automaton is called a directed acyclic word graph (DAWG), a term that is also sometimes used for any [[deterministic acyclic finite state automaton]].

Suffix automata were introduced in 1983 by a group of scientists from the [[University of Denver]] and the [[University of Colorado Boulder]]. They suggested a [[linear time]] [[online algorithm]] for its construction and showed that the suffix automaton of a string <math>S</math> having length at least two characters has at most <math display="inline">2|S| - 1</math> states and at most <math display="inline">3|S| - 4 </math> transitions. Further works have shown a close connection between suffix automata and [[suffix tree]]s, and have outlined several generalizations of suffix automata, such as compacted suffix automaton obtained by compression of nodes with a single outgoing arc.