Some remarks on the KH algorithm fors-grammars

The equivalence algorithm of Korenjak and Hopcroft (KH) fors-grammars is investigated. Two alternative versions, the KHC and KHS algorithms are presented, the first answers a question posed by Hopcroft and the second is formally and practically a faster algorithm.Work carried out under a National Research Council of Canada Grant No. A-7700.     

A note on table look-up

A more realistic bound for the average number of comparisons needed to match an incoming identifier by table look-up, when the table is still growing, is derived.Work carried out under a National Research Council of Canada Grant No. A-7700.     

A new approach toN-person,nonzero-sum,linear differential games

It is shown that there exist equilibrium strategies forn-person, nonero-sum, linear differential games if the cost to each player is convex. The approach used is believed to be novel, and is based on a theorem of Fan.This research was supported by the National Research Council of Canada under Grant No. A-7790.     

A comparison of two methods of encoding arrays

Two tree encoding techniques for arrays are compared and contrasted. It is shown that the pyramids and their generalization ford-dimensional arrays are much superior to binary tree encodings for three measures; access time, storage and average proximity.Work supported by a National Research Council of Canada Grant No. A-7700.     

On strongly exposed points and frechet differentiability

Using properties of convex functionals, it is shown that closed and bounded convex sets in a class of Banach spaces which includes separable conjugate spaces are the closed convex hulls of their strongly exposed points. This research was supported by the National Research Council of Canada, Grant A-3999.     

Majorants andL p norms

It is shown that ifG is an infinite compact abelian group, thenL ^p (G) has the upper majorant property only ifp is even orp=∞. The research for this paper was partially supported by National Research Council of Canada Operating Grant A-4822.     

2–3 brother trees

2–3 brother trees form a dense class of search trees havingO(logN) insertion and deletion algorithms. In this paper we provide anO(logN) insertion algorithm and show that these trees have much better density and storage utilization than 2–3 trees. Thus we demonstrate that the brother property which has so far been used only for binary trees can be usefully applied to 2–3 trees.Work supported partially by a Natural Sciences and Engineering Research Council of Canada Grant No. A-7700 and partially by the German Academic Exchange Service under Nato Research Grant No. 430/402/584/8.     

Optimal control of systems governed by a class of nonlinear evolution equations in a reflexive Banach space

The paper presents a closure theorem for the attainable trajectories of a class of control systems governed by a large class of nonlinear evolution equations in reflexive Banach spaces. Several existence theorems for optimal controls are proven that include a terminal control problem, a time-optimal control problem, and a special Bolza problem. Some results of independent interest are also presented.This work was supported in part by the National Research Council of Canada under Grant No. 7109.The authors would like to thank Professor L. Cesari for pointing out that joint continuity off is required for the setsG andR to satisfy the upper semicontinuity property (Theorems 5.1 and 5.2).     

A simple linear model for the optimal exploitation of renewable resources

This paper describes a simple linearized model for the optimal control of a natural resource stock. Applications of the model to fisheries and forestry, as well as to mineral exploration and recovery, are discussed.Research supported partially by the National Research Council of Canada, Grant A-3990.     

Exact and limiting distributions of the number of successions in a random permutation

Traditionally the distributions of the number of patterns and successions in a random permutation ofn integers 1,2, ..., andn were studied by combinatorial analysis. In this short article, a simple way based on finite Markov chain imbedding technique is used to obtain the exact distribution of successions on a permutation. This approach also gives a direct proof that the limiting distribution of successions is a Poisson distribution with parameter =1. Furthermore, a direct application of the main result, it also yields the waiting time distribution of a succession.This work was supported in part by the Natural Sciences and Engineering Research Council of Canada under Grant NSERC A-9216, and National Science Council of Republic of China under Grant 85-2121-M-259-003.     

Computing the link center of a simple polygon

The link center of a simple polygonP is the set of pointsx insideP at which the maximal link-distance fromx to any other point inP is minimized. Here the link distance between two pointsx, y insideP is defined to be the smallest number of straight edges in a polygonal path insideP connectingx toy. We prove several geometric properties of the link center and present an algorithm that calculates this set in timeO(n ²), wheren is the number of sides ofP. We also give anO(n logn) algorithm for finding an approximate link center, that is, a pointx such that the maximal link distance fromx to any point inP is at most one more than the value attained from the true link center.Work on this paper by the second author has been supported by National Science Foundation Grant DMS-8501947. Work by the third author has been supported by the Canadian National Science and Engineering Research Council, Grant A0332. Work by the fifth author has been supported by Office of Naval Research Grant N00014-82-K-0381, National Science Foundation Grant DCR-83-20085, and by grants from the Digital Equipment Corporation, and the IBM Corporation. Work by the seventh author has been supported by a Killam Senior Research Fellowship from the Canada Council, and work by the ninth author has been supported by the National Science Foundation Grants DCR-84-01898 and DCR-84-01633. Part of the work on this paper has been carried out at the Workshop on Movable Separability of Sets at the Bellairs Research Institute of McGill University, Barbados, February 1986. Further acknowledgments can be obtained from the tenth author upon request.     

A new criterion for 7 to be a fourth power (modp)

A new application is made of Muskat’s evaluation of the cyclotomic numbers of order fourteen, to obtain a necessary and sufficient condition for seven to be a fourth power modulo a prime≡1 (mod 28). Research supported by Natural Sciences and Engineering Research Council Canada Grant No. A-7233.     

Optimal control of a large turboalternator

The optimal torque and voltage control for a large turbogenerator is found by using the minimum norm formulation. It should be noted that the model used is highly nonlinear. Numerical results are presented.This work was supported in part by the National Research Council of Canada, Grant No. A4146.     

Martingale representation and the Malliavin calculus

Using stochastic flows and the Itô differentiation rule, the integrand in the representation of a martingale as a stochastic integral is identified. By iterating this representation result a homogeneous chaos type expansion is obtained. Using the stochastic integral representation, an integration by parts formula is obtained without using any calculus of variations in function space. If the inverse of the Malliavin matrix belongs to all spacesL ^p() it follows that a random variable has a smooth density.The research of R. J. Elliott was partially supported by the Natural Sciences and Engineering Research Council of Canada under Grant A-7964 and the Air Force Office of Scientific Research, United States Air Force, under Grant AFOSR-86-0332. The research of M. Kohlmann was partially supported by the Natural Sciences and Engineering Research Council of Canada under Grant A-7964.     

On realizing symmetric 3-polytopes

We prove the analogue of Eberhard’s Theorem for symmetric convex 3-polytopes with a 4-valent graph, and disprove a conjecture of the late T. Motzkin about realizing symmetric convex 3-polytopes so that all of their geodesics are in planes. This research was supported by the National Research Council of Canada Grant A-3999.     

The exponential rates of convergence of posterior distributions

After the observations were observed, the posterior distribution under mild conditions becomes more concentrated in the neighbourhood of the mode of the posterior distribution as sample size n increase. In this paper, the exponential rate of convergence of posterior distribution around the mode is established by using the generalized Laplace method. An example is also given.This work was supported in part by the Natural Sciences and Engineering Research Council of Canada under Grant NSERC A-9216.     

The rectangle intersection problem revisited

We take another look at the problem of intersecting rectangles with parallel sides. For this we derive a one-pass, time optimal algorithm which is easy to program, generalizes tod dimensions well, and illustrates a basic duality in its data structures and approach.The work of the first author was supported by the DAAD (Deutscher Akademischer Austauschdienst) and carried out while visiting McMaster University as a postdoctoral fellow. The work of the second author was supported by a Natural Sciences and Engineering Research Council of Canada Grant No. A-7700.     

On the chernoff-savage theorem for dependent sequences

Summary Given a sequence of ϕ-mixing random variables not necessarily stationary, a Chernoff-Savage theorem for two-sample linear rank statistics is proved using the Pyke-Shorack [5] approach based on weak convergence properties of empirical processes in an extended metric. This result is a generalization of Fears and Mehra [4] in that the stationarity is not required and that the condition imposed on the mixing numbers is substantially relaxed. A similar result is shown to hold for strong mixing sequences under slightly stronger conditions on the mixing numbers. Research partially supported by the National Research Council of Canada under Grant No. A-3954.     

Optimal load frequency control with governor backlash

A new technique is described for designing an optimal controller for a system whose dynamical equations contain a backlash element. The approach is applied to the problem of load frequency control (LFC) of a single area steam power system.This work was supported in part by the National Research Council of Canada, Grant No. A4146.     

State estimation of linear dynamical systems under bounded control

The problem of estimation of all possible states that a linear system under bounded control may take (namely, the reachable or attainable set) is addressed. A number of previously developed Lyapunov techniques for estimating the reachable set of ann-dimensional linear system are extended and compared. The techniques produce over-estimates in the form ofn-dimensional ellipsoids. Illustrative examples are solved.This work was supported by the Natural Sciences and Engineering Research Council of Canada, Operating Grant Nos. A-0621 and A-4080, and by Research Personnel Support from the Dean of Science, Memorial University of Newfoundland, Canada.