# -------------------------------------------------------------- # Number of transitions in the Glushkov automaton # -------------------------------------------------------------- restart: # # foo = sqrtD || sqDt(k,z) ; sqrtD is used for formal computations, while sqDt(k,z) is used for numerical computations ro:= k -> 1/(1+sqrt(8*k+8)): # # the dominant root of R(z), which is one of the roots of Dt Dt:= (k,z) -> 1-2*z-(7+8*k)*z^2: # # the discriminant that shows up almost everywhere... sqDt:= (k,z) -> sqrt(Dt(k,z)): # # and its square root... R:= (k,z,foo) -> (1-z-foo)/(4*z): # # cost generating function for regular expressions = generating function for the number of regular expressions of a given size Reps:= (k,z,foo) -> (z+z*R(k,z,foo))/(1-2*z*R(k,z,foo)): # # cost generating function for regular expressions that contain epsilon in their language F := (k,z,foo) -> (k*z)/(1-z-3*z*R(k,z,foo)-z*Reps(k,z,foo)): # # cost generating function for the set First for regular expressions Lambda:= (k,z,foo) -> 1-z-2*z*Reps(k,z,foo)-2*z*R(k,z,foo): # # intermediate function (see report, p. ) Rnoeps := (k,z,foo) -> R(k,z,foo) - Reps(k,z,foo): # # cost generating function for regular expressions that contain epsilon in their language Enumer := (k,z,foo) -> k*z^2+z*F(k,z,foo)^2*Lambda(k,z,foo)+4*z^2*F(k,z,foo)^2: # # numerator for the "follow part" in Eglush Edenom := (k,z,foo) -> (1-4*z*R(k,z,foo))*Lambda(k,z,foo)-2*z^2*Rnoeps(k,z,foo): # # denominator for the "follow part" in Eglush Eglush := (k,z,foo) -> F(k,z,foo)+ Enumer(k,z,foo)/Edenom(k,z,foo): # # cost generating function for the edges of the Glushkov automaton simplify(Eglush(k,z,D)): # # Just in case you really want to see it (we advise you not to...) numGlush1 := (k,z,D) -> simplify(numer(Eglush(k,z,D))): numGlush1(k,z,D);# # Here we discovered that the denominator is divisible by z. numGlush1 := (k,z,D) -> simplify(numer(Eglush(k,z,D))/z): numGlush := (k1,z1,D1) -> algsubs(k=k1,algsubs(z=z1,algsubs(D=D1,numGlush1(k,z,D)))): # # This serves to effectively eliminate the use of denominators in intermediate computations, which numGlush1 uses. This way we avoid some annoying divisions by zero... denomGlush1 := (k,z,D) -> denom(Eglush(k,z,D)): denomGlush1(k,z,D); # # Here we discovered that the denominator is divisible by zD. denomGlush2 := (k,z,D) -> simplify(denomGlush1(k,z,D)/(D*z)): denomGlush1(k,z,D); denomGlush := (k1,z1,D1) -> algsubs(k=k1,algsubs(z=z1,algsubs(D=D1,denomGlush2(k,z,D)))): numGlush(k,z,0); denomGlush(k,z,0); P:=(k,z,D)->numGlush(k,z,D)/(1+z+D): # # cf. section 4.1 of report Q:=(k,z,D)->denomGlush(k,z,D)/(1+z+D): P(k,z,D); Q(k,z,D); # Using the fact that D^(2)=1-2 z -(7+ 8 k) z^(2);, one obtains # # 2 D-5 z^2+1+4 z D+D^2; = (1-5*z^2;) + 2 D+4 z D+D^2; = (2 z + 2 z^2; + 8 k z^2; + D^2; ) + 2 D+4 z D+D^2; # # = (1-5*z^2;) + 2 (1+ 2 z) D+D^2 = (D+1+2 z)^( 2) - 4 z - 9 z^( 2) = (D+1+2 z)^( 2) - z (4 + 9 z^()); # # 1-2 z+4 D-7 z^2+4 z D+3 D^2; = (1-2 z-7 z^2)+ 4 D + 4 z D+3 D^2 = (8 k z^2 + D^2 ) + 4 D + 4 z D+3 D^2; # # = 4 D^2 + 4 (1 + z) D + 8 k z^2 = 4 ;( D^2 + (1 + z) D + 2 k z^2); # # This shows that the Q(z) has no roots in [0,ro[k];]. collect(P(k,z,D)/(2*k*z*(1+z+D)),D); numGlush(k,r,0)/(1+r); # # It was found that both of these were divisible by (1+ro(k)) (here r represents ro(k)). Note that D(ro(k)) = 0. denomGlush(k,r,0)/(1+r); algsubs(1-2*r-7*r^2=8*k*r^2,-2*r-7*r^2+1); # Using the fact that 1-2*r-7*r^2 = 8*kr^2;, one obtains that (see also computations immediately below): # # (8*r^5+56*r^4+56*r^3+8*r^2)*k = 8*k*r(r^3+7*r^2+7*r+1)^2;=8*k*r^2;(1+r)*(r^2+6*r+1); # 28*r^4+49*r^5+r-10*r^3-4*r^2;=r*(2*r+7*r^2-1)^2 = 64*k^2*r^5; # # And so numGlush(k,r,0)=2 r^()(1+r)k(64 k^(2)r^(5)+;8*k*r^2;(1+r) (r^2+6 r+1)) = 16 k^(2) r^(3)(1+r)(r^3+8 r^3 k+7 r^2+7 r+1). But r^3+8 r^3 k+7 r^2+7 r+1= r^3+r (1-2 r-7 r^2)+7 r^2+7 r+1 = 1+8 r+5 r^2-6 r^3; # # while denomGlush(k, r, 0) = 64*k^2*r(1-5*r^2)^4; # # Therefore*numGlush(k, r, 0)/denomGlush(k, r, 0) = (1+r)(1+8*r+5*r^2-6*r^3)/(4*r(1-5*r^2)); # factor(r^3+7*r^2+7*r+1); factor(28*r^4+49*r^5+r-10*r^3-4*r^2); factor(64*k^2*r^5+8*k*r^2*(1+r)*(r^2+6*r+1)); factor(r^3+r*(-2*r-7*r^2+1)+7*r^2+7*r+1); # Of course all of this is done automatically by the following functions... numerGlushk := k -> numGlush(k,ro(k),0): # # the numerator and denominator computed at the singularity... denomGlushk := k -> denomGlush(k,ro(k),0): TransitionsGlushkov := (k,n) -> numerGlushk(k)/(denomGlushk(k)*sqrt(2-2*ro(k))*sqrt(Pi))*ro(k)^(-n)*n^(-1/2): # # assymptotic approximation for the lower bound we have computed for the number os transitions in the Glushkov automata evalf(TransitionsGlushkov(2,4)); # # just an example... kk := 30: # # here we kindly ask Maple to compute the exact series for us... sGlush:= series(Eglush(kk,z,sqDt(kk,z)),z,300): for i from 290 to 298 do # # here we compare the approximation we have obtained with the exact values... printf("%A\t%A\t%A\n",i,evalf(TransitionsGlushkov(kk,i)), evalf(TransitionsGlushkov(kk,i)/coeff(sGlush,z,i))): od: # --------------------------------------------------------------------------- # Number of identifications for transitions in the PD automaton # --------------------------------------------------------------------------- # # bar ---> dummy or bigSQ (formal and numerical, respectively) bigSQ := (k,z,foo) -> sqrt((z^2+3*z*R(k,z,foo)-1)^2 + 4*k*z^2); # # a square root that shows up in the cost g.f of Rpieps Rpieps := (k,z,foo,bar) -> ((z^2+3*z*R(k,z,foo) -1) + bar)/(2*z): # # the cost g.f. of the r.e. that have epsilon in the Mirkin base # This last expression shows that bigSQ has no real singularity in [0 , ro]... Rreps := (k,z,foo,bar) -> (z*Rpieps(k,z,foo,bar))/(1-z*Reps(k,z,foo)): # # See \ref{rreps} in report Il := (k, z, foo,bar) -> (z*Rpieps(k, z, foo,bar)^2+z*Rpieps(k,z,foo,bar)*Rreps(k,z,foo,bar))/(1-3*z*R(k, z,foo)-z-z*Reps(k,z,foo)); # # cost g.f. for a lower bound of the number of mergings of states in the set Last It := (k,z,foo,bar) -> (z*Lambda(k,z,foo)*Il(k,z,foo,bar)*F(k,z,foo)+k*z^2+4*z^2*Il(k,z,foo,bar)*F(k,z,foo))/(Lambda(k,z,foo)-4*z*R(k,z,foo)*Lambda(k,z,foo)-2*z^2*Rnoeps(k,z,foo)); # # cost g.f. for a lower bound of transition mergings in the Glushkov automata that arise when one computes the PD automata numerIt1:= (k,z) -> numer(simplify(It(k,z,D,E))): # # Numerator of It, but still with implicit denominators, not suited for direct computations... denomIt1:= (k,z) -> denom(simplify(It(k,z,D,E))): # # Denomirator of It, but still with implicit denominators, not suited for direct computations... numerIt:= (k,z) -> algsubs(E=bigSQ(k,z,0),algsubs(D=0,numerIt1(k,z))): # # The real numerator of It... numerIt2:= (k,z,E) -> algsubs(D=0,numerIt1(k,z)): # # Another version of the real numerator of It... denomIt:= (k,z) -> algsubs(D=0,denomIt1(k,z)/D): # # The real denominator of It, after removing the factor D... IdentificationsPD := (k,n) -> numerIt(k,ro(k))/(denomIt(k,ro(k))*sqrt(2-2*ro(k))*sqrt(Pi))*ro(k)^(-n)*n^(-1/2): # # the asymptotic approximations for the lower bound of the number of identifications of transitions from Glushkov to PD automaton # # The following computations were used to write It(z) and the respective assymptotic aproximations on the paper and in the report. denomIt1(k,z); denomIt(k,z); numerIt1(k,z): # The first two factors of the denominator of It(z) are the same of Q(z), and we have already shown that they are positive in the interval [0 , ro]. # # Using again the fact that D^(2)=1-2 z -(7+ 8 k) z^(2);, one obtains # # 2+z+2*D-3*z^2+z*D; = (1-3 z^2; ) + 1+z+2 D+z D = (2 z + 4 z^(2) + 8 k z^(2) + D^( 2) )+ 1+z+2 D+z D; # # = (2 + z) (D+1) - 3*z^2; # # which is also positive in [0 , ro]. This shows that the radius of convergence of It(z) is still "ro". numerIt2(k,z,E); # # Study of the long factor numerator of It(k,z) lfnumer:=numerIt2(k,z,E)/(z*k*(1+z)): # # removing the small factors of the numerator c1:=coeff(algsubs(E^2=(z^2+3*z*R(k,z,0)-1)^2 + 4*k*z^2,lfnumer),E,0): sort(c1,[z],ascending); a1:=coeff(algsubs(E^2=(z^2+3*z*R(k,z,0)-1)^2 + 4*k*z^2,lfnumer),E,1): sort(a1,[z],ascending); a:=a1/8: sort(a,[z],ascending); b1:=algsubs(8*k*z^2=1-2*z-7*z^2,bigSQ(k,z,0)^2): b:=b1*16: sort(b,[z],ascending); c2:=algsubs(8*k*z^2=1-2*z-7*z^2,c1): c:=c2/2: sort(c,[z],ascending); # Therefore, the numerator is equal to k z(1+z)(a[1] sqrt(b[1])+c[1])=k z(1+z)(8 a sqrt(b/(16))+2 c)= = 2 k z(1+z)(a sqrt(b)+c) ; # Obs: In the paper we denote by b; what is here sqrt(b);... # Now, the denominator is 4 (-5 z^2+1) (1-2 z-7 z^2)^2 (2+z-3 z^2),as shown above, and in order to obtain the expression on the paper, one transforms one of the factors (1-2 z-7 z^2) into 8 k z^(2), which transforms that denominator into ; # 32*k*z(1-5*z^2)^2*(1-2*z-7*z^2)(2+z-3*z^2);. # # Obs: z here really stands for ro(k)... kk := 30: # # here we kindly ask Maple to compute the exact series for us... sIt:= series(It(kk,z,sqDt(kk,z),bigSQ(kk,z,sqDt(kk,z))),z,300): for i from 280 to 290 do # # here we compare the approximation we have obtained with the exact values... printf("%A\t%A\t%A\n",i,evalf(IdentificationsPD(kk,i)), evalf(IdentificationsPD(kk,i)/coeff(sIt,z,i))): od: # # lower bound for the average number of mergings per transition of the Glushkov automaton... avIdG := (k,n) -> IdentificationsPD(k,n)/TransitionsGlushkov(k,n): evalf(avIdG(10,70000)); # # some limits... evalf(limit(avIdG(10000000000,kj),kj=infinity)); evalf(limit(avIdG(10,nj),nj=infinity)); # Support computations to prove that the denominator of Eglush, Q(z), and the denominator of It(z) have no zeros in the critical circle... for k from 1 while evalf(1/4-5/2*ro(k)-7/4*ro(k)^2)<0 do NULL od: print(k,evalf(1/4-5/2*ro(k)-7/4*ro(k)^2)): for k from 1 while evalf(1/2-4*ro(k)-5/2*ro(k)^2)<0 do NULL od: print(k,evalf(1/2-4*ro(k)-5/2*ro(k)^2)): # Ensuring that the denominators of Glush(z) and It(z) do not have zeros on the boundary of the disc of convergence, besides rho... # # The functions that show up in the denominators... F1Denom:= (k,z) -> (z+2)*(sqDt(k,z)+1)-3*z^2: F2Denom:= (k,z)-> 1-5*z^2+2*(1+2*z)*sqDt(k,z)+Dt(k,z): F3Denom:= (k,z) -> (1-2*z-7*z^2) + 4* (1+z)*sqDt(k,z)+3*Dt(k,z): # # Image of the circle |z| = ro(k) by the above function and by sqDt(k,z)... kk:=1: angle:=2*Pi: plot([[Re(F1Denom(kk,ro(kk)*exp(I*t))),Im(F1Denom(kk,ro(kk)*exp(I*t))),t=0..angle], [Re(F2Denom(kk,ro(kk)*exp(I*t))),Im(F2Denom(kk,ro(kk)*exp(I*t))),t=0..angle], [Re(F3Denom(kk,ro(kk)*exp(I*t))),Im(F3Denom(kk,ro(kk)*exp(I*t))),t=0..angle], [Re(sqDt(kk,ro(kk)*exp(I*t))),Im(sqDt(kk,ro(kk)*exp(I*t))),t=0..angle]],color=[red,blue,green,black]);