Optimal algorithms for total exchange without buffering on the hypercube

Two methods are given for constructing total exchange algorithms for hypercubic processor networks. This is done by means of bit sequences with special properties. The algorithms are optimal with respect to a given time model, need no intermediate message buffering and are local in the sense that every processor executes basically the same program.     

Summing over a network without revealing summands

Consider a network in which each node possesses a secret member of a finite abelian group. In this paper we present a protocol by which the nodes can compute the sums of their secret elements without revealing them to each other. The security against discovery of the secret values as a result of conspiracies among nodes or compromise of channels between nodes is shown to depend on the connectivity of the graph defined by the network. Moreover, we are able to quantify exactly the amount of information revealed as a result of a conspiracy of a given set of nodes or compromise of a given set of channels.     

Wavelet Expansions and Fractal Dimensions

The bounds of the upper and lower box dimensions of the graph of a function in terms of the coefficients in its wavelet decomposition are given. An example, that the formula for upper box dimension, given in [4], does not hold, is presented. March 10, 1997. Date revised: March 3, 1998. Date accepted: March 3, 1998.     

RELATIVELY WEAKLY COMPACT SETS IN THE DEN JOY SPACE

Some topological Properties of the completion H of the Denjoy space are studied. In particular sufficient conditions for a subsets of H be relatively compact and characterizations for a subsets of H be restively weakly compact are given.     

A note on the largest empty rectangle problem

We consider the following problem: given a rectangle containingn points, find the largest perimeter subrectangle whose sides are parallel to those of the original rectangle, whose aspect ratio is below a given bound, and which does not contain any of the given points. Chazelle, Drysdale and Lee have studied a variant of this problem with areas as the quantity to be maximized. They gave anO(nlog³ n) algorithm for that problem. We adopt a similar divide-and-conquer approach and are able to use the simpler properties of the perimeter measure to obtain anO(nlog² n) algorithm for our problem.The work of the first author was supported by the Academy of Finland and that of the second by the Natural Sciences and Engineering Research Council of Canada Grant No. A-5692.     

关于图的导出森林独立系统

本文研究图的导出森林独立系统.在这个独立系统中,独立集是指导出子图不含圈的点子集.文中证明了图G的导出森林独立系统是拟阵当且仅当G是块森林.文中同时给出了在强弦图上求最大导出森林的多项式算法.     

A note on rank-additivity

A new criterion is given for rank additivity of a collection of m × n complex matrices.     

A tight upper bound for the number of intersections between two rectangular paths

The problem of finding the number of intersections between two geometric figures in the plane has been studied extensively in literature. In this paper, the geometric figure comprising a continuous rectilinear path (called rectangular path) is considered, and a tight (least) upper bound onI(P, Q), the number of intersections between two rectangular pathsP andQ, is given.Editors' Note: One of our referees has reported that the main result of this paper has recently been given independently by a Chinese researcher at the University of Science and Technology, Hefei, P. R. of China. His paper is under publication in the Chinese Science Bulletin. However, since this journal may not be easily accessible to our readers, and further the two papers are obviously independent of each other, theBIT Editors have decided to accept the present paper.     

The Relaxed Intertwining Lifting in the Coupling Approach

We discuss the relaxed lifting theorem by using a coupling framework. A simple proof of the existence of the relaxed lifting is given; the approach also yields a sufficient condition for uniqueness of the lifting. We investigate in more detail a particular case, in which a complete parametrization of solutions can be obtained.     

二阶Melnikov函数及其应用

在Ｍｅｌｎｉｋｏｖ函数的种种应用中，目前常见到的仅是一阶形式。本文具体推导了二阶Ｍｅｌｎｉｋｏｖ函数的分析表达，提出了临界情况下考察双曲鞍点的稳定流形与不稳定流形相对位置的二阶判据，并成功地用于环面ｖａｎｄｅｒＰｏｌ方程的研究中。     

