Subsequence Automata with Default Transitions

Philip Bille, Inge Li Gørtz, Frederik Rye Skjoldjensen

Let $S$ be a string of length $n$ with characters from an alphabet of size $\sigma$. The \emph{subsequence automaton} of $S$ (often called the \emph{directed acyclic subsequence graph})…