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

Michal Kunc, Alexander Okhotin

Research output

20 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationDevelopments in Language Theory - 15th International Conference, DLT 2011, Proceedings
Pages324-336
Number of pages13
DOIs
Publication statusPublished - 29 Jul 2011
Event15th International Conference on Developments in Language Theory, DLT 2011 - Milan
Duration: 19 Jul 201122 Jul 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6795 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference15th International Conference on Developments in Language Theory, DLT 2011
CountryItaly
CityMilan
Period19/07/1122/07/11

Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Describing periodicity in two-way deterministic finite automata using transformation semigroups'. Together they form a unique fingerprint.

Cite this