Monotone and Convex C 1 Hermite Interpolants Generated by a Subdivision Scheme

   Abstract. We propose C ¹ Hermite interpolants generated by the general subdivision scheme introduced by Merrien [17] and satisfying monotonicity or convexity constraints. For arbitrary values and slopes of a given function f at the end-points of a bounded interval, which are compatible with the contraints, the given algorithms construct shape-preserving interpolants. Moreover, these algorithms are quite simple and fast as well as adapted to CAGD. We also give error estimates in the case of interpolation of smooth functions.     

Markov Decision Processes with Distribution Function Criterion of First-Passage Time

In this paper we discuss MDP with distribution function criterion of first-passage time. Some properties of several kinds of optimal policies are given. Existence results and algorithms for these optimal policies are given in this paper. Accepted 24 July 2000. Online publication 12 April 2001.     

关于微分同胚的一个充分必要条件

确定两个流形是否C^r-微分同胚是微分流形研究中的重要课题,本文定义了反层的概念,给出了反层范畴,由此找到两个微分流形,C^r-微分同胚的特征刻画,于是给出了一种较以往更优的判定法．     

Minimal perfect hashing in polynomial time

We present a universally applicable algorithm for generating minimal perfect hashing functions. The method has (worst case) polynomial time complexity in units of bit operations. An adjunct algorithm for reducing parameter magnitudes in the generated hash functions is given. This probabilistic method makes hash function parameter magnitudes independent of argument (input key) magnitudes.     

Geometry of conservation laws for a class of parabolic PDE's, II: Normal forms for equations with conservation laws

We consider conservation laws for second-order parabolic partial differential equations for one function of three independent variables. An explicit normal form is given for such equations having a nontrivial conservation law. It is shown that any such equation whose space of conservation laws has dimension at least four is locally contact equivalent to a quasi-linear equation. Examples are given of nonlinear equations that have an infinite-dimensional space of conservation laws parameterized (in the sense of Cartan-K?hler) by two arbitrary functions of one variable. Furthermore, it is shown that any equation whose space of conservation laws is larger than this is locally contact equivalent to a linear equation.     

WEAK CONVERGENCE OF HENSTOCK INTEGRABLE SEQUENCES

Some relationships between pointwise and weak convergence of a sequence of Henstock integrable functions are studied, In particular it is provided an example of a sequence of Henstock integrable functions whose pointwise limit is different from the weak one. By introducing an asymptotic version of the Henstock equiintegrability notion it is given a necessary and sufficient condition in order that a pointwisely convergent sequence of Henstock integrable functions is weakly convergent to its pointwise limit.     

二维Kuramoto—Sivashinsky方程的非平凡分歧解及其稳定性

这篇文章讨论了二维K-S方程的分歧现象。对于给定的正整数n_0,m_0,a=n_0~2 m_0~2是一个分歧点,在a附近从平凡解分歧出来的非平凡解枝数依赖于不定方程n~2 m~2=a解的个数,本文给出了解的渐近表示,并讨论了它们的稳定性。     

Lattice Paths and Positive Trigonometric Sums

A trigonometric polynomial generalization to the positivity of an alternating sum of binomial coefficients is given. The proof uses lattice paths, and identifies the trigonometric sum as a polynomial with positive integer coefficients. Some special cases of the q -analogue conjectured by Bressoud are established, and new conjectures are given. January 22, 1997. Date revised: July 9, 1997.     

数值输入模糊输出数据的最小二乘回归模型

本文给出了一个拟合数值输入模糊数输出数据的线性回归模型,证明了模型的解存在且唯一,并得到了解的表达式。     

Multi-attribute hashing with multiple file copies for high performance partial-match retrieval

The average cost for answering partial-match queries can be dramatically reduced by storing multiple copies of the data, each with a different clustering. We analyse the cost benefits (in terms of page accesses) of this arrangement and present heuristic algorithms for determining a near-minimal-cost file organisation for a given probability distribution of queries. We also show how constraining the range of values for specific attributes affects the usefulness of maintaining multiple copies.