login
A129403
Minimal number of edges in e-free non-deterministic finite automata (NFA) for regular expression c_1?c_2?...c_n?.
1
1, 3, 6, 9, 13, 18, 23, 28, 33, 39, 46, 53
OFFSET
1,2
COMMENTS
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).
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).
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.
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.
LINKS
Russ Cox, Graph of the minimal NFAs for n=1..7. PDF PNG
Russ Cox, C program
el Houcein el Abdalaoui, Mohamed Dahmoune, and Djelloul Ziadi, On the transition reduction problem for finite automata, arXiv:1301.3751 [cs.FL], 2013.
J. Hromkovic, S. Siebert, and Th. Wilke, Translating regular expressions into small e-free nondeterministic finite automata, J. Computer and System Sciences 62(4) (2001) 565-588.
Y. Lifshits, A lower bound on the size of e-free NFA corresponding to a regular expression, Information Processing Letters 85 (2003) 293-299.
G. Schnitger, Regular Expressions and NFAs Without e-Transitions, in STACS 2006, 432-443.
PROG
(C) // See link.
CROSSREFS
Sequence in context: A076523 A310159 A282720 * A323622 A154287 A092847
KEYWORD
hard,more,nonn
AUTHOR
Russ Cox, Apr 13 2007
STATUS
approved