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).

Original languageEnglish
Title of host publicationDescriptional Complexity of Formal Systems - 23rd IFIP WG 1.02 International Conference, DCFS 2021, Proceedings
EditorsYo-Sub Han, Sang-Ki Ko
PublisherSpringer Nature
Pages26-37
Number of pages12
ISBN (Print)9783030934880
DOIs
StatePublished - 30 Dec 2021
Event23rd IFIP WG 1.02 International Conference on Descriptional Complexity of Format Systems, DCFS 2021 - Virtual, Online
Duration: 5 Sep 20215 Sep 2021

Publication series

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

Conference

Conference23rd IFIP WG 1.02 International Conference on Descriptional Complexity of Format Systems, DCFS 2021
CityVirtual, Online
Period5/09/215/09/21

    Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

    Research areas

  • Finite automata, State complexity, Two-way automata

ID: 91382899