Two-step compensation of nonlinear systems

We study the problem of stabilization of nonlinear plants. We show that given a nonlinear plant P, if there exists a (nonlinear) compensator F, possibly unstable, which stabilizes P, then, with P₁: = P(I − F(− P))⁻¹, any C defined by C:= F + Q(I − P₁Q)⁻¹ for some finite-gain stable Q will stabilize P.     

You can (sometimes) tell an image by its cover

For a digital image D let the cover of D be defined by C(D) = Σ_P.Q?Dd(P,Q) where d is the city block distance. Formulas are obtained for C(D) for various shapes including upright line segments, rectangles, isosceles triangles and diamonds. It is shown that certain images can be recognized from their cover values in the presence of additional geometric symmetry conditions.     

Computing Homomorphisms Between HolonomicD-modules

Let K C be a subfield of the complex numbers, and let D be the ring of K -linear differential operators on R = K [ x₁, . . . , x_n]. If M and N are holonomic left D -modules we present an algorithm that computes explicit generators for the finite dimensional vector space _D(M, N). This enables us to answer algorithmically whether two given holonomic modules are isomorphic. More generally, our algorithm can be used to get explicit generators for _Dⁱ(M, N) for any i in the sense of Yoneda.     

An alternative solution to the H∞-optimal control problem

In this paper we present an alternative solution to the problem min _{X ε H^n×n∞} |A + BXC|_∞ where A, B, rmand C are rational matrices in H^n×n_∞. The solution circumvents the need to extract the matrix inner factors of B and C, providing a multivariable extension of Sarason's H^∞-interpolation theory [1] to the case of matrix-valued B(s) and C(s). The result has application to the diagonally-scaled optimization problem int |D(A + BXC)D⁻¹|_∞, where the infimum is over D, X εH^n×n_∞, D diagonal.     

Approximate matching of polygonal shapes

For two given simple polygonsP, Q, the problem is to determine a rigid motionI ofQ giving the best possible match betweenP andQ, i.e. minimizing the Hausdorff distance betweenP andI(Q). Faster algorithms as the one for the general problem are obtained for special cases, namely thatI is restricted to translations or even to translations only in one specified direction. It turns out that determining pseudo-optimal solutions, i.e. ones that differ from the optimum by just a constant factor, can be done much more efficiently than determining optimal solutions. In the most general case, the algorithm for the pseudo-optimal solution is based on the surprising fact that for the optimal possible match betweenP and an imageI(Q) ofQ, the distance between the centroids of the edges of the convex hulls ofP andI(Q) is a constant multiple of the Hausdorff distance betweenP andI(Q). It is also shown that the Hausdorff distance between two polygons can be determined in timeO(n logn), wheren is the total number of vertices.This research was supported by the Deutsche Forschungsgemeinschaft under Grant Al 253/1–2, Schwerpunktprogramm Datenstrukturen und effiziente Algorithmen, and by the ESPRIT Basic Research Action No. 7141 (ALCOM II).     

Parallel Construction of (a, b)-Trees

We present an optimal parallel algorithm for the construction of (a, b)-trees-a generalization of 2-3 trees, 2-3-4 trees, and B-trees. We show the existence of a canonical form for (a, b)-trees, with a very regular structure, which allows us to obtain a scalable parallel algorithm for the construction of a minimum-height (a, b)-tree with N keys in O(N/p + log log N) time using p ≤ N/log log N processors on the EREW-PRAM model, and in O(N/p) time using p ≤ N processors on the CREW model. We show that the average memory utilization for the canonical form is at least 50% better than that for the worst-case and is also better than that for a random (a, b)-tree. A significant feature of the proposed parallel algorithm is that its time-complexity depends neither on a nor on b, and hence our general algorithm is superior to earlier algorithms for parallel construction of B-trees.     

2D Bilinear programming for robust PID/DD controller design

