Search

This paper reviews the theory of search. The main viewpoint is statistical but considerable space is spent on connections with other fields such as logic and optimisation. Three primitive ideas dominate: consistency, entropy, and Bayes' methods. The theory of screening provides one of the central examples and there is a section on nonsequential random search deriving from the work of Renyi. The game of Bulls and Cows provides a motivating example for both sequential and nonsequential algorithms.     

Stochastic Navier-Stokes equations

We construct a solution to stochastic Navier-Stokes equations in dimension n4 with the feedback in both the external forces and a general infinite-dimensional noise. The solution is unique and adapted to the Brownian filtration in the 2-dimensional case with periodic boundary conditions or, when there is no feedback in the noise, for the Dirichlet boundary condition. The paper uses the methods of nonstandard analysis.The research of this author was supported by an SERC Grant.     

Chromatic number of Hasse diagrams,eyebrows and dimension

We construct posets of dimension 2 with highly chromatic Hasse diagrams. This solves a previous problem by Nesetril and Trotter.     

An efficient fault-tolerant decentralized commit protocol for single site failure

To maintain consistency on a distributed database system, a commit protocol is often employed to ensure that either all the sub-transactions of a transaction commit or all abort. Special care needs to be taken to ensure the correct functioning of a commit protocol in the face of node failures during the execution of the protocol. A protocol is said to be fault-tolerant if it properly commits or aborts, even if nodes fail.In this paper, we present a fault tolerant decentralized commit protocol which is message optimal in the absence of failures. Furthermore, the protocol (FTDCP) ensures that all sites can achieve a consistent final decision by at most 4 extra messages in the single site failure situation.     

Perturbation bounds for theLDL H andLU decompositions

LetA andA+A be Hermitian positive definite matrices. Suppose thatA=LDL ^H and (A+A)=(L+L)(D+D)(L+L)^H are theLDL ^H decompositons ofA andA+A, respectively. In this paper upper bounds on |D| _F and |L| _F are presented. Moreover, perturbation bounds are given for theLU decomposition of a complexn ×n matrix.     

Some regularity properties of algorithms and additive functions with respect to them

Summary The paper deals with the behaviour of the so-called algorithms with respect to interval filling sequences A connection is established between the uniquely representable points and the continuity points of the algorithms; also strong continuity properties on monotonic algorithms are proved. Finally the results are applied to additive functions. The theorems extend some former results by the authors, by I. Kátai and by A. Járai.Dedicated to the memory of Alexander M. Ostrowski on the occasion of the 100th anniversary of his birth     

Internal approximation of quasi-variational inequalities

Summary In this paper the internal approximation of a quasi-variational inequality is considered. An algorithm of Bensoussan-Lions type is proposed for which the convergence is proved. These results are applied to Signorini problem with friction for which two error estimates and numerical examples are also given.     

A mixed version of Menger's theorem

An(a, b)-n-fan means a union ofn internally disjoint paths. Menger's theorem states that a graphG has an(a, b)-n-fan if and only ifG isn-connected betweena andb. We show thatG contains edge-disjoint(a, b)-n-fans if and only if for anyk withk0min{n–1, |V(G)|–2} and for any subsetX ofV(G)-{a, b} with cardinalityk, G-X is (n-k)-edge-connected betweena andb.     

Trees in tournaments

Letf(n) be the smallest integer such that every tournament of orderf(n) contains every oriented tree of ordern. Sumner has just conjectures thatf(n)=2n–2, and F. K. Chung has shown thatf(n)(1+o(1))nlog₂ n. Here we show thatf(n)12n andf(n)(4+o(1))n.     

Some identities for products and degree raising of splines

In this paper it is shown how the algebraic product of two spline functions, each represented in terms of B-splines, can again be represented as a linear combination of suitable B-splines. As a corollary to this result we obtain an explicit representation of a given B-spline function in terms of B-splines of some arbitrary higher degree. This generalizes some known results for raising the degree by one. Recurrence relations for both products and degree raising are established that may be useful for computation.Communicated by Larry L. Schumaker.