Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: substring

Sortuj według:

Ogranicz wyniki do:

On the State Complexity of Scattered Substrings and Superstrings

Okhotin A.

Fundamenta Informaticae

2010

Vol. 99, nr 3

325-338

It is proved that the set of scattered substrings of a language recognized by an n-state DFA requires a DFA with at least [formula] 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 [formula] 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 [formula]