Subsequence automata with default transitions

Autor: Inge Li Gørtz, Philip Bille, Frederik Rye Skjoldjensen
Rok vydání: 2017
Předmět:
Automaton
FOS: Computer and information sciences
Formal Languages and Automata Theory (cs.FL)
Timed automaton
Büchi automaton
Computer Science - Formal Languages and Automata Theory
0102 computer and information sciences
02 engineering and technology
Longest increasing subsequence
ω-automaton
01 natural sciences
Theoretical Computer Science
Combinatorics
Deterministic automaton
Computer Science - Data Structures and Algorithms
0202 electrical engineering
electronic engineering
information engineering
Discrete Mathematics and Combinatorics
Data Structures and Algorithms (cs.DS)
Nondeterministic finite automaton
Mathematics
Discrete mathematics
Powerset construction
Nonlinear Sciences::Cellular Automata and Lattice Gases
Automata construction
Algorithm
Computational Theory and Mathematics
010201 computation theory & mathematics
Subsequence matching
020201 artificial intelligence & image processing
Computer Science::Formal Languages and Automata Theory
Zdroj: Bille, P, Gørtz, I L & Skjoldjensen, F R 2017, ' Subsequence automata with default transitions ', Journal of Discrete Algorithms, vol. 44, pp. 48-55 . https://doi.org/10.1016/j.jda.2017.05.001
ISSN: 1570-8667
DOI: 10.1016/j.jda.2017.05.001
Popis: 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}) 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\sigma)$ and that this bound is asymptotically optimal. In this paper, we consider subsequence automata with \emph{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 \emph{delay}, i.e., the maximum number of consecutive default transitions followed before consuming a character. Specifically, given any integer parameter $k$, $1 < k \leq \sigma$, we present a subsequence automaton with default transitions of size $O(nk\log_{k}\sigma)$ and delay $O(\log_k \sigma)$. Hence, with $k = 2$ we obtain an automaton of size $O(n \log \sigma)$ and delay $O(\log \sigma)$. On the other extreme, with $k = \sigma$, we obtain an automaton of size $O(n \sigma)$ 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.
Comment: Corrected typos
Databáze: OpenAIRE
Externí odkaz: