Describing periodicity in two-way deterministic finite automata using transformation semigroups

Michal Kunc, Alexander Okhotin

Результат исследований: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференции

20 Цитирования (Scopus)

Аннотация

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 июл 201122 июл 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
СтранаИталия
ГородMilan
Период19/07/1122/07/11

Предметные области Scopus

  • Теоретические компьютерные науки
  • Компьютерные науки (все)

Fingerprint Подробные сведения о темах исследования «Describing periodicity in two-way deterministic finite automata using transformation semigroups». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать