Some decidability problems of sentential formst †

Various decidability problems of SF-languages, i.e. sets of sentential forms, of Chomsky grammars are studied. Among the problems are the equivalence, ambiguity, equality to a regular set, and regularity of SF-languages, and the SF-ness of regular languages. All of these problems are undecidable for type 0 grammars, and many of them are decidable for minimal linear grammars. Strongest possible undecidability and decidability results are looked for.     

Some applications of matrices to location of zeros of polynomials†

In previous papers classical theorems on location of zeros of a polynomial with respect to the left half plane Γ₁ or the unit circle Γ₂ have been reformulated more simply in terms of appropriate companion matrices. It is shown how this work can be extended to the problem of zero location with respect to more general regions Γ of the complex plane. The first approach is to apply the bilinear transformation to the given polynomial, so that for example Γ₁ can be mapped into Γ₂ and a matrix representation of this is derived. An alternative method is discussed which relies on transformation of Γ into Γ₂. Some examples illustrate how any theorem involving Hurwitz-typc minors can be expressed in companion matrix terms, with a consequent halving of the orders of the determinants involved.     

Some “goodness” properties of LDA lattices

We study some structural properties of Construction-A lattices obtained from low density parity check codes over prime fields. Such lattices are called low density Construction-A (LDA) lattices, and permit low-complexity belief propagation decoding for transmission over Gaussian channels. It has been shown that LDA lattices achieve the capacity of the power constrained additive white Gaussian noise (AWGN) channel with closest lattice-point decoding, and simulations suggested that they perform well under belief propagation decoding. We continue this line of work and prove that these lattices are good for packing and mean squared error quantization and that their duals are good for packing. With this, we can conclude that codes constructed using nested LDA lattices can achieve the capacity of the power constrained AWGN channel, the capacity of the dirty paper channel, the rates guaranteed by the computeand-forward protocol, and the best known rates for bidirectional relaying with perfect secrecy.     

Some Studies on Two and Three-level Simplified Expressions of Boolean Functions†

A method of directly testing whether the AND-OR or the OR-AND form of a switching function is more economic for some simple cases is presented. Simplified expressions leading to economic three-level synthesis have also been derived.     

Some properties of Rényi entropy over countably infinite alphabets

We study certain properties of Rényi entropy functionals $H_\alpha \left( \mathcal{P} \right)$ on the space of probability distributions over ?₊. Primarily, continuity and convergence issues are addressed. Some properties are shown to be parallel to those known in the finite alphabet case, while others illustrate a quite different behavior of the Rényi entropy in the infinite case. In particular, it is shown that for any distribution $\mathcal{P}$ and any r ∈ [0,∞] there exists a sequence of distributions $\mathcal{P}_n$ converging to $\mathcal{P}$ with respect to the total variation distance and such that $\mathop {\lim }\limits_{n \to \infty } \mathop {\lim }\limits_{\alpha \to 1 + } H_\alpha \left( {\mathcal{P}_n } \right) = \mathop {\lim }\limits_{\alpha \to 1 + } \mathop {\lim }\limits_{n \to \infty } H_\alpha \left( {\mathcal{P}_n } \right) + r$ .     

Robustness of absolute stability†

The stability of a class of single-input, single-output singularly perturbed systems formed by a linear time-invariant feedforward block with a sector bounded time varying feedback is considered. It is shown that if the reduced order ‘ slow ’ subsystem is absolutely stable and the parasitics are asymptotically stable and sufficiently fast then the full system is absolutely stable. Bounds on the singular perturbation parameter for uniform asymptotic stability and absolute stability are obtained.     

Stabilization of non-linear systems†

The problem of stabilizing a discrete-time non-linear system is considered. For a rather large class of common stabilizable non-linear systems, a procedure leading to the stabilization of a given non-linear system Σ belonging to that class is derived. In this procedure, a pair of compensators is constructed, consisting of a precompensator and an output feedback compensator, which, when connected in closed loop around the system Σ, yield a closed-loop system that is internally stable for bounded input sequences. The procedure allows the construction of infinitely many different pairs of such compensators, thus facilitating the choice of a convenient one.     

Vulnerability of dynamic systems†

The purpose of this paper is to formulate and partially resolve the problem of vulnerability of dynamic systems in the context of the theory of directed graphs. A system is considered vulnerable if its structural properties such as input (output) reachability or structural controllability (observability) is destroyed by a perturbation characterized as removal of a line, or set of lines, from the corresponding graph. Graph-theoretic procedures are developed to identify the minimal sets of lines which are essential for preserving the structural properties of the system.     

Hierarchies of recursive computations†

A recursive version of the Turing machine model is used to analyze the time and storage complexity of recursive algorithms. Hierarchy theorems are proven for time and for width of recursion (the amount of storage used at a level). A particular language is shown to be the “hardest” language to recognize without recursion. Previous results relating recursive and non-recursive time bounded computations are sharpened.     

State-feedback control of non-linear systems†

A design method for state-feedback controllers for single-input non-linear systems is proposed. The method makes use of the transformations of the non-linear system into ‘controllable-like’ canonical forms. The resulting non-linear state feedback is designed in such a way that the eigenvalues of the linearized closed-loop model are invariant with respect to any constant operating point. The method constitutes an alternative approach to the design methodology recently proposed by Baumann and Rugh. Also a review of different transformation methods for non-linear systems is presented. An example and simulation results of different control strategies are provided to illustrate the design technique.     