A new design method of PID structured controllers to achieve robust performance is developed. Both robust stabilization and performance conditions are losslessly expressed by bilinear constraints in the proportional‐double derivative variable ( k _P, k _DD) and the integral‐derivative variable ( k _I, k _D). Therefore, the considered control design can be efficiently solved by alternating optimization between ( k _P, k _DD) and ( k _I, k _D), which is a 2D computationally tractable program. The proposed method works equally efficiently whenever even higher order differential or integral terms are included in PID control to improve its robustness and performance. Numerical examples are provided to show the viability of the proposed development. Copyright © 2016 John Wiley & Sons, Ltd.     

Inversion Problems in theq-Hahn Tableau

If { P_n(x;q)}_nis a family of polynomials belonging to the q -Hahn tableau then each polynomial of this family can be written as P_n(x;q) = ∑_{m = 0}ⁿD_m(n)_m(x) where _m(x) stands for (x;q)_mor x^m. In this paper we solve the corresponding inversion problem, i.e. we find the explicit expression for the coefficients I_m(n) in the expansion _n(x) = ∑_{m = 0}ⁿI_m(n)P_m(x;q).     

The strong semantics for logic programs

Recently, the well-founded semantics of a logic programP has been strengthened to the well-founded semantics-by-case (WF_C) and this in turn has been strengthened to the extended well-founded semantics (WF_E). Both WF_C(P) and WF_E(P) have thelogical consequence property, namely, if an atomAj is true in the theory Th(P), thenAj is true in the semantics as well. However, neither WF_C nor WF_E has the GCWA property, i.e., if an atomAj is false in all minimal models ofP,Aj may not be false in WF_C(P) (resp. WF_E(P)). We extend the ideas in WF_C and WF_E to define a strong well-founded semantics WF_S which has the GCWA property. The strong semantics WF_S(P) is defined by combining GCWA with the notion ofderived rules. Here we use a new Type-III derived rules in addition to those used in WF_C and WF_E. The relationship between WF_S and WF_C is also clarified.     

Stable polyhedra in parameter space

A typical uncertainty structure of a characteristic polynomial is P(s)=A(s)Q(s)+B(s) with A(s) and B(s) fixed and Q(s) uncertain. In robust controller design Q(s) may be a controller numerator or denominator polynomial; an example is the PID controller with Q(s)=K_I+K_Ps+K_Ds². In robustness analysis Q(s) may describe a plant uncertainty. For fixed imaginary part of Q(jω), it is shown that Hurwitz stability boundaries in the parameter space of the even part of Q(jω) are hyperplanes and the stability regions are convex polyhedra. A dual result holds for fixed real part of Q(jω). Also σ-stability with the real parts of all roots of P(s) smaller than σ is treated.Under the above conditions, the roots of P(s) can cross the imaginary axis only at a finite number of discrete “singular” frequencies. Each singular frequency generates a hyperplane as stability boundary. An application is robust controller design by simultaneous stabilization of several representatives of A(s) and B(s) by a PID controller. Geometrically, the intersection of convex polygons must be calculated and represented tomographically for a grid on K_P.     

Memory lower bounds for XPath evaluation over XML streams

We consider the XPath evaluation problem: Evaluate an XPath query Q on a streaming XML document D. We consider two versions of the problem: 1) Filtering Problem: Determine if there is a match for Q in D. 2) Node Selection Problem: Determine the set Q(D) of document nodes selected by Q. We consider Conjunctive XPath (CXPath) queries that involve only the child and descendant axes. Let d denote the depth of D, and n denote the number of location steps in Q. Bar-Yossef et al. (2007, 2005) [6] and [7] presented lower bounds on the memory space required by any algorithm to solve these two problems. Their lower bounds apply to each query in a large subset of XPath, and are obtained (mostly) using nonrecursive(Q,D). In this paper, we present larger lower bounds for a different class of queries (namely, CXPath queries with independent predicates), on recursive(Q,D). One of our results is an Ω(n⋅maxcands(Q,D)) lower bound for the node selection problem, for a worst-case Q; maxcands(Q,D) is the maximum number of nodes of D that can be candidates for output, at any one instant. So, there is no algorithm for the node selection problem that uses O(f(d,|Q|)+maxcands(Q,D)) space, for any function f. This shows that some previously published algorithms are incorrect.     

