Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
It is shown that a two-way deterministic finite automaton (2DFA) with n states over an alphabet Σ can be transformed to an equivalent one-way automaton (1DFA) with | Σ| · F(n) + 1 states, where F(n)=maxk=0nkn-k+1≤(n+1)n+1/(ln(n+1)·e1-o(1))n+1. This reflects the fact that, by keeping the last processed symbol in memory, the simulating 1DFA needs to remember only the state from which the 2DFA leaves the prefix read so far for the first time to the right together with a function that maps some n- k states moving to the left from the last processed symbol to some other k states moving to the right from this symbol. This reduces the number of functions describing the behaviour of the 2DFA on the prefix read so far. A close lower bound of F(n) states is established using a 5-symbol alphabet. The complexity of transforming a sweeping or a direction-determinate 2DFA to a 1DFA is shown to be exactly F(n).
Язык оригинала | английский |
---|---|
Название основной публикации | Descriptional Complexity of Formal Systems - 23rd IFIP WG 1.02 International Conference, DCFS 2021, Proceedings |
Редакторы | Yo-Sub Han, Sang-Ki Ko |
Издатель | Springer Nature |
Страницы | 26-37 |
Число страниц | 12 |
ISBN (печатное издание) | 9783030934880 |
DOI | |
Состояние | Опубликовано - 30 дек 2021 |
Событие | 23rd IFIP WG 1.02 International Conference on Descriptional Complexity of Format Systems, DCFS 2021 - Virtual, Online Продолжительность: 5 сен 2021 → 5 сен 2021 |
Название | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Том | 13037 LNCS |
ISSN (печатное издание) | 0302-9743 |
ISSN (электронное издание) | 1611-3349 |
конференция | 23rd IFIP WG 1.02 International Conference on Descriptional Complexity of Format Systems, DCFS 2021 |
---|---|
Город | Virtual, Online |
Период | 5/09/21 → 5/09/21 |
ID: 91382899