Standard

On the Length of Shortest Strings Accepted by Two-way Finite Automata. / Dobronravov, Egor; Dobronravov, Nikita; Okhotin, Alexander.

In: Fundamenta Informaticae, Vol. 180, No. 4, 30.06.2021, p. 315-331.

Research output: Contribution to journalArticlepeer-review

Harvard

APA

Vancouver

Author

BibTeX

@article{1d699d2cf0b5433c94f99c05d8faad11,
title = "On the Length of Shortest Strings Accepted by Two-way Finite Automata",
abstract = "Given a two-way finite automaton recognizing a non-empty language, consider the length of the shortest string it accepts, and, for each n ≥ 1, let f(n) be the maximum of these lengths over all n-state automata. It is proved that for n-state two-way finite automata, whether deterministic or nondeterministic, this number is at least Ω(10n/5) and less than (2nn+1), with the lower bound reached over an alphabet of size Θ(n). Furthermore, for deterministic automata and for a fixed alphabet of size m ≥ 1, the length of the shortest string is at least e(1+o(1))mn(log n- log m). ",
keywords = "Finite automata, shortest string, state complexity, two-way automata",
author = "Egor Dobronravov and Nikita Dobronravov and Alexander Okhotin",
note = "Publisher Copyright: {\textcopyright} 2021 - IOS Press. All rights reserved. Publisher Copyright: {\textcopyright} 2021 - IOS Press. All rights reserved.",
year = "2021",
month = jun,
day = "30",
doi = "10.3233/fi-2021-2044",
language = "English",
volume = "180",
pages = "315--331",
journal = "Fundamenta Informaticae",
issn = "0169-2968",
publisher = "IOS Press",
number = "4",

}

RIS

TY - JOUR

T1 - On the Length of Shortest Strings Accepted by Two-way Finite Automata

AU - Dobronravov, Egor

AU - Dobronravov, Nikita

AU - Okhotin, Alexander

N1 - Publisher Copyright: © 2021 - IOS Press. All rights reserved. Publisher Copyright: © 2021 - IOS Press. All rights reserved.

PY - 2021/6/30

Y1 - 2021/6/30

N2 - Given a two-way finite automaton recognizing a non-empty language, consider the length of the shortest string it accepts, and, for each n ≥ 1, let f(n) be the maximum of these lengths over all n-state automata. It is proved that for n-state two-way finite automata, whether deterministic or nondeterministic, this number is at least Ω(10n/5) and less than (2nn+1), with the lower bound reached over an alphabet of size Θ(n). Furthermore, for deterministic automata and for a fixed alphabet of size m ≥ 1, the length of the shortest string is at least e(1+o(1))mn(log n- log m).

AB - Given a two-way finite automaton recognizing a non-empty language, consider the length of the shortest string it accepts, and, for each n ≥ 1, let f(n) be the maximum of these lengths over all n-state automata. It is proved that for n-state two-way finite automata, whether deterministic or nondeterministic, this number is at least Ω(10n/5) and less than (2nn+1), with the lower bound reached over an alphabet of size Θ(n). Furthermore, for deterministic automata and for a fixed alphabet of size m ≥ 1, the length of the shortest string is at least e(1+o(1))mn(log n- log m).

KW - Finite automata

KW - shortest string

KW - state complexity

KW - two-way automata

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

U2 - 10.3233/fi-2021-2044

DO - 10.3233/fi-2021-2044

M3 - Article

AN - SCOPUS:85109217396

VL - 180

SP - 315

EP - 331

JO - Fundamenta Informaticae

JF - Fundamenta Informaticae

SN - 0169-2968

IS - 4

ER -

ID: 78913444