notesum.ai

Published at December 9

A lower bound on the state complexity of transforming two-way nondeterministic finite automata to unambiguous finite automata

cs.FL

68Q45

Released Date: December 9, 2024

Authors: Semyon Petrov¹, Alexander Okhotin¹

Aff.: ¹St. Petersburg State University

Arxiv: http://arxiv.org/pdf/2412.06283v1

Refer to caption

$n$	2DFA $\to$ UFA	2DFA $\to$ UFA	2NFA $\to$ UFA	2NFA $\to$ DFA
	2UFA $\to$ UFA	2UFA $\to$ UFA	(lower bound)
	(lower bound)	(upper bound)
	$\sum\limits_{k=1}^{n}{n\choose k-1}{n\choose k}{2k-2\choose k-1}$	$\sum\limits_{k=1}^{n}{n\choose k-1}{n\choose k}k!$	$\sum\limits_{k=1}^{n}(k-1)!k!\genfrac{\{}{\}}{0.0pt}{}{n}{k}\genfrac{\{}{\}}{0% .0pt}{}{n+1}{k}$	$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}{n\choose i}{n\choose j}(2^{n-i}-1)^% {n-j}$
1	1	1	1	1
2	6	6	7	7
3	39	39	115	133
4	276	292	3 451	7 891
5	2 055	2 505	164 731	1 613 581
6	15 798	24 306	11 467 387	1 201 168 507
7	124 173	263 431	1 096 832 395	3 360 710 751 133
8	992 232	3 154 824	138 027 417 451	36 005 748 492 454 531