|
Search: id:A129403
|
|
|
| A129403 |
|
Minimal number of edges in e-free non-deterministic finite automata (NFA) for regular expression c_1?c_2?...c_n?. |
|
+0
1
|
| |
|
|
OFFSET
|
1,2
|
|
|
COMMENT
|
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 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).
|
|
LINKS
|
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.
|
|
PROGRAM
|
C program: see link.
|
|
CROSSREFS
|
Sequence in context: A171514 A032782 A076523 this_sequence A154287 A092847 A143975
Adjacent sequences: A129400 A129401 A129402 this_sequence A129404 A129405 A129406
|
|
KEYWORD
|
hard,more,nonn
|
|
AUTHOR
|
Russ Cox (rsc(AT)swtch.com), Apr 13 2007
|
|
|
Search completed in 0.002 seconds
|
