|
| << vorige | volgende >> |
Tijdschrift beschrijving
Alle jaargangen van het bijbehorende tijdschrift
Alle afleveringen van het bijbehorende jaargang
Alle artikelen van de bijbehorende aflevering
Details van artikel 3 van 6 gevonden artikelen
| Titel: |
On the State Complexity of Scattered Substrings and Superstrings |
| Auteur: |
Okhotin, Alexander |
| Verschenen in: |
Fundamenta informaticae |
| Paginering: | Jaargang 99 (2010) nr. 3 pagina's 325-338 |
| Jaar: |
2010-05-25 |
| Inhoud: |
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. |
| Uitgever: |
IOS Press |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 3 van 6 gevonden artikelen
| << vorige | volgende >> |