Standard

On the length of shortest strings accepted by two-way finite automata. / Dobronravov, Egor; Dobronravov, Nikita; Okhotin, Alexander.

Developments in Language Theory - 23rd International Conference, DLT 2019, Proceedings. ed. / Piotrek Hofman; Michał Skrzypczak. Springer Nature, 2019. p. 88-99 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11647 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Dobronravov, E, Dobronravov, N & Okhotin, A 2019, On the length of shortest strings accepted by two-way finite automata. in P Hofman & M Skrzypczak (eds), Developments in Language Theory - 23rd International Conference, DLT 2019, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11647 LNCS, Springer Nature, pp. 88-99, 23rd International Conference on Developments in Language Theory, DLT 2019, Warsaw, Poland, 5/08/19. https://doi.org/10.1007/978-3-030-24886-4_6

APA

Dobronravov, E., Dobronravov, N., & Okhotin, A. (2019). On the length of shortest strings accepted by two-way finite automata. In P. Hofman, & M. Skrzypczak (Eds.), Developments in Language Theory - 23rd International Conference, DLT 2019, Proceedings (pp. 88-99). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11647 LNCS). Springer Nature. https://doi.org/10.1007/978-3-030-24886-4_6

Vancouver

Dobronravov E, Dobronravov N, Okhotin A. On the length of shortest strings accepted by two-way finite automata. In Hofman P, Skrzypczak M, editors, Developments in Language Theory - 23rd International Conference, DLT 2019, Proceedings. Springer Nature. 2019. p. 88-99. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-030-24886-4_6

Author

Dobronravov, Egor ; Dobronravov, Nikita ; Okhotin, Alexander. / On the length of shortest strings accepted by two-way finite automata. Developments in Language Theory - 23rd International Conference, DLT 2019, Proceedings. editor / Piotrek Hofman ; Michał Skrzypczak. Springer Nature, 2019. pp. 88-99 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{1125a4eec19a40a2847b710366bd2576,
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 Ω(8n/5) and less than, 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 (Formula Presented).",
author = "Egor Dobronravov and Nikita Dobronravov and Alexander Okhotin",
year = "2019",
month = jan,
day = "1",
doi = "10.1007/978-3-030-24886-4_6",
language = "English",
isbn = "9783030248857",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "88--99",
editor = "Piotrek Hofman and Micha{\l} Skrzypczak",
booktitle = "Developments in Language Theory - 23rd International Conference, DLT 2019, Proceedings",
address = "Germany",
note = "23rd International Conference on Developments in Language Theory, DLT 2019 ; Conference date: 05-08-2019 Through 09-08-2019",

}

RIS

TY - GEN

T1 - On the length of shortest strings accepted by two-way finite automata

AU - Dobronravov, Egor

AU - Dobronravov, Nikita

AU - Okhotin, Alexander

PY - 2019/1/1

Y1 - 2019/1/1

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 Ω(8n/5) and less than, 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 (Formula Presented).

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 Ω(8n/5) and less than, 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 (Formula Presented).

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

UR - http://www.mendeley.com/research/length-shortest-strings-accepted-twoway-finite-automata

U2 - 10.1007/978-3-030-24886-4_6

DO - 10.1007/978-3-030-24886-4_6

M3 - Conference contribution

AN - SCOPUS:85073906465

SN - 9783030248857

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 88

EP - 99

BT - Developments in Language Theory - 23rd International Conference, DLT 2019, Proceedings

A2 - Hofman, Piotrek

A2 - Skrzypczak, Michał

PB - Springer Nature

T2 - 23rd International Conference on Developments in Language Theory, DLT 2019

Y2 - 5 August 2019 through 9 August 2019

ER -

ID: 49647585