Cache Oblivious Algorithms for the RMQ and the RMSQ Problems

In the Range Minimum/Maximum Query (RMQ) and Range Maximum-Sum Segment Query (RMSQ) problems, we are given an array which we can preprocess in order to answer subsequent queries. In the RMQ query, we are given a range on the array and we need to find the maximum/minimum element within that range. On the other hand, in RMSQ query, we need to return the segment within the given query range that gives the maximum sum. In this paper, we present cache oblivious optimal algorithms for both of the above problems. In particular, for both the problems, we have presented linear time data structures having optimal cache miss. The data structures can answer the corresponding queries in constant time with constant cache miss.     

Summatory Functions of Digital Sums Occurring in Cryptography

Morain and Olivos gave two algorithms that allow fast exponentiation in elliptic curve cryptosystems. These algorithms are based on representations of integers in certain redundant binary number systems. In this paper we consider the weight and the sum of digits function of these representations. In particular, we give formulas for their summatory functions. In the proofs we use the Mellin-Perron formula. In order to apply this formula, we have to compute the analytic continuation of a class of Dirichlet series.     

Optimal service control against worst case admission policies: A multichained stochastic game

In this paper we will consider two-person zero-sum games and derive a general approach for solving them. We apply this approach to a queueing problem. In section 1 we will introduce the model and formulate the Key-theorem. In section 2 we develop the theory that we will use in section 3 to prove the Key-theorem. This includes a general and useful result in Lemma 2.1 on the sufficiency of stationary policies.     

闵可夫斯基空间中子流形的若干性质

本文研究了Ｆｉｎｓｌｅｒ流形中的子流形,特别地,我们给出了闵可夫斯基空间中超球面的一个特征,同时,我们讨论了闵可夫斯基空间中超曲面的第二基本形式。     

Cyclic subspace codes via subspace polynomials

Subspace codes have been intensely studied in the last decade due to their application in random network coding. In particular, cyclic subspace codes are very useful subspace codes with their efficient encoding and decoding algorithms. In a recent paper, Ben-Sasson et al. gave a systematic construction of subspace codes using subspace polynomials. In this paper, we mainly generalize and improve their result so that we can obtain larger codes for fixed parameters and also we can increase the density of some possible parameters. In addition, we give some relative remarks and explicit examples.     

A review of open queueing network models of manufacturing systems

In this paper we review open queueing network models of manufacturing systems. The paper consists of two parts. In the first part we discuss design and planning problems arising in manufacturing. In doing so we focus on those problems that are best addressed by queueing network models. In the second part of the paper we describe developments in queueing network methodology. We are primarily concerned with features such as general service times, deterministic product routings, and machine failures — features that are prevalent in manufacturing settings. Since these features have eluded exact analysis, approximation procedures have been proposed. In the second part of this paper we review the developments in approximation procedures and highlight the assumptions that underlie these approaches.     

A quasilinear Neumann problem with discontinuous nonlinearity

In this paper we study a quasilinear boundary value problem of Neumann type with discontinuous terms. In particular we consider a problem in which the p–Laplacian is involved. In order to prove the existence of solutions we replace this problem with a multivalued approximation of it and, using a variational approach for locally Lipschitz functionals, we prove two existence results for it.     

The articulation of symbol and mediation in mathematics education

In this paper we include topics which we consider are relevant building blocks to design a theory of mathematics education. In doing so, we introduce a pretheory consisting of a set of interdisciplinary ideas which lead to an understanding of what occurs in the “central nervous system”—our metaphor for the classroom and eventually in more global settings. In particular we highlight the crucial role of representations, symbols viewed from an evolutionary perspective and mathematics as symbolic technology in which representations are embedded and executable.     

在任意不定常温度场和任意法向动载荷联合作用下中心开孔圆底扁球壳的动力问题

