A129403 Minimal number of edges in e-free non-deterministic finite automata (NFA) for regular expression c_1?c_2?...c_n?.

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

Table of n, a(n) for n=1..12.

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 program: see link.

Crossrefs

Sequence in context: A076523 A310159 A282720 * A323622 A154287 A092847

Adjacent sequences: A129400 A129401 A129402 * A129404 A129405 A129406

Keyword

hard,more,nonn

Author

Russ Cox, Apr 13 2007

Status

approved