Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › Рецензирование
Longer Shortest Strings in Two-Way Finite Automata. / Крымский, Станислав Тимурович; Okhotin, Alexander.
Descriptional Complexity of Formal Systems - 22nd International Conference, 2020, Proceedings. ред. / Galina Jirásková; Giovanni Pighizzini. Springer Nature, 2020. стр. 104-116 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 12442 LNCS).Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › Рецензирование
}
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