On the State Complexity of Scattered Substrings and Superstrings

Abstract

It is proved that the set of scattered substrings of a language recognized by an n-state DFA requires a DFA with at least 2 $^{n/2-2}$ states (the known upper bound is 2 $^n$ ), with witness languages given over an exponentially growing alphabet. For a 3-letter alphabet, scattered substrings are shown to require at least 2 $^{sqrt{2n+30}-6}$ states. A similar state complexity function for scattered superstrings is determined to be exactly 2 $^{n-2}$ + 1 for an alphabet of at least n − 2 letters, and strictly less for any smaller alphabet. For a 3-letter alphabet, the state complexity of scattered superstrings is at least 1/5 4sqrt{n/2}n-3/4.