Search

In some communication problems, it is a good assumption that the channel consists of an additive white Gaussian noise forward link and an essentially noiseless feedback link. In this paper, we study channels where no bandwidth constraint is placed on the transmitted signals. Such channels arise in space communications. It is known that the availability of the feedback link cannot increase the channel capacity of the noisy forward link, but it can considerably reduce the coding effort required to achieve a given level of performance. We present a coding scheme that exploits the feedback to achieve considerable reductions in coding and decoding complexity and delay over what would be needed for comparable performance with the best known (simplex) codes for the one-way channel. Our scheme, which was motivated by the Robbins-Monro stochastic approximation technique, can also be used over channels where the additive noise is not Gaussian but is still independent from instant to instant. An extension of the scheme for channels with limited signal bandwidth is presented in a companion paper (Part II).

International audience; Foreword This document presents a translation for historical perspective of the paper: " B. Courcelle, G. Kahn, and J. Vuillemin. Algorithmes d'´ equivalence et de réduction a des expressions minimales dans une classe d'´ equations récursives simples, in, Jacques Loeckx, editor, Automata, Languages and Programming, volume Abstract In this paper, we describe an algorithm for deciding equivalence in a domain whose objects are defined by uninterpreted fixpoint equations. The algorithm is then applied to finding minimal representations of those objects.

1. Introduction. Let the two random variables (r.v.) X and Y, with E(X) = p and E(Y) = q, describe the outcomes of two experiments, Ex I and Ex II. An experimenter, who does not know the values of p and q, has to perform a sequence of experiments, and at each step he may choose between Ex I and Ex II. He has to stop after n steps, and he wishes to maximise the sum of all outcomes. His decision between Ex I and Ex II at the kth step will depend on the corresponding decisions at prior steps and on the outcomes of these prior experiments. We call a plarn, which fixes his sequence of decisions according to his previous knowledge, a strategy. Robbins [6] shows that it is easy to find a strategy so that the arithmetic mean of n outcomes tends (n -- oo) towards max (p, q) with probability 1. Bradt, Johnson and Karlin [3] try to find a best strategy for fixed n rather than asymptotically. They assume known a priori distributions for the values of p and q. For other approaches see Robbins [7] Isbell [5], Bellman [2] and Vogel [8]. The purpose of this paper is to describe a class of strategies, which results from the following kind of restriction. In the first 2k steps we perform each of Ex I and Ex II k times. Then the rest of the n - 2k steps are made either with Ex I alone or with Ex II alone. The decision whether to continue with Ex I or with Ex II will be made with the help of a sequential probability ratio test for double dichotomies. Therefore k is a r.v. that will be denoted by K when appropriate. Strategies of this kind are not exceptionally good ones (in the sense of the lossfunction defined in Section 3). But when a strategy is applied in practice it may be found economic to do only one sort of experiment for most of the steps. Perhaps the equipment of the other sort of experiment can be used for other purposes; perhaps the shift from one experiment to the other is costly. For such reasons it may be quite natural to use only those strategies described above. Another justification for treating this class of strategies are the results in [8], for which the Theorems 2 and 3 of this paper are needed. Section 2 contains some auxiliary material. Except for Theorem 1, which we give in a slightly more general form than needed for the rest of this paper, nothing here is new, but we found it convenient to summarize some definitions and easy-to-prove formulas in one section. The loss-function and an approximation to the loss-function will be derived

Deming and Stephan (1940) first proposed the use of an iterative proportional fitting procedure to estimate cell probabilities in a contingency table subject to certain marginal constraints. In this paper we first relate this procedure to a variety of sources and a variety of statistical problems. We then describe the procedure geometrically for two-way contingency tables using the concepts presented in Fienberg (1968). This geometrical description leads to a rather simple proof of the convergence of the iterative procedure. We conclude the paper with a discussion of extensions to multi-dimensional tables and to tables with some zero entries.

During the life of a cellular organism, the individual cells grow, divide and die. Our aim in this paper is to examine various mathematical models that represent this process as a sequence of discrete events. In section I and ll we give models in which the development of a cell is not affected by the spatial arrangement of the neighbouring cells. In section lll we drop this restriction for one-dimensional organisms to get the Lindenmayer model. The models in the remaining sections represent attempts to generalize the Lindenmayer model to higher dimensions. The Von-Neumann cellular array model of section IV proves unsatisfactory. The geographical models of section V, Vl and Vll are somewhat better for higher dimensional organisms. The final section gives a precise definition of a class of models, that includes those models presented earlier in the paper. The hope is that biologists will find these models suitable for describing real organisms and that mathematicians will be stimulated to prove biologically interesting theorems about them.

On the basis of already known theoretical results concerning the use of the geoelectrical sounding method with the a p p a r a t us immersed in water, in t h e present paper we i n d i v i d u a t e the kernel f u n c t i on of t h e p a r t i c u l a r geometry of t h e problem. The s t u d y of t h e p r o p e r t i e s of t h e kernel function allows a b e t t e r understanding of the possibilities of a p p l i c a t i o n of the new method. The theoretical results t h a t we describe must be regarded, among other things, as t h e basis for t h e derivation of a direct q u a n t i t a t i v e i n t e r p r e t a t i o n method.

