Weak Factor Automata: Comparing (Failure) Oracles and Storacles
Loek Cleophas, Derrick G. Kourie, Bruce W. Watson · 2013
Abstract. The factor oracle [3] is a data structure for weak factor recognition. It is a deterministic finite automaton (DFA) built on a string p of length m that is acyclic, recognizes at least all factors of p, has m+1 states which are all final, is homogeneous, and has m to 2m − 1 transitions. The factor storacle [6] is an alternative automaton that satisfies the same properties, except that its number of transitions may be larger than 2m−1, although it is conjectured to be linear with an upper bound of at most 3m. In [14] (among others), we described the concept of a failure automaton i.e. a failure DFA (FDFA), in which so-called failure transitions are used to reduce the total num-ber of transitions and thus reduce representation space compared to the use of a DFA. We modify factor oracle and storacle construction algorithms to introduce failure arcs during the respective automata’s construction. We thus end up with four deterministic automata types for weak factor recognition: factor oracle, factor storacle, failure factor oracle, and failure factor storacle. We compare them empirically in terms of size. The results show that despite the relative simplicity of (failure) factor (st)oracles, the fail-ure versions show additional savings of 2–7 % in number of transitions, for generated