1,2

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). Sequence data is from exhaustive search. The NFAs for n=1,2,4,5 are unique; for n=3,6,7 they are not. a(8) <= 28, a(9) <= 34, a(10) <= 41 by heuristic construction.

Schnitger improved 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).

Russ Cox, Graph of the minimal NFAs for n=1..7.

Russ Cox, C program

J. Hromkovic, S. Siebert, 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.

C program: see link.

Sequence in context: A004131 A032782 A076523 this_sequence A092847 A005488 A048202

Adjacent sequences: A129400 A129401 A129402 this_sequence A129404 A129405 A129406

hard,more,nonn

Russ Cox (rsc(AT)swtch.com), Apr 13 2007