Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › Рецензирование
A framework for the study of periodic behaviour of two-way deterministic finite automata (2DFA) is developed. Computations of 2DFAs are represented by a two-way analogue of transformation semigroups, every element of which describes the behaviour of a 2DFA on a certain string x. A subsemigroup generated by this element represents the behaviour on strings in x +. The main contribution of this paper is a description of all such monogenic subsemigroups up to isomorphism. This characterization is then used to show that transforming an n-state 2DFA over a one-letter alphabet to an equivalent sweeping 2DFA requires exactly n+1 states, and transforming it to a one-way automaton requires exactly states, where G(k) is the maximum order of a permutation of k elements.
| Язык оригинала | английский |
|---|---|
| Название основной публикации | Developments in Language Theory - 15th International Conference, DLT 2011, Proceedings |
| Страницы | 324-336 |
| Число страниц | 13 |
| DOI | |
| Состояние | Опубликовано - 29 июл 2011 |
| Событие | 15th International Conference on Developments in Language Theory, DLT 2011 - Milan, Италия Продолжительность: 19 июл 2011 → 22 июл 2011 |
| Название | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Том | 6795 LNCS |
| ISSN (печатное издание) | 0302-9743 |
| ISSN (электронное издание) | 1611-3349 |
| конференция | 15th International Conference on Developments in Language Theory, DLT 2011 |
|---|---|
| Страна/Tерритория | Италия |
| Город | Milan |
| Период | 19/07/11 → 22/07/11 |
ID: 41142716