本文得出了在任意不定常温度场和任意法向动载荷联合作用下中心开孔圆底扁球壳的动力问题的解析解.我们假设温度沿壳体厚度直线分布.在第一部分.我们研究了常用边界条件下的中心开孔圆底扁球壳的自由振动.作为例子,我们计算了一边缘夹紧的扁球壳的自然基频(m=0),所得结果与E.Reissner[1]的结果作了比较.频率方程的解法是钱伟长[2]提出来的.这将在附录3中介绍.在第二部分,我们研究了在任意谐温度场和任意谐法向动载荷联合作用下的中心开孔圆底扁球壳的强迫振动.在第三部分,我们研究了在任意不定常温度场和任意法向动载荷联合作用下的具有初始条件的上述壳体的强迫振动.在附录1和2中,我们讨论了如何用应力函数来表示位移边界条件和m=1情形的边界条件.     

Non‐linear initial boundary value problemsof hyperbolic–parabolic type. A general investigationof admissible couplings between systems of higher order. Part 1: linear theory

In this article (which is divided in three parts) we investigate the non‐linear initial boundary value problems (1.2) and (1.3). In both cases we consider coupled systems where each system is of higher order and of hyperbolic or parabolic type. Our goal is to characterize systematically all admissible couplings between systems of higher order and different type. By an admissible coupling we mean a condition that guarantees the existence, uniqueness and regularity of solutions to the respective initial boundary value problem. In part 1 at hand, we develop the underlying theory of linear hyperbolic and parabolic initial boundary value problems. Testing the PDEs with suitable functions we obtain a priori estimates for the respective solutions. In particular, we make use of the regularity theory for linear elliptic boundary value problems that was previously developed by the author. In part 2, we prove the local in time existence, uniqueness and regularity of solutions to the quasilinear initial boundary value problem (1.2) using the so‐called energy method. In the above sense, the regularity assumptions about the coefficients and right‐hand sides define the admissible couplings. In part 3, we extend the results of part 2 to the non‐linear initial boundary value problem (1.3). In particular, the assumptions about the respective parameters correspond to the previous regularity assumptions and hence define the admissible couplings now. Moreover, we exploit the assumptions about the respective parameters for the case of two coupled systems. Copyright © 2002 John Wiley & Sons, Ltd.     

On the long time behavior of non-autonomous Lotka-Volterra models with diffusion via the sub-supertrajectory method

In this paper we study in detail the geometrical structure of global pullback and forwards attractors associated to non-autonomous Lotka-Volterra systems in all the three cases of competition, symbiosis or prey-predator. In particular, under some conditions on the parameters, we prove the existence of a unique nondegenerate global solution for these models, which attracts any other complete bounded trajectory. Thus, we generalize the existence of a unique strictly positive stable (stationary) solution from the autonomous case and we extend to Lotka-Volterra systems the result for scalar logistic equations. To this end we present the sub-supertrajectory tool as a generalization of the now classical sub-supersolution method. In particular, we also conclude pullback and forwards permanence for the above models.     

直线上随机环境中可逗留的随机游动的若干性质

主要研究直线上随机环境中可逗留的随机游动的常返性与极限性质,在独立随机环境下,通过强大数定律给出了常返与暂留的一个充分条件;在一般随机环境下,通过数列的有界性给出了常返与零常返的充分条件并讨论了在独立随机环境下非常返性中的大数定律,从而推广了Solomon的研究框架.     

Robustness analysis in Multi-Objective Mathematical Programming using Monte Carlo simulation

In most multi-objective optimization problems we aim at selecting the most preferred among the generated Pareto optimal solutions (a subjective selection among objectively determined solutions). In this paper we consider the robustness of the selected Pareto optimal solution in relation to perturbations within weights of the objective functions. For this task we design an integrated approach that can be used in multi-objective discrete and continuous problems using a combination of Monte Carlo simulation and optimization. In the proposed method we introduce measures of robustness for Pareto optimal solutions. In this way we can compare them according to their robustness, introducing one more characteristic for the Pareto optimal solution quality. In addition, especially in multi-objective discrete problems, we can detect the most robust Pareto optimal solution among neighboring ones. A computational experiment is designed in order to illustrate the method and its advantages. It is noteworthy that the Augmented Weighted Tchebycheff proved to be much more reliable than the conventional weighted sum method in discrete problems, due to the existence of unsupported Pareto optimal solutions.     

