On the State Complexity of Scattered Substrings and Superstrings

Article type: Research Article

Authors: Okhotin, Alexander

Affiliations: Department of Mathematics, University of Turku Turku FIN¨C20014, Finland, and Academy of Finland. E-mail: alexander.okhotin@utu.fi

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.

Keywords: descriptional complexity, finite automata, state complexity, substring, subword, subsequence, Higman–Haines sets

DOI: 10.3233/FI-2010-252

Journal: Fundamenta Informaticae, vol. 99, no. 3, pp. 325-338, 2010