Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
The paper estimates the number of states in an unambiguous finite automaton (UFA) that is sufficient and in the worst case necessary to simulate an n-state two-way deterministic finite automaton (2DFA). It is proved that a 2DFA with n states can be transformed to a UFA with fewer than 2n· n! states. On the other hand, for every n, there is a language recognized by an n-state 2DFA that requires a UFA with at least Ω((42)n·n-1/2) states. The latter result is proved by estimating the rank of a certain matrix.
Язык оригинала | английский |
---|---|
Название основной публикации | Language and Automata Theory and Applications - 15th International Conference, LATA 2021, Proceedings |
Редакторы | Alberto Leporati, Carlos Martín-Vide, Dana Shapira, Claudio Zandron |
Издатель | Springer Nature |
Страницы | 81-93 |
Число страниц | 13 |
ISBN (печатное издание) | 9783030681944 |
DOI | |
Состояние | Опубликовано - фев 2021 |
Событие | 15th International Conference on Language and Automata Theory and Applications, LATA 2021 - Milan, Италия Продолжительность: 1 мар 2021 → 5 мар 2021 |
Название | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Том | 12638 LNCS |
ISSN (печатное издание) | 0302-9743 |
ISSN (электронное издание) | 1611-3349 |
конференция | 15th International Conference on Language and Automata Theory and Applications, LATA 2021 |
---|---|
Страна/Tерритория | Италия |
Город | Milan |
Период | 1/03/21 → 5/03/21 |
ID: 78911685