%I #29 Sep 12 2024 14:39:37
%S 1,3,6,9,13,18,23,28,33,39,46,53
%N Minimal number of edges in e-free non-deterministic finite automata (NFA) for regular expression c_1?c_2?...c_n?.
%C Also minimal number of edges in dag on n+1 nodes with integer-labeled edges such that every subsequence of 1,2,...,n matches the edge labels on a path starting at the root of the dag and vice versa. Maximal number of distinct edges in the dag is A000292(n). Hromkovic et al. showed lower bound of Theta(n log n) and upper bound of O(n log^2 n). Lifshits improved lower bound of Theta(n log^2 n / log log n).
%C Schnitger improved the lower bound to Theta(n log^2 k) for regular expressions of length n over alphabets of size k, so A129403(n) is asymptotically O(n log^2 n).
%C The method of el Abdalaoui et al. produces minimal NFAs for the sizes for which a(n) is known; the method also implies a(13) <= 60, a(14) <= 67. It is not known whether the method always produces minimal NFAs.
%C Sequence data is from exhaustive search. The NFAs for n=1,2,4,5,9 are unique; for n=3,6,7,8 they are not. a(8)-a(9) added Mar 05 2013. a(10)-a(12) added Oct 05 2014.
%H Russ Cox, Graph of the minimal NFAs for n=1..7. <a href="/A129403/a129403.pdf">PDF</a> <a href="/A129403/a129403.png">PNG</a>
%H Russ Cox, <a href="/A129403/a129403.c.txt">C program</a>
%H el Houcein el Abdalaoui, Mohamed Dahmoune, and Djelloul Ziadi, <a href="http://arxiv.org/abs/1301.3751">On the transition reduction problem for finite automata</a>, arXiv:1301.3751 [cs.FL], 2013.
%H J. Hromkovic, S. Siebert, and Th. Wilke, <a href="http://dx.doi.org/10.1006/jcss.2001.1748">Translating regular expressions into small e-free nondeterministic finite automata</a>, J. Computer and System Sciences 62(4) (2001) 565-588.
%H Y. Lifshits, <a href="http://dx.doi.org/10.1016/S0020-0190(02)00436-2">A lower bound on the size of e-free NFA corresponding to a regular expression</a>, Information Processing Letters 85 (2003) 293-299.
%H G. Schnitger, <a href="http://dx.doi.org/10.1007/11672142_35">Regular Expressions and NFAs Without e-Transitions</a>, in STACS 2006, 432-443.
%o (C) // See link.
%K hard,more,nonn
%O 1,2
%A _Russ Cox_, Apr 13 2007