Standard

On the state complexity of scattered substrings and superstrings. / Okhotin, Alexander.

In: Fundamenta Informaticae, Vol. 99, No. 3, 02.07.2010, p. 325-338.

Research output: Contribution to journal › Article › peer-review

Harvard

Okhotin, A 2010, 'On the state complexity of scattered substrings and superstrings', Fundamenta Informaticae, vol. 99, no. 3, pp. 325-338. https://doi.org/10.3233/FI-2010-252

APA

Okhotin, A. (2010). On the state complexity of scattered substrings and superstrings. Fundamenta Informaticae, 99(3), 325-338. https://doi.org/10.3233/FI-2010-252

Vancouver

Okhotin A. On the state complexity of scattered substrings and superstrings. Fundamenta Informaticae. 2010 Jul 2;99(3):325-338. https://doi.org/10.3233/FI-2010-252

Author

Okhotin, Alexander. / On the state complexity of scattered substrings and superstrings. In: Fundamenta Informaticae. 2010 ; Vol. 99, No. 3. pp. 325-338.

BibTeX

@article{127152e677304662b682499bbcf7b538,
title = "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 2n), 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, Higman-Haines sets, state complexity, subsequence, substring, subword",
author = "Alexander Okhotin",
year = "2010",
month = jul,
day = "2",
doi = "10.3233/FI-2010-252",
language = "English",
volume = "99",
pages = "325--338",
journal = "Fundamenta Informaticae",
issn = "0169-2968",
publisher = "IOS Press",
number = "3",

}

RIS

TY - JOUR

T1 - On the state complexity of scattered substrings and superstrings

AU - Okhotin, Alexander

PY - 2010/7/2

Y1 - 2010/7/2

N2 - 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 2n), 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.

AB - 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 2n), 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.

KW - descriptional complexity

KW - finite automata

KW - Higman-Haines sets

KW - state complexity

KW - subsequence

KW - substring

KW - subword

UR - http://www.scopus.com/inward/record.url?scp=77954061045&partnerID=8YFLogxK

U2 - 10.3233/FI-2010-252

DO - 10.3233/FI-2010-252

M3 - Article

AN - SCOPUS:77954061045

VL - 99

SP - 325

EP - 338

JO - Fundamenta Informaticae

JF - Fundamenta Informaticae

SN - 0169-2968

IS - 3

ER -

ID: 41142137