Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
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.
Язык оригинала | английский |
---|---|
Название основной публикации | Descriptional Complexity of Formal Systems - 22nd International Conference, 2020, Proceedings |
Редакторы | Galina Jirásková, Giovanni Pighizzini |
Издатель | Springer Nature |
Страницы | 104-116 |
Число страниц | 13 |
ISBN (печатное издание) | 9783030625351 |
DOI | |
Состояние | Опубликовано - 2020 |
Событие | 22nd International Conference on Descriptional Complexity of Format Systems, DCFS 2020 - Vienna, Австрия Продолжительность: 24 авг 2020 → 26 авг 2020 |
Название | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Том | 12442 LNCS |
ISSN (печатное издание) | 0302-9743 |
ISSN (электронное издание) | 1611-3349 |
конференция | 22nd International Conference on Descriptional Complexity of Format Systems, DCFS 2020 |
---|---|
Страна/Tерритория | Австрия |
Город | Vienna |
Период | 24/08/20 → 26/08/20 |
ID: 72034528