Subsequence automata with default transitions

Publication: Research - peer-reviewJournal article – Annual report year: 2017

Documents

DOI

View graph of relations

Let S be a string of length n with characters from an alphabet of size σ. The subsequence automaton of S (often called the directed acyclic subsequence graph) is the minimal deterministic finite automaton accepting all subsequences of S. A straightforward construction shows that the size (number of states and transitions) of the subsequence automaton is O(nσ) and that this bound is asymptotically optimal. In this paper, we consider subsequence automata with default transitions, that is, special transitions to be taken only if none of the regular transitions match the current character, and which do not consume the current character. We show that with default transitions, much smaller subsequence automata are possible, and provide a full trade-off between the size of the automaton and the delay, i.e., the maximum number of consecutive default transitions followed before consuming a character. Specifically, given any integer parameter k, 1<k≤σ, we present a subsequence automaton with default transitions of size O(nklogk⁡σ) and delay O(logk⁡σ). Hence, with k=2 we obtain an automaton of size O(nlog⁡σ) and delay O(log⁡σ). At the other extreme, with k=σ, we obtain an automaton of size O(nσ) and delay O(1), thus matching the bound for the standard subsequence automaton construction. Finally, we generalize the result to multiple strings. The key component of our result is a novel hierarchical automata construction of independent interest.

Original languageEnglish
JournalJournal of Discrete Algorithms
Volume44
Pages (from-to)48-55
Number of pages8
ISSN1570-8667
DOIs
StatePublished - 1 May 2017
CitationsWeb of Science® Times Cited: 0

    Keywords

  • Algorithm, Automaton, Subsequence matching
Download as:
Download as PDF
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
Word

ID: 140635745