Conference paper · Book chapter
Subsequence Automata with Default Transitions
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
The key component of our result is a novel hierarchical automata construction of independent interest.
Language: | English |
---|---|
Publisher: | Springer |
Year: | 2016 |
Pages: | 208-216 |
Proceedings: | 42nd International Conference on Current Trends in Theory and Practice of Computer ScienceInternational Conference on Current Trends in Theory and Practice of Computer Science |
Series: | Lecture Notes in Computer Science |
Journal subtitle: | 42nd International Conference on Current Trends in Theory and Practice of Computer Science, Harrachov, Czech Republic, January 23-28, 2016, Proceedings |
ISBN: | 3662491915 , 3662491923 , 9783662491911 and 9783662491928 |
ISSN: | 03029743 and 16113349 |
Types: | Conference paper and Book chapter |
DOI: | 10.1007/978-3-662-49192-8_17 |
ORCIDs: | Bille, Philip and Gørtz, Inge Li |