On the connection between the exponential stability of C0-semigroups and the admissibility of a certain Sobolev space

Let T be a strongly continuous semigroup on a Banach space X and A its infinitesimal generator. We will prove that T is exponentially stable, if and only if, there exist p[1,∞) such that the space is admissible to the system Σ(A,I,I), defined below (i.e for all f belonging to the Sobolev space the convolution T*f lies in .     

On the computation of the gap metric

This paper deals with the computation of the gap metric introduced by Zames and El-Sakkary [17]. It is shown that the gap between two systems (P₁, P₂) is precisely the maximum of the two expressions for (i, j) equal to (1, 2) and (2, 1), and (N_i, D_i) being normalized right coprine factorizations of P_i, I = 1, 2, in the sense of Vidyasagar [12]. This expression is computable using well-known techniques from interpolation theory.     

Hermite Interpolation of Solid Orientations with Circular Blending Quaternion Curves

Construction methods are presented that generate Hermite interpolation quaternion curves on SO(3). Two circular curves C₁(t) and C₂(t), 0 ≤ t ≤ 1, are generated that interpolate two orientations q₁ and q₂, and have boundary angular velocities: C₁′(0) = ω₁ and C₂′(1) = ω₂, respectively. They are smoothly blended together on SO(3) to generate a Hermite quaternion curve Q(t) ∈ SO(3), 0 ≤ t ≤ 1, which satisfies the boundary conditions: Q(0) = q₁, Q(1) = ₂, Q′(0) = ω₁, and Q′ (1) = ω₂.     

A simplified approach for the design of basically non-interacting multiple-input-multiple-output systems using qft

Quantitative feedback theory (QFT) has presented techniques for the design of multiple-input-multiple-output (MIMO) linear time invariant (LTI) systems with structured parameter uncertainty in the plant P for the satisfaction of specifications on the closed loop transfer function matrix T = [T_ij]. In many practical applications the specifications are of the basically non-interacting (BNIA) type, i.e. a_ii(ω) < | T_ii(jω) | < b_ii(ω), | T_ij(jω) | < b_ij(ω), (i ≠ j) and b_ij(ω) < a_ii(ω) in a significant range of frequencies. In one QFT technique the design is based on expressing when the matrix of compensators G = diag(G_ii(s)), L_i = G_iiQ_ii, P^?1 = [1/Q_ij], D_ij a disturbance due to plant interaction between the different system channels. It is shown in this paper that when the specifications are BNIA and F = diag(F_ii(s)), the effect of the disturbance acting on the main diagonal terms (i.e. D_ii) can be neglected. This observation saves some computational burden because satisfaction of specifications on the T_iis becomes a single-input-single-output (SISO) design problem instead of the more elaborated multiple-input-single-output (MISO) design problem which had to be designed originally. A detailed 2-input-2-output design example is presented illustrating the simpler approach, stressing the importance of considering the correlation between specifications in the design procedure.     

Bases for projective modules in An(k)

Let A_n(k) be the Weyl algebra, with k a field of characteristic zero. It is known that every projective finitely generated left module is free or isomorphic to a left ideal. Let M be a left submodule of a free module. In this paper we give an algorithm to compute the projective dimension of M. If M is projective and rank(M)≥2 we give a procedure to find a basis.     

Calculating the Galois Group of Y′ = = = AY + + + B,Y′ = = = AY Completely Reducible

We consider a special case of the problem of computing the Galois group of a system of linear ordinary differential equations Y′ = MY, M C (x)^{n × n}. We assume that C is a computable, characteristic-zero, algebraically closed constant field with a factorization algorithm. There exists a decision procedure, due to Compoint and Singer, to compute the group in case the system is completely reducible. Berman and Singer (1999, J. Pure Appl. Algebr., 139, 3–23) address the case in which M = [yjsco5390x.gif M 1 * 0 M 2 ], Y′ = M_iY completely reducible for i = 1, 2. Their article shows how to reduce that case to the case of an inhomogeneous system Y′ = AY + B, A C (x)^{n × n}, B C (x)ⁿ, Y′ = AY completely reducible. Their article further presents a decision procedure to reduce this inhomogeneous case to the case of the associated homogeneous system Y′ = AY. The latter reduction involves using a cyclic-vector algorithm to find an equivalent inhomogeneous scalar equation L(y) = b,L C(x)[ D ], b C (x), then computing a certain set of factorizations of L in C(x)[D ]; this set is very large and difficult to compute in general. In this article, we give a new and more efficient algorithm to reduce the case of a system Y′ = AY + B,Y′ = AY completely reducible, to that of the associated homogeneous systemY′ = AY. The new method’s improved efficiency comes from replacing the large set of factorizations required by the Berman–Singer method with a single block-diagonal decomposition of the coefficient matrix satisfying certain properties.     

Study of enhanced DC and analog/radio frequency performance of a vertical super-thin body FET by high-k gate dielectrics

This article reports the DC and analog/radio frequency (RF) response of a newly invented device called vertical super-thin body (VSTB) FET towards high-k (Si₃N₄/HfO₂) and low-k (SiO₂) gate dielectrics in conjunction with the scaling effect through a well-calibrated Sentaurus TCAD tool. At channel length (L_G) of 20 nm, compared to SiO₂, Si₃N₄ improves various DC parameters such as off-state leakage current (I_off), on-current (I_on), on-to-off current ratio (I_on/I_off ratio), subthreshold swing (SS), and drain-induced-barrier-lowering (DIBL) by 77.15%, 26.2%, one order of magnitude, 15.78%, and 36.2%, respectively. On the other hand, a higher improvement is seen in all these DC parameters for the HfO₂ gate dielectric (I_off, I_on, I_on/I_off ratio, SS, DIBL improves respectively by 91.8%, 41.57%, two orders of magnitude, 28.28%, and 62.71%). The underlying physics behind such excellent improvement is explained by the device off-state energy band diagram, electrostatic potential, and channel electron density profile for each dielectric. Further, for all the gate dielectrics considered, the device characteristics were studied for a wide range of L_G from 10 to 50 nm to reveal the scaling impact on the device performance. Irrespective of the gate dielectric material, the device exhibits excellent performance at L_G = 10 nm, which in turn indicates to the brilliant scalability of this new device. Besides, although Si₃N₄ and HfO₂ increase gate capacitance (C_gg)/gate-drain capacitance (C_gd), due to the extremely low values of C_gg/C_gd, enhanced unit gain cut-off frequency, and gain-bandwidth-product is achieved. In addition, the increased transconductance (g_m) of the device applying Si₃N₄/HfO₂ gate dielectric leads to a higher peak value of TGF, intrinsic gain, TFP, GFP, and GTFP. This study intends to expand the fundamental knowledge about such a new device as a VSTB FET and hence, aims to be utilized in the future research of this novel device.     

Lower Bounds for Merging Networks

A lower bound theorem is established for the number of comparators in a merging network. Let M(m, n) be the least number of comparators required in the (m, n)-merging networks, and let C(m, n) be the number of comparators in Batcher's (m, n)-merging network, respectively. We prove for n≥1 that M(4, n)=C(4, n) for n≡0, 1, 3 mod 4, M(4, n)≥C(4, n)−1 for n≡2 mod 4, and M(5, n)=C(5, n) for n≡0, 1, 5 mod 8. Furthermore Batcher's (6, 8k+6)-, (7, 8k+7)-, and (8, 8k+8)-merging networks are optimal for k≥0. Our lower bound for (m, n)-merging networks, m≤n, has the same terms as C(m, n) has as far as n is concerned. Thus Batcher's (m, n)-merging network is optimal up to a constant number of comparators, where the constant depends only on m. An open problem posed by Yao and Yao (Lower bounds on merging networks, J. Assoc. Comput. Mach.23, 566–571) is solved: lim_n→∞M(m, n)/n=log m/2+m/2^{log m}.