Standard

Longer Shortest Strings in Two-Way Finite Automata. / Крымский, Станислав Тимурович; Okhotin, Alexander.

Descriptional Complexity of Formal Systems - 22nd International Conference, 2020, Proceedings. ed. / Galina Jirásková; Giovanni Pighizzini. Springer Nature, 2020. p. 104-116 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12442 LNCS).

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

Harvard

Крымский, СТ & Okhotin, A 2020, Longer Shortest Strings in Two-Way Finite Automata. in G Jirásková & G Pighizzini (eds), Descriptional Complexity of Formal Systems - 22nd International Conference, 2020, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12442 LNCS, Springer Nature, pp. 104-116, 22nd International Conference on Descriptional Complexity of Format Systems, DCFS 2020, Vienna, Austria, 24/08/20. https://doi.org/10.1007/978-3-030-62536-8_9

APA

Крымский, С. Т., & Okhotin, A. (2020). Longer Shortest Strings in Two-Way Finite Automata. In G. Jirásková, & G. Pighizzini (Eds.), Descriptional Complexity of Formal Systems - 22nd International Conference, 2020, Proceedings (pp. 104-116). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12442 LNCS). Springer Nature. https://doi.org/10.1007/978-3-030-62536-8_9

Vancouver

Крымский СТ, Okhotin A. Longer Shortest Strings in Two-Way Finite Automata. In Jirásková G, Pighizzini G, editors, Descriptional Complexity of Formal Systems - 22nd International Conference, 2020, Proceedings. Springer Nature. 2020. p. 104-116. (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-62536-8_9

Author

Крымский, Станислав Тимурович ; Okhotin, Alexander. / Longer Shortest Strings in Two-Way Finite Automata. Descriptional Complexity of Formal Systems - 22nd International Conference, 2020, Proceedings. editor / Galina Jirásková ; Giovanni Pighizzini. Springer Nature, 2020. pp. 104-116 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{4c453280e367482781f3aa5e2d09f0a6,
title = "Longer Shortest Strings in Two-Way Finite Automata",
abstract = "In a recent paper, Dobronravov et al. (“On the length of shortest strings accepted by two-way finite automata”, DLT 2019) prove that the shortest string in a language recognized by an n-state two-way finite automaton (2DFA) can be at least symbols long, improved to in their latest contribution. The lower bound was obtained using “direction-determinate” 2DFA, which always remember their direction of motion at the last step, and used an alphabet of size In this paper, the method of Dobronravov et al. is extended to a new, more general class: the semi-direction-determinate 2DFA. This yields n-state 2DFA with shortest strings of length Furthermore, the construction is adapted to use a fixed alphabet, resulting in shortest strings of length It is also shown that an n-state semi-direction-determinate 2DFA can be transformed to a one-way NFA with states.",
author = "Крымский, {Станислав Тимурович} and Alexander Okhotin",
note = "Funding Information: Research supported by Russian Science Foundation, project 18-11-00100. Publisher Copyright: {\textcopyright} 2020, Springer Nature Switzerland AG. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.; 22nd International Conference on Descriptional Complexity of Format Systems, DCFS 2020 ; Conference date: 24-08-2020 Through 26-08-2020",
year = "2020",
doi = "10.1007/978-3-030-62536-8_9",
language = "English",
isbn = "9783030625351",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "104--116",
editor = "Galina Jir{\'a}skov{\'a} and Giovanni Pighizzini",
booktitle = "Descriptional Complexity of Formal Systems - 22nd International Conference, 2020, Proceedings",
address = "Germany",

}

RIS

TY - GEN

T1 - Longer Shortest Strings in Two-Way Finite Automata

AU - Крымский, Станислав Тимурович

AU - Okhotin, Alexander

N1 - Funding Information: Research supported by Russian Science Foundation, project 18-11-00100. Publisher Copyright: © 2020, Springer Nature Switzerland AG. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2020

Y1 - 2020

N2 - In a recent paper, Dobronravov et al. (“On the length of shortest strings accepted by two-way finite automata”, DLT 2019) prove that the shortest string in a language recognized by an n-state two-way finite automaton (2DFA) can be at least symbols long, improved to in their latest contribution. The lower bound was obtained using “direction-determinate” 2DFA, which always remember their direction of motion at the last step, and used an alphabet of size In this paper, the method of Dobronravov et al. is extended to a new, more general class: the semi-direction-determinate 2DFA. This yields n-state 2DFA with shortest strings of length Furthermore, the construction is adapted to use a fixed alphabet, resulting in shortest strings of length It is also shown that an n-state semi-direction-determinate 2DFA can be transformed to a one-way NFA with states.

AB - In a recent paper, Dobronravov et al. (“On the length of shortest strings accepted by two-way finite automata”, DLT 2019) prove that the shortest string in a language recognized by an n-state two-way finite automaton (2DFA) can be at least symbols long, improved to in their latest contribution. The lower bound was obtained using “direction-determinate” 2DFA, which always remember their direction of motion at the last step, and used an alphabet of size In this paper, the method of Dobronravov et al. is extended to a new, more general class: the semi-direction-determinate 2DFA. This yields n-state 2DFA with shortest strings of length Furthermore, the construction is adapted to use a fixed alphabet, resulting in shortest strings of length It is also shown that an n-state semi-direction-determinate 2DFA can be transformed to a one-way NFA with states.

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

UR - https://www.mendeley.com/catalogue/d890d8d7-8496-3322-bc3d-9867a2798e2c/

U2 - 10.1007/978-3-030-62536-8_9

DO - 10.1007/978-3-030-62536-8_9

M3 - Conference contribution

AN - SCOPUS:85097363756

SN - 9783030625351

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

SP - 104

EP - 116

BT - Descriptional Complexity of Formal Systems - 22nd International Conference, 2020, Proceedings

A2 - Jirásková, Galina

A2 - Pighizzini, Giovanni

PB - Springer Nature

T2 - 22nd International Conference on Descriptional Complexity of Format Systems, DCFS 2020

Y2 - 24 August 2020 through 26 August 2020

ER -

ID: 72034528