In choice reaction time tasks, response latency varies as the subject changes his bias for speed vs accuracy; this is the speed-accuracy tradeoff. Ollman's Fast Guess model provides a mechanism for this tradeoff by allowing the subject to vary his probability of making a guess response rather than a stimulus controlled response (SCR). It is shown that the mean latency of SCR's (μs) in two-choice experiments can be estimated from a single session, regardless of how the subject adjusts his guessing probability. Three experiments are reported in which μs apparently remained virtually constant despite tradeoffs in which accuracy varied from chance to near-perfect. From the standpoint of the Fast Guess model, this result is interpreted to mean that the tradeoff here was produced almost entirely by mixing different proportions of fast guesses and constant (mean) latency SCR's. The final sections of the paper discuss the question of what other models might be compatible with μs invariance.

The question whether a system of n — 1 real algebraic numbers (n = 2, 3, •) chosen from an algebraic field of degree not higher than n9 yields periodicity by Jacobi's Algorithm is still as open and challenging as hundred years ago. The present paper gives an affirmative answer to this problem in the following case: let K(w) be an algebraic number field generated by w = (Dn — d: m)ί/n, where m, n, d, D are natural numbers satisfying the conditions m^ 1, n έ 3, d | D, 1 ^ d ^ D/2(n — 1). Then n — 1 numbers can be chosen from K(w), so that their Jacobi Algorithm becomes purely periodic. The length of the period equals n2 (or n, if d = m = 1). This is the longest period of a periodic Jacobi Algorithm ever known. In three corollaries the following special cases are investigated

The aim of this paper is to present and discuss the application of the epsilon technique to the identification of distributed-parameter systems. After the problem formulation, attention is focused on computational aspects. The numerical results obtained for two typical systems are presented.

Results of a preceding paper on pure operations are generalized. The application to local field theory is discussed in some detail.

Heuristically guided search is a technique which systematically takes into account information from the problem domain for directing the search. The problem is to find the shortest path in a weighted graph from a start vertex V a to a goal vertex V z : For every intermediate vertex, an estimate is available of the distance to V z . If this estimate satisfies a consistency assumption, an algorithm by Hart, Nilsson, and Raphael is guaranteed to find the optimum, looking at the priori minimum number of vertices. In this paper, a version of the algorithm mentioned above is presented which is guaranteed to succeed with the minimum amount of storage. An application of this technique to the chromosome matching problem is then shown. Matching is the last stage of automatic chromosome analysis procedures, and can also solve ambiguities in the classification stage. Some peculiarities of this kind of data suggest the use of a heuristically guided search algorithm instead of the standard Edmonds' algorithm. The method that we obtain in this way is proved to exploit the clustering of chromosome data: A linear-quadratic dependence on the number of chromosomes is obtained for perfectly clustered data. Finally, some experimental results are given.

PREVENTION is a word with many rshades and ranges of meaning. I have read somewhere that in colonial days Philadelphia health officials sought to prevent an epidemic of yellow fever by repeatedly firing a cannon from the steps of City Hall. This was certainly an unique preventive approach; however, it lacked any evaluation, since no one really knows how many mosquitoes were killed by this procedure. Occam's Razor turns out to be a more formidable preventive weapon than Philadelphia cannon. Occam's Razor was tempered by a few cutting remarks about human functioning which, loosely translated and brought up to date, could be stated thus: "Don't complicate simple things." For those who prefer a more literal translation, Occam's words were: "Assumptions introduced to explain something should not be multiplied beyond necessity." The focus in this paper is not so much on the hard-nosed data about early identification of children with potential problems, but the mythologics and encrustations about mental health and education which have kept this kind of an attempt feeble and ineffective. We will need to change blades in Occam's Razor more than once, before we get any program of real significance and impact operating in this area. Now what is the mystique which needs slicing and why? The state of a child's mental health or ill health is best known and judged by a mental health professional (psychiatrist, clinical psychologist or psychiatric social worker) rather than by less "sophisticated" professional persons who live with the child on a day-to-day basis. About ten years ago, the State of California decide to invest a sizable amount of money and some of my time to find out whether emotionally disturbed children could be identified early in their school life and, if so, could something be done to immobilize, interrupt, or intercept this kind of development. We found we could identify children with beginning learning and behavior problems, if we effectively and economically used perceptual ratings of students by teachers, peers, and the students themselves. Not surprisingly, we found our measures of the state of emotional de

Methods to realize race-free asynchronous sequential circuits by using appropriate single transition time (STT) state assignments have been described in the literature. This paper deals with that restricted class of asynchronous circuits (called pulse-input asynchronous circuits) for which in every input sequence each input state l i is always followed by a special input state l o ≠l i . A method is presented to realize any pulse-input asynchronous sequential circuit with p internal states by a universal race-free STT state assignment in 2E o variables, where E o =[log 2 n] and n≤p is the number of the elements in a defined subset of internal states.

This paper presents a new method for the optimization of system reliability with linear constraints, using the parametric approach [1]. The classical nonlinear programming technique is used for the solution. This method, which is analytically complete, sufficiently accurate and computationally simple, gives optimum or near optimum design. The procedure is illustrated with examples, and flow charts for the problems are given.