Subsequence Automata with Default Transitions

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

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

272 Downloads (Pure)

Abstract

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() 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(n log σ) and delay O(log σ). On the other extreme, with k = σ, we obtain an automaton of size O() and delay O(1), thus matching the bound for the standard subsequence automaton construction. The key component of our result is a novel hierarchical automata construction of independent interest.
Original languageEnglish
Title of host publicationSOFSEM 2016: Theory and Practice of Computer Science : 42nd International Conference on Current Trends in Theory and Practice of Computer Science, Harrachov, Czech Republic, January 23-28, 2016, Proceedings
Number of pages9
Volume9587
PublisherSpringer
Publication date2016
Pages208-216
ISBN (Print)978-3-662-49191-1
ISBN (Electronic)978-3-662-49192-8
DOIs
Publication statusPublished - 2016
Event42nd International Conference on Current Trends in Theory and Practice of Computer Science - Harrachov, Czech Republic
Duration: 23 Jan 201628 Jan 2016
Conference number: 42
http://www.sofsem.cz/sofsem16/

Conference

Conference42nd International Conference on Current Trends in Theory and Practice of Computer Science
Number42
Country/TerritoryCzech Republic
CityHarrachov
Period23/01/201628/01/2016
Internet address
SeriesLecture Notes in Computer Science
ISSN0302-9743

Fingerprint

Dive into the research topics of 'Subsequence Automata with Default Transitions'. Together they form a unique fingerprint.

Cite this