On the Length of Shortest Strings Accepted by Two-way Finite Automata

Результат исследований: Научные публикации в периодических изданияхстатьярецензирование

Аннотация

Given a two-way finite automaton recognizing a non-empty language, consider the length of the shortest string it accepts, and, for each n ≥ 1, let f(n) be the maximum of these lengths over all n-state automata. It is proved that for n-state two-way finite automata, whether deterministic or nondeterministic, this number is at least Ω(10n/5) and less than (2nn+1), with the lower bound reached over an alphabet of size Θ(n). Furthermore, for deterministic automata and for a fixed alphabet of size m ≥ 1, the length of the shortest string is at least e(1+o(1))mn(log n- log m).

Язык оригиналаанглийский
Страницы (с-по)315-331
Число страниц17
ЖурналFundamenta Informaticae
Том180
Номер выпуска4
DOI
СостояниеОпубликовано - июл 2021

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

  • Теоретические компьютерные науки
  • Алгебра и теория чисел
  • Информационные системы
  • Математика и теория расчета

Fingerprint

Подробные сведения о темах исследования «On the Length of Shortest Strings Accepted by Two-way Finite Automata». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать