Search

In a previous paper [1] a theory, called transfer equivalence theory for constant linear dynamical systems, was presented, which led to a simple realization algorithm. In the present paper that theory is significantly sharpened by weakening the requirements for transfer equivalence, and this leads to the concepts of prime structure and prime system.

The most familiar network flow problem is that of finding the maximal integer flow from a source s to a sink t in a network G. In this paper we discuss the problem of simultaneous flows from s to t and from t to s. The main result of this paper is a max-flow min-cut theorem for this type of problem. The method of proof used indicates a procedure for finding the maximal flows. Finally, the problem of feasibility is discussed.

A well-known theorem of Perron [4] and Frobenius [3] states that a positive matrix A of order n has a positive characteristic root c* which is simple and greater than the absolute value of the other roots. This root lies between the greatest and smallest row-sum, and it is greater than the maximum of the main diagonal elements. The coordinates of a characteristic vector belonging to co* can be chosen as positive numbers. For all these results a new simple proof has been published in [2]. Moreover, new bounds are given there for the other n 1 characteristic roots and for the greatest positive roots of the principal minors of order n 1. Finally not only the existence of co* is proved, but also a convergent method for the computation of co* is obtained. In the proof of the convergence a certain constant g is used which could be replaced by another constant to obtain a quicker convergence. But g is actually not needed if only a rough approximation from the standpoint of pure mathematics is needed since other constants depending on the numerical example will be used. Hence we were not interested in whether the convergence was somewhat quicker or not. But during the presentation of this method at the Conference for Matrix Computations in Detroit, there was a certain interest in the method, and the question of the speed of the convergence was raised. Moreover, in some papers at this meeting it was pointed out that methods for computations should be developed even if they are not suitable for present-time machines, for they may be useful for future machines. Therefore it seems that it is of interest to improve the original method in order to obtain a quicker convergence and to simplify the computation by replacing square roots of row-sums by rational functions of them. Of course, we do not want to repeat the paper [2], and so we take here the different standpoint that the results of Frobenius are already known. It will be shown that the greatest positive root of a positive matrix can be found as exactly as needed by multiplying certain rows successively by given constants and dividing the corresponding columns by these constants. Let g be the smallest element of the main diagonal of A. Instead of A

Introduction. Most encoding and decoding equipment operates in binary symbols, whereas it is often desirable to use a code consisting of symbols from GF(2S); each code symbol is really s binary symbols. This happens, for example, in multilevel transmission; it also happens when the chief function of the code is burst-error correction. The question discussed in this paper is when and how a binary cyclic code of block length s(2s 1) can be mapped in a natural way onto a cyclic code of block length 2s 1 over GF(2S). Such codes are attractive because they combine the advantages of multilevel efficiency with binary implementation; however the moral of this paper seems to be that we had better look for other ways to achieve this goal. Indeed the "natural" practical mapping between codes over GF(2) and codes over GF(2S) is mathematically rather unnatural. The image of a cyclic code over GF(2) may easily fail to be a linear space over GF(2S). Thus it is not surprising (although disappointing) that we appear to find only a rather small class of rather poor codes. The only previous published work on this subject known to the writer is due to M. Hanan and F. P. Palermo; these authors discuss a more general form of the same basic question, and arrive at the same basic conclusion. The plan of this paper is as follows: Section 1 describes the mapping p from the vector space over the binary field to the vector space over GF(2s), and gives an explicit form for the inverse mapping. Section 2 gives necessary and sufficient conditions for the image under (p of a binary cyclic code to be a cyclic code over GF(2S), and consequently for the image under p ` of a cyclic code over GF(2S) to be a binary cyclic code. These conditions are essentially the same as those given by Hanan and Palermo, and are definitely unhelpful from a practical point of view. Section 3 describes the class of "interlaced" codes, which can always be mapped back and forth, and shows that the union and intersection of an interlaced code with a mappable code is again mappable. Section 4 shows how to get new mappings from old-specifically, if a(x) is the polynomial of least degree in a mappable cyclic code (the generator polynomial), then the reciprocal polynomial of a(x) is also mappable, and so is the polynomial obtained by reversing the order of the coefficients of a(x). (The mapping function 5p is different in the three cases.) Section 5 describes the one choice of p which we know always works and shows how it works. Section 6 contains several theorems which are useful when looking for mappings; for example, we need consider only noninterlaced codes generated over GF(2s) by polynomials of degree ?s 1. The Appendix contains a series of examples, which hopefully will be useful as illustrations of the text.

In this paper random variables defined on a bicompact topological group G are examined. A regular completely additive measure $\mu $ defined on the class of all Borel subsets of G with $\mu (G) = 1$ will be called a probability distribution.Let $\xi _1 $, $\xi _2 $ be two independent G-valued random variables with probability distributions $\mu _1 $, $\mu _2 $. Then the product $\xi = \xi _1 \cdot \xi _2 $ has the probability distribution $\mu = \mu _1 \cdot \mu _2 $, where the convolution $\mu _1 \mu _2 $ is defined by the formula \[ {\text{(1)}}\qquad \mu _1 \mu _2 (E) = \int_G {\mu _1 (Ex^{ - 1} )d\mu _2 (x)} \] Let us denote by $S(G)$ the set of all probability distributions on a bicompact group G. By virtue of the multiplication defined in (1), the set $S(G)$ has become clearly a semigroup. It is possible to introduce into $S(G)$ a certain topology so that it will become a Hausdorff bicompact semigroup.The purpose of this paper is to find the class of all possible limiting distributions for a sequenc...

In this paper we use the differential recurrence relations satisfied by the ${}_2 F_1 $ and their generalizations the${}_p F_q $ and Lauricella functions to associate a Lie algebra (dynamical symmetry algebra) with each of these families of special functions. We demonstrate that the representation theory of the Lie algebras yields a variety of addition theorems and generating functions for the associated families. Most of the results of this survey are contained in the author’s papers [1]–[3] but the comments on the functions $F_A $, $F_B $, $F_C $ are new.

This paper considers the planar decomposition of a complete bipartite graph, that is, the decomposition of a complete bipartite graph into planar subgraphs such that the union of all these planar subgraphs is the original complete bipartite graph and any two of them have no edge in common. This problem is motivated by the synthesis of a given logical network consisting only of NOR and/or NAND elements with as few integrated circuits as possible. The main result of this paper is that the smallest number of planar subgraphs into which a complete bipartite graph $K_{n,n} $ can be decomposed does not exceed $[ n/3] + 1$, where $[ x ]$ stands for the minimum integer not less than x.

In this paper the relations between various semigroups of operators and between various infinitesimal operators connected with a homogeneous in t Markov process are investigated. General conditions are established under which the Markov process is determined by its corresponding infinitesimal operator.Let $U_t $ be a semigroup of linear operators in the Banach space L such that $\|U_t \| \leqq 1$. Let $T_t = U_t $ be an adjoint semigroup in the conjugate space $B = L^ * $. More abstractly the main object of this paper can be characterized as the study of semigroups $T_t $ and its infinitesimal operators in strong and weak topologies of space B.

One considers a class of linear, time-invariant controllable systems, together with a group of transformations of the systems, and one determines a complete system of independent invariants. One examines also how these invariants are influenced by a feedback. The results are also interpreted from the point of view of the canonical forms and one shows that—under some natural hypotheses—the canonical forms contained (implicitly) in the paper are described in terms of a minimal number of parameters. The algebraic concept of “universal element” is a principal tool in proving the last result and a leading guide for the whole paper.

This paper considers some aspects of two-dimensional random fields with a view toward application in information processing problems involving two-dimensional data. In particular, we call attention to two possible properties which have important implications in terms of representations. They are (a) second order homogeneity with respect to some groups of transformation; (b) the Markovian property. The most interesting results of this paper are those concerning Gaussian random fields which are both homogeneous and Markov.

In this paper we consider the differential properties of the solution to the Cauchy problem for the quasilinear parabolic equation \[ (1)\qquad \frac{{\partial v}}{{\partial t}} = \frac{1}{2}\sum\limits_{i,j = 1}^n {c_{ij} } (t,x,v)\frac{{\partial ^2 v}}{{\partial x_i \partial x_i }} + \sum\limits_{i = 1}^n {a_i } (t,x,v)\frac{{\partial v}}{{\partial x_i }}, \] where $c_{ij} = \sum\nolimits_{k = 1}^n {b_{ik} } (t,x,v)b_{jk} (t,x,v)$.Let class $C_T^{m,\gamma } $ be a class of continuous functions, which has bounded space derivatives up to the m-th order, and its m-th derivative is Holder continuous with Holder constant $\gamma $It is proved in this paper that if \[ \{ {b(t,x,v),a(t,x,v),\psi (x)} \} \in C_T^{m,\gamma } ,\qquad m \geqq 2, \] then $v \in C_{t_0 }^{m,\gamma } $, where $t_0 > 0$ depends only on the constants of class $C_T^{m,\gamma } $. If $n = 1$, $a(t,x,v) \equiv 0$, then the above assertion will follow for all $t \in [0,T]$ and $x \in ( - \infty ,\infty )$. It is noted that $b(t,x,v)$ may b...

In this paper we study some approximation theory questions which arise from the analysis of the discretization error associated with the use of the Rayleigh-Ritz-Galerkin method for approximating the solutions to various types of boundary value problems, cf. [13, [2], [33, [43, [7], [8], [93, [12], [143, [18], [19], [20] and [22]. In particular, we consider upper and lower bounds for the error in approximation of certain families of functions in Sobolev spaces, cf. [15], by functions in finite-dimensional "polynomial spline types" subspaces, cf. [16]. In doing this, we directly generalize, improve, and extend the corresponding results of[1], [17], [18], [19], [20], and [21]. Throughout this paper, the symbol K will be used repeatedly to denote a positive constant, not necessarily the same at each occurrence and the symbol μ will be used repeatedly to denote a nonnegative, continuous function on [0,∞], not necessarily the same at each occurrence.

In this paper we investigate the relations between conditional expectations in the strict sense (i.e. ordinary conditional expectations) and in the wide sense (i.e. projections of a Hilbert space $L_2 $ into some closed linear subspace), as they were defined by Doob [3].Let $(X,F,\mu )$ be a probability space and $G \subset F$ be some $\sigma $-algebra. We denote by $L_2 (G)$ the system of all G-measurable random variables of $L_2 $. Following Bahadur we name such subspaces, $L_2 (G)$, measurable subspaces, and projections on them measurable projections.The most important result of the paper is the followingTheorem 3.The system$\mathfrak{M} \subset L_2 $is a measurable subspace if and only i f it satisfies the following conditions: (0) $\mathfrak{M}$ is a closed linear subspace, (1) $1 \in \mathfrak{M}$, (2) if$f \in \mathfrak{M}$, $g \in \mathfrak{M}$, then$\max (f,g) \in \mathfrak{M}$.In papers published up to now the operation of multiplying two functions was used, but it was introduced only for bounde...

This paper derives the conditions guaranteeing that a singular extremal that joins fixed endpoints provides a strong minimum for the independent time variable. For the nonsingular case, Weierstrass has shown that the extremal must be embedded in a field. The principal conditions that imply the existence of a field for a nonsingular problem with an n-dimensional state vector ${\bf x}$ and a scalar control variable u are that ${{\partial ^2 H} / {\partial u^2 }}$ is unequal to zero and that the $n \times (n + 1)$ matrix $[{{\partial {\bf x}(t)} / {\partial \lambda (t_0 )}},\dot {\bf x}(t)]$ has rank n. Here t is the time, H is the generalized Hamiltonian, and $\lambda $ is the adjoint vector. This paper shows that under proper assumptions the field concept can be extended to the singular case. The condition on ${{\partial ^2 H} / {\partial u^2 }}$ is replaced by \[ \frac{\partial } {{\partial u}}\frac{{d^2 }} {{dt^2}}\frac{{\partial H}} {{\partial u}} \ne 0. \] The above matrix, whose first n columns are ob...

It is knowyn [5, Theorem 2.7] that if A > 0 (every element of A is nonnegative), then A has a inonnegative real eigenvalue equal to its spectral radius. If in addition A is irreducible, then this eigeuivalue is positive and simple. If a nonnegative irreducible matrix has k eigenvalues of modulus p(A), then A is said to be k-cyclic if k > I and primitive if k = 1. In a recent paper [8], Yamamoto iintroduced an iterative method for finding nested upper and lower bounds for the spectral radius of a nonnegative irreducible matrix. Although the method applies to both cyclic and primitive matrices, it involves matrix squaring, so its utility may be offset by a substantial increase in computing costs over the power method [11, [2], [5]. These increased costs might be justified for cyclic matrices (for which the power method fails to converge) or for matrices with dominance ratio close to unity, a condition which slows the convergence of the power method. However, such justification would depend on comparisons of the convergence properties of the competing methods. In an attempt to make theoretical comparisons of Yamamoto's method with the classical power method, a third "hybrid" method was developed. This new method also applies to cyclic matrices, and, like Yamamoto's method, involves matrix squaring. This paper establishes the convergence properties of the new method and compares it with the other two. The hybrid method is shown to give as good (and in most cases considerably better) bounds as Yamamoto's method or the power method. A practical comparison supports the theoretical findings, which indicate that the

This paper discusses some new results related to ergodic and limit theorems and also to the repeated logarithm low for inhomogeneous Markov chains. Theorems are formulated and proved for conditions that were not treated in the literature; some estimates obtained previously by S. N. Bernshtein are employed.Lemma 1 is of greatest importance in the paper.

This paper describes an algorithm for finding dominators in an arbitrary directed graph. The algorithm uses depth-first search and efficient algorithms for computing disjoint set unions and manipulating priority queues to achieve a time bound of $O(V\log V + E)$ if V is the number of vertices and E is the number of edges in the graph. This bound compares favorably with the $O(V(V + E))$ time bound of previously known algorithms for finding dominators in arbitrary directed graphs, and with the $O(V + E\log E)$ time bound of a known algorithm for finding dominators in reducible graphs. If $E \geqq V\log V$, the new algorithm requires $O(E)$ time and is optimal to within a constant factor.

Algorithms for the identification of the cliques (maximal complete subgraphs) of a graph are generally designed to produce the cliques of the graph from its adjacency information only—that is, given only the points and the lines of the graph. This paper presents two new clique detection algorithms.One utilizes (a) the cliques of a subgraph of the graph having the same points, and (b) the set of lines of the graph not in the subgraph. The other utilizes (a) the cliques of a supergraph of the graph having the same points, and (b) the set of lines of the supergraph not in the graph. The development of the theorems underlying the algorithms, which relate the cliques of a graph to those of the subgraph obtained by the removal of a line from the graph, are also presented. These algorithms are intended primarily for application to a special problem which arises in certain graph theoretical cluster analysis schemes : a sequence of graphs, all having the same points, is generated ; each is subjected to a cluster a...

This paper derives a simple formula for calculating upper and lower bounds for the number of sets of nonnegative integer variables that satisfy a single linear inequality with positive rational coefficients. These bounds are shown to be tighter than several recently published ones.

This is an expository paper dealing with those tools in asymptotic analysis which are especially useful in obtaining asymptotic results in enumeration problems. Emphasis is on tools which are general, are easily applied, and give estimates of the form $a_n \sim f(n)$. Many examples are given to illustrate the usage of the various tools. It is assumed that a summation or a generating function for $a_n $ is explicitly or implicitly given.

This is an expository paper on some connections between coding theory and combinatorial mathematics (and number theory). A long introduction to linear codes is followed by short sections on perfect codes, t-designs, sphere packings, simple groups, lattices, and theta-functions, and projective planes.

This paper considers the problem of merging sets formed from a total of n items in such a way that at any time, the name of a set containing a given item can be ascertained. Two algorithms using different data structures are discussed. The execution times of both algorithms are bounded by a constant times $nG(n)$, where $G(n)$ is a function whose asymptotic growth rate is less than that of any finite number of logarithms of n.

A basic algorithm for solving many discrete problems is the so-called “backtracking” algorithm. The basic problem is that of generating the elements of a subset $S_0 $ of a finite set in an efficient manner. If a group G acts on $S_0 $, then one might wish to obtain only nonisomorphic elements of $S_0 $. In this paper the basic backtracking algorithm is described in terms of chains of partitions on the set S. The corresponding isomorph rejection problem is described in terms of G-invariant chains of partitions on S. Examples and flow charts are given.

With $\mathcal{H}$ a family of sets and $\mathcal{D}$ a set, a social choice function assigns a nonempty subset $F(Y,D)$ of Y to each $(Y,D) \in \mathcal{H} \times \mathcal{D}$. In social choice theory, the sets in $\mathcal{H}$ are feasible alternative sets, each $D \in \mathcal{D}$ specifies preferences on the alternatives of individuals in the society, and $F(Y,D)$ denotes the “best” alternatives in Y for each potential situation $(Y,D)$. This paper reviews a number of topics in social choice theory through the medium of social choice functions. It begins with two-alternative situations, providing axiomatic characterizations of simple majority, weighted majority, absolute special majority and representative systems. Various aspects of simple majorities with many alternatives are examined, including facets of cyclical majorities, single-peaked preferences and sets of individual preference orders that guarantee the transitivity of simple majority. A classification of types of conditions for general socia...

The main results of this paper are two-fold. The first, Theorem 1, is a generalization of the work of Chow and others concerning the set of locally accessible points of a nonlinear control system. It is shown that under quite general conditions, this set lies on a surface in state space and has a nonemptyinterior in the relative topology of that surface.The second result, Theorem 3, generalizes the bang-bang theorem to nonlinear control systems using higher order control variations as developed by Kelley and others. As a corollary we obtain Halkin’s bang-bang theorem for a linear piecewise analytic control system.

The problem of the existence and construction of a table of interpolating rational functions is considered. Some general properties of this table and relations between its elements are proved. Sufficient conditions for the existence of continued fractions whose convergents form the elements of the table are given.The results in this paper are mainly obtained by using methods which are similar to certain methods used in the theory of Pade approximation.

Since 1970, it has been known that open loop Nash equilibrium points exist for N-person differential games when there are integral bounds on the control functions. These results were obtained using various fixed-point theorems, and required that the duration of the game be “small”.In this paper it is assumed that the controls are constrained to take values in compact, convex subsets of $R^{q_i} $. A fixed-point theorem due to Tychonov is used, and as a result there are no restrictions on the duration of the game.

This paper gives a formal definition of the biological concept of evolutionary distance and an algorithm to compute it. For any set S of finite sequences of varying lengths this distance is a real-valued function on $S \times S$, and it is shown to be a metric under conditions which are wide enough to include the biological application. The algorithm, introduced here, lends itself to computer programming and provides a method to compute evolutionary distance which is shorter than the other methods currently in use.

A theorem of Stroud and Mysovskikh ascertains that we can construct a two-dimensional integration formula of degree $N = 2m - 1$ with the $m^2 $ distinct, finite common zeros of two orthogonal polynomials $P1(x,y)$ and $P2(x,y)$ of degree m as points.This paper gives the pairs of orthogonal polynomials of second degree, dependent on a characteristic number introduced by Mysovskikh, whose zeros give rise to a third degree integration formula with four real points and positive weights.

In this paper we introduce a method to obtain all generating functions of Boas and Buck type for any given orthogonal polynomial set. We also characterize the orthogonal polynomials that satisfy \[xP'_n (x) = nP_n (x) + \sum\limits_0^{n - 1} {( - 1)^{n - k} \rho _k P_k (x)\quad {\text{with }}\rho _k \ne 0,\quad k = 0,1, \cdots .} \]

With the kth conjugate point of t$\eta _k (t)$, defined for a given nth order linear differential equation as the minimum number r greater than t such that there exists a nontrivial solution of the differential equation having zeros at t and r and at least $n + k - 1$ zeros on the interval $[ t,r ]$, it is well known that $\eta _k (t)$ is a strictly increasing continuous function of t when $k = 1$; however, this question remains open when $k > 1$. For $k\geqq 1$, the main theorems of this paper give conditions which guarantee that $\eta _k (t)$ is strictly increasing and continuous and that $\eta _k (t)$ depends continuously on the coefficients in the given differential equation. The relationship between these results and previous results for fourth order differential equations is indicated.

Some established results concerning best $L_p $-approximations are introduced, and it is shown that a minimax approximation can generally be found as the limit of a sequence of such approximations. The values of p required, however, are too large to be practicable, and the main part of this paper is devoted to the development of an extrapolation scheme which enables minimax approximations to be predicted from best $L_p $-approximations for comparatively small values of p. Numerical evidence is presented to show that the scheme works well in practice.

A class of optimal control problems is studied in which the controls and outputs are taken as elements in Banach spaces, and the cost functions and constraints are expressible in terms of the norms on these spaces. The paper is principally concerned with generalizing certain results of Balakrishnan relating to optimal control in Hilbert space to this more general setting.

Practical interpolation schemes for functions of more than one variable need not be finite dimensional as in the case of univariate functions. The so-called “blending function methods” are one example of such transfinite schemes. Another is the method of “pseudo-harmonic interpolation” described in this paper. For any bounded, convex planar domain $\mathcal{D}$, we show how to construct a bivariate function U which interpolates to arbitrary Dirichlet boundary conditions on the perimeter of $\mathcal{D}$. The interpolant $U(Q)$ satisfies the familar “maximum principle” and, in the case in which the domain $\mathcal{D}$ is circular, is actually a harmonic function in $\mathcal{D}$. Higher order schemes are described in which the function $U(Q)$ interpolates to specified normal derivatives on the boundary of $\mathcal{D}$ as well as to the Dirichlet boundary conditions. The interpolation schemes are also viewed as idempotent linear operators (i.e., projectors) on families of continuous functions on $\overlin...

This paper is concerned with best two-sided scaling of a general square matrix, and in particular with a certain characterization of that best scaling: namely that the first and last singular vectors (on left and right) of the scaled matrix have components of equal modulus. Necessity, sufficiency, and its relation with other characterizations are discussed. Then the problem of best scaling for rectangular matrices is introduced and a conjecture made regarding a possible best scaling. The conjecture is verified for some special cases.

This paper is concerned with the problem of determining bounds on the rate of growth of oscillatory solutions of the delay-differential equationn $y'(x) = my(x - d(x))$ when the delay function $d(x)$ is bounded. Special triples $(y,d,m)$ are considered, where d is piecewise continuous and $m = 1$ or $m = - 1$. Obtainable bounds on the growth of a solution y belonging to such a triple are given in terms of the bound on d and the number of half-cycles through which y has oscillated.

This paper presents a class of iterative procedures, called accelerated Frank–Wolfe algorithms, It shows that a subclass, namely the nontrivial proper algorithms, is of special interest. An algorithm parametrized by an integer q is exhibited and it is then seen that for every $q > 0$, the algorithm is a nontrivial proper accelerated Frank–Wolfe algorithm.

Let $( {\Omega ,\mathcal{B}} )$ be a measurable space, ${\rm X},Y$ be separable Hilbert spaces. Let T be a random linear operator from $\Omega \times {\rm X}$ into Y. Let $T^\dag ( \omega )$ denote the generalized inverse of $T( \omega )$, for $\omega \in \Omega $. Questions of measurability of $T^\dag ( \omega )$ are investigated in this paper, and in particular the following results are established: (i) If T is bounded, then $T^\dag $ is a random operator. (ii) If T is a closed operator with dense domain and if $T^\dag $ is bounded, then $T^\dag $ is a random operator under some mild restriction on the domains of $T( \omega )$ and $T^ * ( \omega ),\omega \in \Omega $. The results are applied to the measurability of best approximate solutions of random linear operator equations.

Let L be a positive, linear functional and F be an approximation to L that is exact for polynomials of degree $n - 1$. According to Peano’s theorem we can write $(L - F)(f) = R(f) = \int {f^{(n)} (t)} K(t)dt$, where $K(t)$ is the Peano kernel. If $K(t)$ is of one sign, then accurate error estimates can be obtained by computing $R(x^n )$. However, it is usually a difficult task to determine when $K(t)$ is of one sign. This paper presents easily applied conditions for $K(t)$ to be of one sign. These conditions apply to formulas F which are constructed by first interpolating the function by a polynomial P and then setting $Rf = (L)(f - P)$. The interpolation processes known as Hermite–Birkhoff interpolation are the ones studied here. The conditions given have only to do with the method of interpolation and do not depend on the functional L or the various points where the function and its derivative may be evaluated. The results are applied to some well-known quadrature rules such as Simpson’s rule and Euler–...

The present paper shows how to construct a maximum matching in a bipartite graph with n vertices and m edges in a number of computation steps proportional to $(m + n)\sqrt n $.

In this paper we consider first order context-free, linear, and regular graph grammars and obtain many results similar to those for the corresponding string grammars. We obtain normal forms for context-free and regular graph grammars, simplification lemmas, and algorithms for membership, emptiness, finiteness and infiniteness. We show the relation between regular graph languages and regular sets and show that the set of graphs resembling the nonregular set $\{ a^n b^n | n \geqq 1\} $ is not generated by a first order context-free graph grammar. We also give several graphical characterizations of each of the three types of graph grammars.

This paper gives an alternative proof of Brouwer’s fixed-point theorem. The expected preknowledge on the part of the reader in following the proof is the continuity of the roots of polynomial equations with respect to the coefficients, and the standard compactness argument.

Suppose a program P is written to accept a set of inputs I. If we are only interested in a nonempty subset $I^ * $ of I, we usually can simplify P to another program $P^ * $ such that $P^ * $ runs faster on $I^ * $ than P does. The problem of specialization is to find such $P^ * $. In this paper, the program P and the input $I^ * $ will be specified by axioms. Using these axioms, we can obtain $P^ * $ from P through theorem-proving techniques.

This paper gives a necessary and sufficient condition that the common zeros of a set of polynomials in n variables can be used as the points in an integration formula for an n-dimensional region. This result applies for all $n \geqq 1$.

This paper is concerned with the problem of determining bounds on the rate of growth of oscillatory solutions of the delay-differential equation $y'(x) = y(x - d(x))$ when the delay function $d(x)$ is bounded above by some constant D for all $x\leqq x_0 $. A class of special pairs $(y,d)$ is constructed so that y is continuous and oscillatory on $[x_0 - D,\infty )$, d is piecewise continuous on $[x_0 ,\infty )$, and the functions y and d satisfy the equation $y'(x) = y(x - d(x))$ on $(x_0 ,\infty )$ except at points of discontinuity of d. Obtainable bounds on the growth of y are given in terms of the maximum delay D of the function d corresponding to y and the number of half-cycles through which y has oscillated. It is then shown that these bounds hold for more general oscillatory solutions.

Previous extensions of the stability criterion of Popov [1] for systems with a stable linear time-invariant plant $G(s)$ followed by a nonlinear time-varying gain $k(t)f( \cdot )$ entailed the definition of nonlinearity classes $[ f( \cdot ) \in N]$ and corresponding frequency domain multipliers $Z_N (s)$. Then, defining a measure of nonlinearity \[ F_{\min } \equiv \mathop {\min }\limits_x \{ \frac{{xf( x)}}{{\int_0^x {f( z )dz} }} \} \] stability is ensured if $Z(s) \in Z_N (s)$ exists, such that (i) $G(s)Z(s)$ is strictly positive real, (ii) $Z(s - \Lambda ) \in Z_N (s)$ and (iii)\[\frac{1}{k}\frac{{dk}}{{dt}}\leqq \Lambda F_{\min } \quad ( {\text{see [ 5 ]}}).\]In this paper, the point by point requirement of (iii) is replaced by an integral criterion. In many cases the constraints on $k(t)$ predicated by the integral inequality are substantially less strict than those of (iii) above. As (iii) is a special case of the integral relation, the results are never more strict.The development here will be li...

In this paper stationary stochastic processes in the strong sense are investigated, which satisfy the condition \[ | {{\bf P} ( {AB} ) - {\bf P} ( A ){\bf P} ( B )} | \leqq \varphi ( n ){\bf P}( A ),\quad \varphi ( n ) \downarrow 0, \] for every $A \in \mathfrak{M}_{ - \infty }^0 ,B \in \mathfrak{M}_n^\infty $, or the “strong mixing condition” \[ \mathop {\sup }\limits_{A \in \mathfrak{M}_{ - \infty }^0 ,B \in \mathfrak{M}_n^\infty } | {{\bf P} ( {AB} ) - {\bf P} ( A ){\bf P} ( B )} |\alpha ( n ) \downarrow 0, \] where $\mathfrak{M}_a^b $ is a $\sigma $-algebra generated by the events \[ \{ {( {x_{i_1 } ,x_{i_2 } , \cdots ,x_{i_k } } ) \in {\bf E}} \},\qquad a \leqq i_1 < i_2 < \cdots < i_k \leqq b, \]${\bf E}$ being a k-dimensional Borel set.Some limit theorems for the sums of the type \[ \frac{{x_1 + \cdots + x_n }}{{B_n }} - A_n \quad {\text{or}} \quad \frac{{f_1 + \cdots + f_n }}{{B_n }} - A_n \] are established. Here $f_j = T^j f$, and the random variable f is measurable with respect to $\mathfrak{M}...

This paper shows the existence of a ternary triorthogonal code and a comma-free ternary triorthogonal code. Some theorems are proved for their existence and some algorithms for generating these codes are developed. For a dictionary of size $D = 3^{n + 1} $ and word length $L = 3^n $, the former code exists for any positive integer n and the latter code exists for $n > 1$. The ternary elements $\{ 0,1,2\} $ used in the codes are isomorphic, under the one-to-one correspondence, to the triphase vectors $\{ e^{(2\pi i/3 )r} ,r = 0,1,2\}$. The modulo 3 addition of $\{ 0,1,2\} $ and the triphase vector multiplication are also isomorphic under the one-to-one correspondence.

An homogeneous random field is defined to be a family of random variables $x(s,t)$, $ - \infty < s < \infty , - \infty < t < \infty $, such that \[ {\bf M}[ {x( {s,t} )} ] \equiv 0,\mathop {\lim }\limits_{\begin{subarray}{l} h_{1 \to 0} \\ h_{2 \to 0} \end{subarray}} {\bf M}\left[ {x\left( {s + h_1 ,t + h_2 } \right) - x( {s,t} )} \right]^2 = 0 \] and that $B_x (s,t) = {\bf M}[x(s + m,t + n)x\overline {(m,n)} ]$ exists and is independent of m and n.In the present paper, the extrapolation problem consists in determining the best linear prediction for the value of the field at any point in the upper half-plane by values at points in the entire lower half-plane. Various types of homogeneous random fields (singular fields, regular fields and fields of Markov type) are considered from the point of view of extrapolation theory. Necessary and sufficient conditions for these types of random fields are given in terms of spectral functions of the field. An expression for the mean square error of the optimum predict...