DOI

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.
Язык оригиналаанглийский
Название основной публикацииDevelopments in Language Theory
Подзаголовок основной публикации29th International Conference, DLT 2025, Seoul, South Korea, August 19–22, 2025, Proceedings
РедакторыSang-Ki Ko, Florin Manea
ИздательSpringer Nature
Страницы107–122
Число страниц16
ISBN (печатное издание)9783032014740
DOI
СостояниеОпубликовано - 16 авг 2025
СобытиеDevelopments in Language Theory - Сеул, Республика Корея
Продолжительность: 19 авг 202522 авг 2025
Номер конференции: 29
https://cida.uos.ac.kr/dlt2025/

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

НазваниеLecture Notes in Computer Science
Том16036 LNCS

конференция

конференцияDevelopments in Language Theory
Сокращенное названиеDLT 2025
Страна/TерриторияРеспублика Корея
ГородСеул
Период19/08/2522/08/25
Сайт в сети Internet

ID: 140132196