Search: id:A129403
Results 1-1 of 1 results found.

%I A129403
%S A129403 1,3,6,9,13,18,23
%N A129403 Minimal number of edges in e-free non-deterministic finite automata (NFA) 
               for regular expression c_1?c_2?...c_n?.
%C A129403 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.
%C A129403 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).
%H A129403 Russ Cox, <a href="a129403.pdf">Graph of the minimal NFAs for n=1..7.</
               a>
%H A129403 Russ Cox, <a href="a129403.c.txt">C program</a>
%H A129403 J. Hromkovic, S. Siebert, 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 A129403 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 A129403 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 A129403 C program: see link.
%Y A129403 Sequence in context: A004131 A032782 A076523 this_sequence A154287 A092847 
               A143975
%Y A129403 Adjacent sequences: A129400 A129401 A129402 this_sequence A129404 A129405 
               A129406
%K A129403 hard,more,nonn
%O A129403 1,2
%A A129403 Russ Cox (rsc(AT)swtch.com), Apr 13 2007

Search completed in 0.001 seconds