• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

On the State Complexity of Scattered Substrings and Superstrings

Alexander Okhotin, On the State Complexity of Scattered Substrings and Superstrings. TUCS Technical Reports 849, Turku Centre for Computer Science, 2007.

Abstract:

It is proved that the set of <i>scattered substrings</i> of a language recognized by an <i>n</i>-state DFA requires 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}-6}$ states. A similar state complexity function for <i>scattered superstrings</i> is shown to be $2^{n-2}+1$ for an alphabet of at least <i>n</i>-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) 4^{\sqrt{n/2}} n^{-3/4}$.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tOkhotin07e,
  title = {On the State Complexity of Scattered Substrings and Superstrings},
  author = {Okhotin, Alexander},
  number = {849},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2007},
  keywords = {descriptional complexity, finite automata, state complexity, substring, subword, subsequence, Higman-Haines sets},
  ISBN = {978-952-12-1968-9},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication