Flag transitive planes of dimension four over GF(3)

Two non desarguesian flag transitive planes of order 3⁴ whose Kernel is GF(3) are constructed. These planes are distinct from the planes of the same order contained in the class constructed by Narayana Rao M. L. (Proceedings of American Mathematical Society 39 (1973) 51–56) and Ebert, G.L. and Baker, R. (Enumeration of two dimensional Flag-Transitive planes, Algebras, Groups and Geometries 3 (1985) 248–257). The Flag Transitive group modulo the scalar collineations of these planes is generated by two elements and is of order 328.     

Probabilistic aspects of finite-fuel,reflected follower problems

The issue is that of following the path of a Brownian particle by a process of bounded total variation and subject to a reflecting barrier at the origin, in such a way as to minimize expected total cost over a finite horizon. We establish the existence of optimal processes and the dynamic programming equations for this question, and show (by purely probabilistic arguments) its relation to an appropriatefamily of optimal stopping problems with absorption at the origin.Work carried out during a visit by the second author at the University Pierre et Marie Curie (Paris VI), and at INRIA (Institut National de Recherche en Informatique et en Automatique). The hospitality of these institutions is gratefully acknowledged.Research supported in part by the U.S. Air Force Office of Scientific Research, under grant AFOSR-86-0203.     

An algebraic approach to Cichelli's perfect hashing

The aim of this paper is to describe a new approach to building minimal and perfect hash functions for a predefined set of keys. Several papers have dealt with this problem and proposed various kinds of functions. This study is based on a function whose address depends both on the letter codes and the letter position in the key, and therefore represents an extension of Cichelli's function. The weights associated with the position are considered to be fixed, and letter code computing is considered to be an interpolation problem. As a result, hash building only requires the solution of an algebraic linear system and then the time complexity is polynomialO(n ³).     

On Shellsort and the frobenius problem

A boundO(N ^1+1/k ) for the running time of Shellsort, withO(logN) passes, is proved very simply by application of a Frobenius basis withk elements.     

Bin packing can be solved within 1 + ε in linear time

For any listL ofn numbers in (0, 1) letL* denote the minimum number of unit capacity bins needed to pack the elements ofL. We prove that, for every positive ε, there exists anO(n)-time algorithmS such that, ifS(L) denotes the number of bins used byS forL, thenS(L)/L*≦1+ε for anyL providedL* is sufficiently large. The work of this author was supported by NSF Grant MCS 70-04997.     

Characterization of a class of bivariate distribution functions

Let F_X,Y(x,y) be a bivariate distribution function and P_n(x), Q_m(y), n, m = 0, 1, 2,…, the orthonormal polynomials of the two marginal distributions F_X(x) and F_Y(y), respectively. Some necessary conditions are derived for the co-efficients c_n, n = 0, 1, 2,…, if the conditional expectation E[P_n(X) ∥ Y] = c_nQ_n(Y) holds for n = 0, 1, 2,…. Several examples are given to show the application of these necessary conditions.     

On the recovery of error patterns from signatures obtained in digital system testing

Error patterns are lost in the data compression process inherent in signature analysis. These however contain useful information about the faults in faulty units. The present paper investigates the possibility to recover the lost error patterns from the signatures obtained at the end of a test run. It is shown that, the recovery is possible if the test outcome sequence is not longer than the signature analyser period and if the number of possible error signatures can be reduced to a subset a priori known.     

On the construction of a class of invariant polynomials in several matrices,extending the zonal polynomials

Summary The construction of a class of invariant polynomials in several matrices extending the zonal polynomials is discussed. The method adopted generalized the orginal group-theoretic approach of James [9]. A table of three-matrix polynomials up to degree 5 is presented. CSIRO     

Foncteurs isomorphes des catégories d'actions à des catégories de fibrarations

Sans résumé

---

This article is the text of a talk given at the Symposium on Differential Geometry in Debrecen, Hungary, on August 28–September 3, 1975.     

Limit laws for upper and lower extremes from stationary mixing sequences

The aim of this paper is to examine the weak limiting behavior of upper and lower extremes from stationary sequences satisfying dependence conditions similar to D and D′ introduced by Leadbetter (Z. Wahrsch. Verw. Gebiete28 (1974), 289–303). By establishing the convergence in distribution of an associated sequence of point processes, the joint limiting distribution of any collection of upper and lower extremes can be determined. Sufficient and, in some cases, necessary conditions for the asymptotic independence of the upper and lower extremes are also given.