Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
The paper determines the number of states in a two-way deterministic finite automaton (2DFA) over a one-letter alphabet sufficient and in the worst case necessary to represent the results of the following operations: (i) intersection of an m-state 2DFA and an n-state 2DFA requires between m∈+∈n and m∈+∈n∈+∈1 states; (ii) union of an m-state 2DFA and an n-state 2DFA, between m∈+∈n and 2m∈+∈n∈+∈4 states; (iii) Kleene star of an n-state 2DFA, (g(n)∈+∈O(n))2 states, where is the maximum value of lcm(p 1, ..., p k ) for , known as Landau's function; (iv) k-th power of an n-state 2DFA, between (k∈-∈1)g(n)∈-∈k and k(g(n)∈+∈n) states; (v) concatenation of an m-state and an n-state 2DFAs, states.
Язык оригинала | английский |
---|---|
Название основной публикации | Descriptional Complexity of Formal Systems - 13th International Workshop, DCFS 2011, Proceedings |
Страницы | 222-234 |
Число страниц | 13 |
DOI | |
Состояние | Опубликовано - 11 авг 2011 |
Событие | 13th International Workshop of Descriptional Complexity of Formal Systems, DCFS 2011 - Giessen/Limburg, Германия Продолжительность: 25 июл 2011 → 27 июл 2011 |
Название | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Том | 6808 LNCS |
ISSN (печатное издание) | 0302-9743 |
ISSN (электронное издание) | 1611-3349 |
конференция | 13th International Workshop of Descriptional Complexity of Formal Systems, DCFS 2011 |
---|---|
Страна/Tерритория | Германия |
Город | Giessen/Limburg |
Период | 25/07/11 → 27/07/11 |
ID: 41143605