DOI

The paper estimates the number of states in an unambiguous finite automaton (UFA) that is sufficient and in the worst case necessary to simulate an n-state two-way deterministic finite automaton (2DFA). It is proved that a 2DFA with n states can be transformed to a UFA with fewer than 2n· n! states. On the other hand, for every n, there is a language recognized by an n-state 2DFA that requires a UFA with at least Ω((42)n·n-1/2) states. The latter result is proved by estimating the rank of a certain matrix.

Язык оригиналаанглийский
Название основной публикацииLanguage and Automata Theory and Applications - 15th International Conference, LATA 2021, Proceedings
РедакторыAlberto Leporati, Carlos Martín-Vide, Dana Shapira, Claudio Zandron
ИздательSpringer Nature
Страницы81-93
Число страниц13
ISBN (печатное издание)9783030681944
DOI
СостояниеОпубликовано - фев 2021
Событие15th International Conference on Language and Automata Theory and Applications, LATA 2021 - Milan, Италия
Продолжительность: 1 мар 20215 мар 2021

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

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

конференция

конференция15th International Conference on Language and Automata Theory and Applications, LATA 2021
Страна/TерриторияИталия
ГородMilan
Период1/03/215/03/21

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

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

ID: 78911685