DOI

In a recent paper, Dobronravov et al. (“On the length of shortest strings accepted by two-way finite automata”, DLT 2019) prove that the shortest string in a language recognized by an n-state two-way finite automaton (2DFA) can be at least symbols long, improved to in their latest contribution. The lower bound was obtained using “direction-determinate” 2DFA, which always remember their direction of motion at the last step, and used an alphabet of size In this paper, the method of Dobronravov et al. is extended to a new, more general class: the semi-direction-determinate 2DFA. This yields n-state 2DFA with shortest strings of length Furthermore, the construction is adapted to use a fixed alphabet, resulting in shortest strings of length It is also shown that an n-state semi-direction-determinate 2DFA can be transformed to a one-way NFA with states.

Язык оригиналаанглийский
Название основной публикацииDescriptional Complexity of Formal Systems - 22nd International Conference, 2020, Proceedings
РедакторыGalina Jirásková, Giovanni Pighizzini
ИздательSpringer Nature
Страницы104-116
Число страниц13
ISBN (печатное издание)9783030625351
DOI
СостояниеОпубликовано - 2020
Событие22nd International Conference on Descriptional Complexity of Format Systems, DCFS 2020 - Vienna, Австрия
Продолжительность: 24 авг 202026 авг 2020

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

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

конференция

конференция22nd International Conference on Descriptional Complexity of Format Systems, DCFS 2020
Страна/TерриторияАвстрия
ГородVienna
Период24/08/2026/08/20

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

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

ID: 72034528