Radar backscattering of forest stands†

Research on the potential applications of microwave remote sensing in agriculture is conducted in the Netherlands by the ROVE team. Since active microwave remote sensing, featuring its all-weather capability, also seems to be a promising tool for forest classification, especially on a global scale, the Wageningen Agricultural University started a new working group in co-operation with the ROVE team in order to explore this field of application.

Results of four X-band SLAR flights have been analysed. The digital radar images obtained are accurately corrected both geometrically and radiometrically and indicate gamma values instead of arbitrary grey tones.

Radar signatures, showing seasonal and angular effects, of 16 classes of forest stands have been derived from the images. Special attention has been paid to the statistical properties of the radar signatures and their impact on classification accuracy. Several interesting phenomena have been observed indicating effects of vegetation structure on radar backscattering.

One of the test areas is a young forest in the Oost-Flevoland polder featuring a substantial variety of species; parcels are relatively large, rectangular in shape, homogeneous in structure and age and with pure species stands making this an ideal test site. Another test area is an old forest located at the Veluwe. Much variation in age is present here, which made it possible to determine relationships between tree age and radar backscatter for several coniferous tree species.

The initial work as presented here clearly demonstrates the appropriateness of X-band ability in the classification of (Dutch) forests. Theoretical considerations suggest that a multitemporal approach is likely to give the most accurate results of tree-type classification. A classification simulation yielded overall error fractions ranging from 10 to 16 per cent at the Oost-Flevoland polder test area and 14 to 28 per cent at the Veluwe test area. This can be demonstrated in multitemporal radar images as well as in actual classified images.     

Constrained controllability of discrete-time systems†

The constrained controllability of the discrete-time system x_k+1=A(k)x_k+B(k)u,_k is considered where the control uk is termed admissible if it satisfies specified magnitude constraints. Constrained controllability is concerned with the existence of an admissible control which steers the state x to a given target set from a specified initial state

Conditions for checking constrained controllability to a given target set from a specified initial state are presented. These conditions involve solving finite-dimensional optimization problems and can be checked via numerical computation. In addition, conditions for checking global constrained controllability to a given target set are presented. A system is globally constrained controllable if for every initial state, there exists an admissible control that steers the system to the target.

If a given discrete-time system is constrained controllable, it may be desirable to obtain an admissible control that steers the system to the target from a specified initial state. Such a control is called a steering control. Results for computing steering controls are also presented

This paper is concluded with a numerical example. In this example, it is shown that the constrained controllability of a continuous-time system which has been discretized is dependent on the discretization time. The set of states which can be steered to the target changes as the discretization time changes. Furthermore, the example shows that a discrete-time steering control cannot always be obtained by discretizing a continuous-time steering control; the steering control for the discrete-time system must be obtained directly from the discrete-time model.     

Fuzzy control of steam turbines†

A feasibility study of a fuzzy logic speed control of a steam turbine is reported. The efficiency of the fuzzy control is compared with conventional PID control. As a basis for this comparison, we use a mathematical model of the turbine which has been well validated at a real turbine in connection with the design of the PID control. For this model, a simple fuzzy controller is designed. To assess the resulting fuzzy control, we study by simulation the step response of the speed at a full load reduction, as well as the robustness with respect to parameter variations of the turbine.     

Optimization of linear systems of constrained configuration†

For the sake of simplicity it is often desirable to restrict the number of feedbacks in a controller. In this case the optimal feedbacks depend on the disturbance to which the system is subjected. Using a quadratic error integral as a measure of the response, three criteria of optimization are considered :

1. The response to a given initial disturbance.

2. The worst response to an initial disturbance of given magnitude.

3. The worst comparison with the unconstrained optimal system.

It is shown that for each of these criteria the gradient with respect to the feedbacks can be calculated by a uniform method. The solution may then be found either directly or by a descent procedure. The method is illustrated by an example.     

Derivation languages of grammar forms†

The family of derivation languages or Szilard languages associated with a grammar form is studied. It is shown that Szilard equivalence, regular completeness and regular sufficiency are decidable properties. Although the decidability of left Szilard equivalence remains open, we reduce this problem to the equivalence problem for a special class of s-grammar forms     

Synthesis of a Class of Non-linear Systems†

A problem in the practical application of the Volterra series to nonlinear theory is the synthesis of systems with a given set of Volterra kernels. In this article we present a method of determining whether a given Volterra kernel can be synthesized exactly by using only a finite number of multipliers. A method for the synthesis of such kernels is also presented. The use of the techniques discussed here is illustrated by examples.     

Determination of zeros of polynomials by synthetic division †

An algorithm is introduced for finding zeros of polynomials with real as well as complex coefficients. Based on the geometrical and functional properties of polynomials, the method can determine accurate distinct and repeated zeros of polynomials. The convergence of Newton's method plays an important role in this method. It has been found that the region of convergence by Newton's method is adequate. The important feature of this procedure is the obtaining of zeros of polynomials by combining Newton's method, synthetic division and functional properties of polynomials. The algorithm has been tested on many examples and numerical calculations have produced a greater degree of accuracy.