Abstract

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

Original languageEnglish
Pages (from-to)315-331
Number of pages17
JournalFundamenta Informaticae
Volume180
Issue number4
DOIs
StatePublished - Jul 2021

Scopus subject areas

  • Theoretical Computer Science
  • Algebra and Number Theory
  • Information Systems
  • Computational Theory and Mathematics

Keywords

  • Finite automata
  • shortest string
  • state complexity
  • two-way automata

Fingerprint

Dive into the research topics of 'On the Length of Shortest Strings Accepted by Two-way Finite Automata'. Together they form a unique fingerprint.

Cite this