Endomorphism monoids of free acts and O-wreath products of monoids

Monoids and acts which may have zero elements are considered. In Section 1 we construct a O-wreath product of monoids. In 2 we prove the theorem that the endomorphism monoid of a free act over a monoid with zero can be represented as a O-wreath product. Considering monoids with tero we are interested in their annihilator properties. In 3 we give necessary and sufficient conditions for a O-wreath product of monoids to be a right (left) Baer (Rickart) monoid. In 4 we obtain as a consequence corresponding conditions for the endomorphism monoid of a free act over a monoid with zero.     

Approximation of Markov semigroups in total variation distance under an irregular setting: An application to the CIR process

In this paper, we propose a method to prove the total variation convergence of approximation of Markov semigroups with singularities. In particular our approach is adapted to the study of numerical schemes for Stochastic Differential Equation (SDE) with simply locally smooth coefficients. First we present this method and then, we apply it to the CIR process. In particular, we consider the weak second order scheme introduced in Alfonsi (2010) and we prove that it also converges towards the CIR diffusion process for the total variation distance. This convergence occurs with almost order two.     

The fundamental existence theorem on invariant fiber bundles

For discrete dynamical systems the theory of invariant manifolds is well known to be of vital importance. In terms of difference equations this theory is basically concerned with autonomous equations. However, the crucial and currently most difficult questions in this field are related to non-periodic, in particular chaotic motions. Since this topic - even in the autonomous context is an intrinsically time-variant matter. There is and urgent need for a non-autonomous version of invariant manifold theory. In this paper we present we present a very general version of the classical result on stable and unstable manifolds for hyperbolic fixed points of diffeomorphisms. In fact, we drop the assumption of invertibility of the mapping, we consider non-autonomous difference equations rather than mappings In effect, we generalize the notion of invariant manifold to the concept of invariant fiber bundle.     

On the Stability of the Directional Regularity

In this paper we select two tools of investigation of the classical metric regularity of set-valued mappings, namely the Ioffe criterion and the Ekeland Variational Principle, which we adapt to the study of the directional setting. In this way, we obtain in a unitary manner new necessary and/or sufficient conditions for directional metric regularity. As an application, we establish stability of this property at composition and sum of set-valued mappings. In this process, we introduce directional tangent cones and the associated generalized primal differentiation objects and concepts. Moreover, we underline several links between our main assertions by providing alternative proofs for several results.

     

非线性系统的线性对称结构

非线性系统的线性对称结构洪奕光，程代展（中国科学院系统科学研究所，北京１０００８０）１９９１年１２月２０日收到．１９９３年９月１６日收到压缩稿，一、引言近年来，人们对非线性控制系统对称性问题的研究很感兴趣．这主要是因为现实世界存在着大量的对称现象，而...     

Graph homomorphisms and nodal domains

In this paper, we derive some necessary spectral conditions for the existence of graph homomorphisms in which we also consider some parameters related to the corresponding eigenspaces such as nodal domains. In this approach, we consider the combinatorial Laplacian and co-Laplacian as well as the adjacency matrix. Also, we present some applications in graph decompositions where we prove a general version of Fisher’s inequality for G-designs.     

Stochastic flows of SDEs with irregular coefficients and stochastic transport equations

In this article we study (possibly degenerate) stochastic differential equations (SDEs) with irregular (or discontinuous) coefficients, and prove that under certain conditions on the coefficients, there exists a unique almost everywhere stochastic (invertible) flow associated with the SDE in the sense of Lebesgue measure. In the case of constant diffusions and BV drifts, we obtain such a result by studying the related stochastic transport equation. In the case of non-constant diffusions and Sobolev drifts, we use a direct method. In particular, we extend the recent results on ODEs with non-smooth vector fields to SDEs.