On the Condition for FSM Being a Scrambler

A necessary condition for a self-synchronizing delayless invertible finite state machine(FSM)being ascrambler was conjectured in[1].A counterexample to the conjecture is given in this paper.     

A parallel asynchronous implementation of the ϵ-relaxation method for the linear minimum cost flow problem

In this paper we present a parallel asynchronous implementation of the ϵ-relaxation method for solving the linear minimum cost flow problem on distributed memory message-passing multiprocessor systems. The general structure of the method is well suited to efficient parallelization, since a single iteration can be performed on several nodes simultaneously. We describe the implementation details of the parallel version on both a Fujitsu AP1000 and a cluster of Digital Alpha workstations connected via FDDI links. The results obtained demonstrate that our implementation is capable of substantial speedups.     

On the homogeneous Gröbner basis for tensors

Algorithmic methods of commutative algebra based on the involutive and Gröbner bases technique are efficient means for completion of equations governing dynamical systems to involution. At the same time, when working with high-dimensional tensor quantities, direct use of standard functions for calculating Gröbner bases, which are built in computer algebra systems Maple and Mathematica, requires much memory. However, being multilinear forms, tensors admit special grading that makes it possible to classify polynomials in terms of their degree of homogeneity. With regard to this feature, we propose to use a special homogeneous Gröbner basis, which allows us to avoid difficulties associated with large amount of computation. Such a basis is constructed step by step, as the degree of the polynomial grows. As an example, an algorithm for constructing the homogeneous basis in a finite-dimensional Hamiltonian system with many polynomial constraints (the so-called Yang-Mills mechanics) is presented.     

On the state estimation for non-linear dynamic systems †

The object of this paper is to present an approximate technique for state estimation of non-linear dynamical systems under noisy observations. The conditional cumulant is introduced, by which the conditional probability density can be characterized. A set of dynamical equations satisfied by conditional cumulants is derived, and an approximate method is proposed for computing the cumulants. The relation of the cumulant method to the stochastic linearization technique is also discussed. Finally the state estimation problem for linear stochaatic system with state-dependent disturbance is solved to illustrate the use of the Gaussian approximation.     

On the abs algorithms for perturbed linear systems ∗

One of the most important problems in numerical analysis and numerical optimization is to solve a linear system of equations. Sometimes it should be repeated when one of the equations is replaced by a new one. In this paper as a result of theoretical analysis, an algorithm model and a particular algorithm which are based on the ABS class are proposed. After the original linear system has been solved by the ABS class, the algorithms proposed here can efficiently solve the new system which is obtained from the original system by replacing one of its equations by using information obtained in the previous computation. These algorithms can be used continually when some equations of the original system are replaced by new equations successively with less computation effort.     

On the analogue methods for power spectral density estimation†

This paper examines an analogue method for power spectral density estimation which employs an asymmetrical modulation. The approximate expressions for the expected value and for the dispersion of the estimate thus obtained are worked out by means of simplifying hypotheses.

Then a comparison is drawn between the method under examination and another one with symmetrical modulation; it is shown that in some cases the former has advantageous results in that at a parity of estimate dispersion it demands a smaller number of components.     

On Some Optimization Problems for the Rényi Divergence

We consider the problem of determining the maximum and minimum of the Rényi divergence D_λ(P||Q) and D_λ(Q||P) for two probability distribution P and Q of discrete random variables X and Y provided that the probability distribution P and the parameter α of α-coupling between X and Y are fixed, i.e., provided that Pr{X = Y } = α.     

On finite difference methods for the solution of the Schrödinger equation

A review for the numerical methods used for the solution of the Schrödinger equation is presented.     

The maximum principle for systems with time-delay†

In this paper the classical maximum principle of Pontryagin is modified for obtaining the optimal solution for dynamical processes with time-delay in system dynamical equations. An optimal control problem is then solved using Hamilton's canonical equations derived for the system with time-delay.     

On the co‐polarized phase difference for oil spill observation

In this study dual‐polarized synthetic aperture radar (SAR) measurements were used to enhance oil spill observation. The co‐polarized phase difference (CPD) was modelled and used to characterize the scattering return from oil spills and biogenic slicks. The model predicts, under low to moderate wind conditions, a larger CPD standard deviation (σ) for oil with respect to the sea, while for biogenic slicks a σ value similar to that for the sea is obtained. Experiments accomplished with multilook complex (MLC) C‐ and L‐band SAR data show that the model predictions are confirmed and that the C‐band is, as expected, to be preferred to the L‐band.     

