Tail asymptotics for the fundamental period in the MAP/G/1 queue

This paper studies the tail behavior of the fundamental period in the MAP/G/1 queue. We prove that if the service time distribution has a regularly varying tail, then the fundamental period distribution in the MAP/G/1 queue has also regularly varying tail, and vice versa, by finding an explicit expression for the asymptotics of the tail of the fundamental period in terms of the tail of the service time distribution. Our main result with the matrix analytic proof is a natural extension of the result in (de Meyer and Teugels, J. Appl. Probab. 17: 802–813, 1980) on the M/G/1 queue where techniques rely heavily on analytic expressions of relevant functions. I.-S. Wee’s research was supported by the Korea Research Foundation Grant KRF 2003-070-00008.     

Regular Cayley maps for finite abelian groups

A regular Cayley map for a finite group A is an orientable map whose orientation-preserving automorphism group G acts regularly on the directed edge set and has a subgroup isomorphic to A that acts regularly on the vertex set. This paper considers the problem of determining which abelian groups have regular Cayley maps. The analysis is purely algebraic, involving the structure of the canonical form for A. The case when A is normal in G involves the relationship between the rank of A and the exponent of the automorphism group of A, and the general case uses Ito's theorem to analyze the factorization G = AY, where Y is the (cyclic) stabilizer of a vertex. Supported in part by the N.Z. Marsden Fund (grant no. UOA0124).     

The automorphism group of Payne derived generalized quadrangles

We solve a long-standing open problem by proving that the automorphism group of any thick Payne derived generalized quadrangle with ambient quadrangle S a thick generalized quadrangle of order s, s?5 and odd, with a center of symmetry, is induced by the automorphism group of S.     

A linear approximation for the regular reflection of a weak shock at a wedge satisfying sonic condition

The problem of shock reflection by a wedge, which the flow is dominated by the unsteady potential flow equation, is a important problem. In weak regular reflection, the flow behind the reflected shock is immediately supersonic and becomes subsonic further downstream. The reflected shock is transonic. Its position is a free boundary for the unsteady potential equation, which is degenerate at the sonic line in self-similar coordinates. Applying the special partial hodograph transformation used in [Zhouping Xin, Huicheng Yin, Transonic shock in a nozzle I, 2-D case, Comm. Pure Appl. Math. 57 (2004) 1-51; Zhouping Xin, Huicheng Yin, Transonic shock in a nozzle II, 3-D case, IMS, preprint (2003)], we derive a nonlinear degenerate elliptic equation with nonlinear boundary conditions in a piecewise smooth domain. When the angle, which between incident shock and wedge, is small, we can see that weak regular reflection as the disturbance of normal reflection as in [Shuxing Chen, Linear approximation of shock reflection at a wedge with large angle, Comm. Partial Differential Equations 21 (78) (1996) 1103-1118]. By linearizing the resulted nonlinear equation and boundary conditions with above viewpoint, we obtain a linear degenerate elliptic equation with mixed boundary conditions and a linear degenerate elliptic equation with oblique boundary conditions in a curved quadrilateral domain. By means of elliptic regularization techniques, delicate a priori estimate and compact arguments, we show that the solution of linearized problem with oblique boundary conditions is smooth in the interior and Lipschitz continuous up to the degenerate boundary.     

On circle diffeomorphisms with discontinuous derivatives and quasi-invariance subgroups of Malliavin-Shavgulidze measures

This note is devoted to construction of the domain of the regular representation of Diff₊(S¹). We consider a subgroup of diffeomorphism group such that the Malliavin-Shavgulidze measure is quasi-invariant with respect to the left action of the subgroup. The measure appears to be quasi-invariant with respect to the left action of diffeomorphisms with discontinuous second derivative. We derive an expression for quasi-invariance density and obtain an additional PSL(2,R) symmetry breaking term.     

Clustering of spectra and fractals of regular graphs

