This paper establishes a lower bound on the number of states necessary in the worst case to simulate an n-state two-way nondeterministic finite automaton (2NFA) by a one-way unambiguous finite automaton (UFA). It is proved that for every n, there is a language recognized by an n-state 2NFA that requires a UFA with at least ∑k=1n(k-1)!k!nkn+1k = Ω(n2n+2/e2n) states, where nk denotes Stirling’s numbers of the second kind. This result is proved by estimating the rank of a certain matrix, which describes every possible behaviour of n-state 2NFAs during their computation.
Original languageEnglish
Title of host publicationDevelopments in Language Theory
Subtitle of host publication29th International Conference, DLT 2025, Seoul, South Korea, August 19–22, 2025, Proceedings
EditorsSang-Ki Ko, Florin Manea
PublisherSpringer Nature
Pages107–122
Number of pages16
ISBN (Print)9783032014740
DOIs
StatePublished - 16 Aug 2025
EventDevelopments in Language Theory - Сеул, Korea, Republic of
Duration: 19 Aug 202522 Aug 2025
Conference number: 29
https://cida.uos.ac.kr/dlt2025/

Publication series

NameLecture Notes in Computer Science
Volume16036 LNCS

Conference

ConferenceDevelopments in Language Theory
Abbreviated titleDLT 2025
Country/TerritoryKorea, Republic of
CityСеул
Period19/08/2522/08/25
Internet address

    Research areas

  • Two-way finite automata, state complexity, unambiguous finite automata

ID: 140132196