On the minimum number of neighbors needed for consensus of flocks

This paper investigates consensus of flocks consisting of $n$ autonomous agents in the plane, where each agent has the same constant moving speed $v_n$ and updates its heading by the average value of the $k_n$ nearest agents from it, with $v_n$ and $k_n$ being two prescribed parameters depending on $n$. Such a topological interaction rule is referred to as $k_n$-nearest-neighbors rule, which has been validated for a class of birds by biologists and verified to be robust with respect to disturbances. A theoretical analysis will be presented for this flocking model under a random framework with large population, but without imposing any {\it a priori} connectivity assumptions. We will show that the minimum number of $k_n$ needed for consensus is of the order ${\rm O}(\log n)$ in a certain sense. To be precise, there exist two constants $C_1>C_2>0$ such that, if $k_n > C_1\log n$, then the flocking model will achieve consensus for any initial headings with high probability, provided that the speed $v_n$ is suitably small. On the other hand, if $k_n 相似文献   

On the Problem of Optimizing Parallel Programs for Complex Memory Hierarchies

Based on a thorough study of the relationship between array element accesses and loop indices of the nested loop,a method is presented with which the staggering relation and the compacting relation between the threads of the nested loop (either with a single linear function of with multiple linear functions) can be determined at compile-time,and accordingly the nested loop (either perfectly nested one or imperfectly nested one) can be restructured to avoid the thrashing problem.Due to its simplicity,our method can be efficiently implemented in any parallel compiler,and the improvement of the performance is significant as shown be the experimental results.     

Does the cosmological principle exist in the rotating Universe?

We find the probability density distribution of torque orientations in the Universe for the entire period of its evolution. It is shown that in the early Universe the orientation of its spin is random, and the cosmological principle is satisfied. This result is naturally consistent with the CMBisotropy. In the modern Universe the rotation axis direction becomes anisotropic, and the cosmological principle, strictly speaking, is not satisfied. This is confirmed by the large-scale anisotropy in the distribution of space objects and by the torque alignment direction. But since the value of the angular velocity of our Universe is \(\omega_{U_{n}}\sim10^{-19}\;\text{Hz}\), finding of such rotation and its influence on the natural processes is extremely difficult. So today dominates the view that the Universe is isotropic, and the cosmological principle is satisfied in it.     

On a collocation B-spline method for the solution of the Navier–Stokes equations

A novel B-spline collocation method for the solution of the incompressible Navier–Stokes equations is presented. The discretization employs B-splines of maximum continuity, yielding schemes with high-resolution power. The Navier–Stokes equations are solved by using a fractional step method, where the projection step is considered as a Div–Grad problem, so that no pressure boundary conditions need to be prescribed. Pressure oscillations are prevented by introducing compatible B-spline bases for the velocity and pressure, yielding efficient schemes of arbitrary order of accuracy. The method is applied to two-dimensional benchmark flows, and mass lumping techniques for cost-effective computation of unsteady problems are discussed.     

On the Hopcroft’s minimization technique for DFA and DFCA

We show that the absolute worst case time complexity for Hopcroft’s minimization algorithm applied to unary languages is reached only for deterministic automata or cover automata following the structure of the de Bruijn words. A previous paper by Berstel and Carton gave the example of de Bruijn words as a language that requires $O(nlogn)$ steps in the case of deterministic automata by carefully choosing the splitting sets and processing these sets in a FIFO mode for the list of the splitting sets in the algorithm. We refine the previous result by showing that the Berstel/Carton example is actually the absolute worst case time complexity in the case of unary languages for deterministic automata. We show that the same result is valid also for the case of cover automata and an algorithm based on the Hopcroft’s method used for minimization of cover automata. We also show that a LIFO implementation for the splitting list will not achieve the same absolute worst time complexity for the case of unary languages both in the case of regular deterministic finite automata or in the case of the deterministic finite cover automata as defined by S. Yu.     

A metric space for computer programs and the principle of computational least action

We define a normed metric space for computer programs and derive from it the Principle of Computational Least Action. In our model, programs follow trajectories determined by Newton’s equation of motion in an abstract computational phase space and generate computational action as they evolve. A program’s action norm is the L ₁-norm of its action function, and its distance from other programs is the distance derived from the action norm. The Principle of Computational Least Action states the goal of performance optimization as finding the program with the smallest action norm. We illustrate this principle by analyzing a simple program.

---