We exhibit a characteristic structure of the class of all regular graphs of degree d that stems from the spectra of their adjacency matrices. The structure has a fractal threadlike appearance. Points with coordinates given by the mean and variance of the exponentials of graph eigenvalues cluster around a line segment that we call a filar. Zooming-in reveals that this cluster splits into smaller segments (filars) labeled by the number of triangles in graphs. Further zooming-in shows that the smaller filars split into subfilars labeled by the number of quadrangles in graphs, etc. We call this fractal structure, discovered in a numerical experiment, a multifilar structure. We also provide a mathematical explanation of this phenomenon based on the Ihara-Selberg trace formula, and compute the coordinates and slopes of all filars in terms of Bessel functions of the first kind.     

Regular expression constrained sequence alignment

We introduce regular expression constrained sequence alignment as the problem of finding the maximum alignment score between given strings $S_1$ and $S_2$ over all alignments such that in these alignments there exists a segment where some substring $s_1$ of $S_1$ is aligned to some substring $s_2$ of $S_2$, and both $s_1$ and $s_2$ match a given regular expression R, i.e. $s_1,s_2\in L(R)$ where $L(R)$ is the regular language described by R. For complexity results we assume, without loss of generality, that $n=|S_1|⩾|m|=|S_2|$. A motivation for the problem is that protein sequences can be aligned in a way that known motifs guide the alignments. We present an $\mathrm{O}(nmr)$ time algorithm for the regular expression constrained sequence alignment problem where $r=\mathrm{O}(t^4)$, and t is the number of states of a nondeterministic finite automaton N that accepts $L(R)$. We use in our algorithm a nondeterministic weighted finite automaton M that we construct from N. M has $\mathrm{O}(t^2)$ states where the transition-weights are obtained from the given costs of edit operations, and state-weights correspond to optimum alignment scores we compute using the underlying dynamic programming solution for sequence alignment. If we are given a deterministic finite automaton D accepting $L(R)$ with $t_d$ states then our construction creates a deterministic finite automaton $M_d$ with $t_d^2$ states. In this case, our algorithm takes $\mathrm{O}(t_d^{2}nm)$ time. Using $M_d$ results in faster computation than using M when $t_d<t^2$. If we only want to compute the optimum score, the space required by our algorithm is $\mathrm{O}(t^{2}n)$ ($\mathrm{O}(t_d^{2}m)$ if we use a given $M_d$). If we also want to compute an optimal alignment then our algorithm uses $\mathrm{O}(t^{2}m+t^2|s_1||s_2|)$ space ($\mathrm{O}(t_d^{2}m+t_d^2|s_1||s_2|)$ space if we use a given $M_d$) where $s_1$ and $s_2$ are substrings of $S_1$ and $S_2$, respectively, $s_1,s_2\in L(R)$, and $s_1$ and $s_2$ are aligned together in the optimal alignment that we construct. We also show that our method generalizes for the case of the problem with affine gap penalties, and for finding optimal regular expression constrained local sequence alignments.     

Limit theorems for random walks

We consider a random walk $S_{\tau }$ which is obtained from the simple random walk $S$ by a discrete time version of Bochner’s subordination. We prove that under certain conditions on the subordinator $\tau$ appropriately scaled random walk $S_{\tau }$ converges in the Skorohod space to the symmetric $\alpha$-stable process $B^{\alpha }$. We also prove asymptotic formula for the transition function of $S_{\tau }$ similar to the Pólya’s asymptotic formula for $B^{\alpha }$.     

一类正则锥在非线性奇异边值中的应用

本文构造了一个新的正则锥,运用非紧减算子的不动点定理,得到了一类非线性奇异边值问题正解的唯一性,改进了有关结果.     

Left supersymmetric Structures on Lie Superalgebras

§１．ＩｎｔｒｏｄｕｃｔｉｏｎＲｅｃｅｎｔｌｙ,ｔｈｅｓｔｕｄｙｏｆｌｅｆｔ－ｓｙｍｍｅｔｒｉｃａｌｇｅｂｒａｓａｎｄｌｅｆｔ－ｓｙｍｍｅｔｒｉｃｓｔｒｕｃｔｕｒｅｓｏｎＬｉｅａｌｇｅｂｒａｓｈａｓｂｅｃｏｍｅａｎｉｎｔｅｒｅｓｔｉｎｇｓｕｂｊｅｃｔ...