DOI

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

Язык оригиналаанглийский
Название основной публикацииDescriptional Complexity of Formal Systems - 23rd IFIP WG 1.02 International Conference, DCFS 2021, Proceedings
РедакторыYo-Sub Han, Sang-Ki Ko
ИздательSpringer Nature
Страницы26-37
Число страниц12
ISBN (печатное издание)9783030934880
DOI
СостояниеОпубликовано - 30 дек 2021
Событие23rd IFIP WG 1.02 International Conference on Descriptional Complexity of Format Systems, DCFS 2021 - Virtual, Online
Продолжительность: 5 сен 20215 сен 2021

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том13037 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

конференция

конференция23rd IFIP WG 1.02 International Conference on Descriptional Complexity of Format Systems, DCFS 2021
ГородVirtual, Online
Период5/09/215/09/21

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

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

ID: 91382899