Normal forms for multi‐input flat systems of minimal differential weight

We present normal forms for nonlinear control systems that are the closest to static feedback linearizable ones, that is, for systems that become feedback linearizable via the simplest dynamic feedback, which is the one‐fold prolongation of a suitably chosen control. They form a particular class of flat systems, namely those of differential weight n + m + 1, where n is the number of states and m is the number of controls. We also show that the dynamic feedback may create singularities in the control space depending on the state and we discuss them. We also address the issue of the normalization of the system only versus that of the system together with a flat output. Finally, we illustrate our results by several examples.     

On Local Structural Stability of Differential 1-Forms and Nonlinear Hypersurface Systems on a Manifold with Boundary

In this paper we consider smooth differential 1-forms and smooth nonlinear control-affine systems with (n−1)-inputs evolving on an n-dimensional manifold with boundary. These systems are called hypersurface systems under the additional assumption that the drift vector field and control vector fields span the tangent space to the manifold. We locally classify all structurally stable differential 1-forms on a manifold with boundary. We give complete local classification of structurally stable hypersurface systems on a manifold with boundary under static state feedback defined by diffeomorphisms, which preserve the manifold together with its boundary. Date received: March 30, 2000. Date revised: October 30, 2000.     

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).     

Study on climbing strategy and analysis of Mars rover

To ensure the safety and efficiency of Zhurong Mars rover when climbing a slope on Mars, the forces of the rover under four climbing methods, which are normal climbing, Z-type climbing, diagonal climbing, and bionic wriggle climbing, are analyzed. Each method corresponds to different maximum climbing slopes. The experiments are carried out with a backup rover on dense and soft terrains to determine the range of climbing slope for different climbing methods. According to the slope, peak current, cost of transport, and state of terrain, the climbing strategy is given. For dense and soft terrains, the soil cohesive is 0.99 and 1.4 kN/mⁿ⁺¹ and soil friction modules are 1528 and 700 kN/mⁿ⁺², respectively. Specifically, normal climbing is recommended for low-range slopes, while Z-type or diagonal climbing are suggested for medium-range slopes, and bionic wriggle climbing is found to be optimal for high-range slopes. To ensure the safety of the Zhurong Mars rover, it fails climbing if the critical values are exceeded. These results provide valuable insights for human operators when planning the rover's slope-climbing actions on Mars.     

Four rendezvous problems for n non-identical simple-integral plants

Four rendezvous problems for n non-identical simple-integral plants (K ₁/s, K₂/s,[tdot],K_n/s), with a common input x(t) = A_mi^m u(t), m = 0,1,2,[tdot], and initial output conditions of (ξ₁,ξ₂,[tdot], ξ_n), are studied in this paper. These rendezvous problems, generally speaking, are concerned with transferring the n plants outputs to meet one another in a finite time (at a. fixed target or on a non-stationary one).     

Incomplete crossed hypercubes

In this paper, a new interconnection network called the incomplete crossed hypercube is proposed for connecting processors of parallel computing systems. The incomplete crossed hypercube architecture denoted by CI _n−m ⁿ is made by combining two complete crossed hypercubes CQ _n and CQ _n−m for 1≤m≤n. Several topological properties of CI _n−m ⁿ are analyzed. In particular, accurate mean internode distance formulas of both CQ _n and CI _n−m ⁿ are given. Compared with the incomplete enhanced hypercube EI _n−m ⁿ , CI _n−m ⁿ has shorter mean internode distance for large n. An optimal routing algorithm for CI _n−m ⁿ is also described which guarantees the generation of a shortest path from a node to another in CI _n−m ⁿ .     

Efficient Algorithms for k-Terminal Cuts on Planar Graphs

The minimum k-terminal cut problem is of considerable theoretical interest and arises in several applied areas such as parallel and distributed computing, VLSI circuit design, and networking. In this paper we present two new approximation and exact algorithms for this problem on an n-vertex undirected weighted planar graph G. For the case when the k terminals are covered by the boundaries of m > 1 faces of G, we give a min{O(n ² log n logm), O(m ² n ^1.5 log² n + k n)} time algorithm with a (2–2/k)-approximation ratio (clearly, m \le k). For the case when all k terminals are covered by the boundary of one face of G, we give an O(n k3 + (n log n)k ²) time exact algorithm, or a linear time exact algorithm if k = 3, for computing an optimal k-terminal cut. Our algorithms are based on interesting observations and improve the previous algorithms when they are applied to planar graphs. To our best knowledge, no previous approximation algorithms specifically for solving the k-terminal cut problem on planar graphs were known before. The (2–2/k)-approximation algorithm of Dahlhaus et al. (for general graphs) takes O(k n ² log n) time when applied to planar graphs. Our approximation algorithm for planar graphs runs faster than that of Dahlhaus et al. by at least an O(k/logm) factor (m \le k).     

PIN OLEDs — Improved structures and materials to enhance device lifetime

Abstract— Currently, three issues are identified that decide upon the commercial success of organic light‐emitting diodes (OLEDs), both in display and lighting applications: power efficiency, lifetime, and price competitiveness. PIN OLEDs are widely seen as the preferred way to maximize power efficiency. Here, it is reported that this concept also delivers the world longest lifetimes. For a highly efficient deep‐red PIN OLED, a half‐lifetime of 25,000 hours for a starting brightness of 10,000 cd/m² and a minimal voltage increase over lifetime is reported. This value corresponds to more than 1 × 10⁶ hours at 1000 cd/m² using an exponent of n = 1.7, which was measured by driving the OLEDs at different starting luminances. Because there is no initial luminance drop, these PIN OLEDs also exhibit a very high 80% lifetime (>300,000 hours at 1000 cd/m²). New record lifetime values for blue and green will be reported as well. Additionally, further topics that have impact on the production yield and cost such as the newly developed air‐stable organic n‐doping material NDN‐26 and top‐emitting structures will be discussed.     

On-line 2-satisfiability

We deal with the followingon-line 2-satisfiability problemP(m, n): starting fromC(0)=true, consider a sequence ofm Boolean formulasC(k) (inn variables and in conjunctive normal form), each of them being the intersection of the previous one with a single clause which is the union of two literals. Solve the sequence of 2-satisfiability problemsC(k)=true,k=1,...,m. It is well known that a 2-satisfiability problem involvingm clauses can be solved inO(m) time. Thus, by a naive approach one can solveP(m, n) in overallO(m ²) time. We present an algorithm with overallO(nm) time complexity, which for every formula not only checks its satisfiability, but also actually computes a solution (if any), and moreover, detects all forced and all identical variables. Our algorithm makes use of an efficient on-line transitive closure procedure by Italiano. We discuss two applications to the design of integrated electronic circuits and to edge classification in automated perception.To the memory of Bob Jeroslow     

An Efficient Algorithm for Batch Stability Testing

Given a stable marriage problem instance represented by a bipartite graph having 2n vertices and m edges, we describe an algorithm that can verify the stability of k different matchings in a batch fashion in O((m+kn)log ² n) time. This affirmatively answers a longstanding open question of Gusfield and Irving as to whether stability can be verified in a batch setting (after sufficient preprocessing) in time sub-quadratic in n.     

Efficient Algorithms for <Emphasis Type="Italic">k</Emphasis>-Terminal Cuts on Planar Graphs

The minimum k-terminal cut problem is of considerable theoretical interest and arises in several applied areas such as parallel and distributed computing, VLSI circuit design, and networking. In this paper we present two new approximation and exact algorithms for this problem on an n-vertex undirected weighted planar graph G. For the case when the k terminals are covered by the boundaries of m > 1 faces of G, we give a min{O(n ² log n logm), O(m ² n ^1.5 log² n + k n)} time algorithm with a (2–2/k)-approximation ratio (clearly, m \le k). For the case when all k terminals are covered by the boundary of one face of G, we give an O(n k3 + (n log n)k ²) time exact algorithm, or a linear time exact algorithm if k = 3, for computing an optimal k-terminal cut. Our algorithms are based on interesting observations and improve the previous algorithms when they are applied to planar graphs. To our best knowledge, no previous approximation algorithms specifically for solving the k-terminal cut problem on planar graphs were known before. The (2–2/k)-approximation algorithm of Dahlhaus et al. (for general graphs) takes O(k n ² log n) time when applied to planar graphs. Our approximation algorithm for planar graphs runs faster than that of Dahlhaus et al. by at least an O(k/logm) factor (m \le k).     

Moduli and canonical forms for linear dynamical systems II: The topological case

In this paper we study real linear dynamical systems \(\dot x = Fx + Gu,y = Hx,x \in R^n \) = state space,u ∈ R ^m = input space,y ∈ R ^p = output space, under the equivalence relation induced by base change in state space; or in other words we study triples of matrices with real coefficients (F, G, H) of sizesn × n, n × m, p × n respectively, under the action(F, G, H.) →(TFT ^?1,TG, HT ^?1) ofGL _n (R), the group of invertible realn × n matrices. One of the central questions studied is: “do there exist continuous canonical forms for this equivalence relation?”. After various trivial obstructions to the existence of such forms have been removed the answer is very roughly: no ifm ≥ 2, p ≥ 2, yes ifm = 1, orp = 1. For a precise statement cf. theorem 1.7. Existence or nonexistence of continuous canonical forms is related to the existence of a universal family of real linear dynamical systems. More precisely continuous canonical forms exist if such a universal family exists and if the underlying vector bundle of this family is the trivial vector bundle. In the case studied we show that a universal family in the appropriate sense does exist. The methods used are purely (differential) topological and in particular do not involve any algebraic geometry. There is a corresponding algebraic theory over any fieldk instead ofR which is the subject of part III of this series of papers.     

A class of boolean functions with linear combinational complexity

In this paper we investigate the combinational complexity of Boolean functions satisfying a certain property, ⁿ_k,m. A function of n variables has the ⁿ_k,m property if there are at least m functions obtainable from each way of restricting it to a subset of n - - k variables. We show that the complexity of a ⁿ_3,5 function is no less than , and this bound cannot be much improved. Further, we find that for each k, there are ⁿ_k,2^k functions with complexity linear in n.     

A generalization of concavity for finite differences

The concept of concavity is generalized to discrete functions, u, satisfying the n^th-order difference inequality, (−1)^n−kΔⁿu(m) ≥ 0, M = 0, 1,..., N and the homogeneous boundary conditions, u(0) = … = u(k−1) = 0, u(N + k + 1) = … = u(N + n) = 0 for some k “1, …, n − 1”. A piecewise polynomial is constructed which bounds u below. The piecewise polynomial is employed to obtain a positive lower bound on u(m) for m = k, …, N + k, where the lower bound is proportional to the supremum of u. An analogous bound is obtained for a related Green's function.     

Stability problems in using state variable feedback to produce a servomechanism of specified type number

The problem of constructing a Hurwitz polynomial Â( s) of degree n, under the condition that the coefficients up to and including that of 8^m?1 are given, is discussed, Root locus arguments are used to establish necessary and sufficient conditions for stabilizability with m = l, 2, 3 and sufficient conditions for m > 3. A Routh array approach yields necessary and sufficient conditions for m = 4 and a general method of attack for m > 4 The origin of the problem (in the design of tracking servo-mechanisms) is explained, and a procedure for producing a system with specified type number is outlined.     

Quadratic Lower Bound for Permanent Vs. Determinant in any Characteristic

In Valiant’s theory of arithmetic complexity, the classes VP and VNP are analogs of P and NP. A fundamental problem concerning these classes is the Permanent and Determinant Problem: Given a field \mathbbF{\mathbb{F}} of characteristic ≠ 2, and an integer n, what is the minimum m such that the permanent of an n × n matrix X = (x_ij) can be expressed as a determinant of an m × m matrix, where the entries of the determinant matrix are affine linear functions of x_ij ’s, and the equality is in \mathbbF[X]{\mathbb{F}}[{\bf X}]. Mignon and Ressayre (2004) proved a quadratic lower bound m = W(n²)m = \Omega(n^{2}) for fields of characteristic 0. We extend the Mignon–Ressayre quadratic lower bound to all fields of characteristic ≠ 2.     

ALOGTIME and a conjecture of S.A. Cook

Usingsequential, machine-independent characterization of theparallel complexity classesAC ^k andNC ^k , we establish the following conjecture of S.A. Cook. There is a free variable equational logicALV with the property thatif f, g are function symbols forALOGTIME computable functions for which f=g is provable inALV, then there are polynomial size Frege proofs for the infinite family {|f=g| _m ⁿ :n, m} of propositional tautologies. Here, the propositional formula |f=g| _m ⁿ expresses the equality off andg on inputs of length at mostn, provided that the function values are of length at mostm. We establish a related result with constant formula-depth polynomial size Frege proofs for a systemAV related to uniformAC ⁰ functions.Part of this research supported by NSF Grant # DCR-860615. Extended abstract of this paper appeared in theIEEE Proc. of Logic in Computer Science, Philadelphia (June 1990).     

Asymmetric multi-party quantum state sharing of an arbitrary m-qubit state

We present a scheme for asymmetric multi-party quantum state sharing of an arbitrary m-qubit state with n agents. The sender Alice first shares m − 1 Bell states and one n + 1-particle Greenberger–Horne–Zeilinger state with n agents, where the agent Bob, who is designated to recover the original m-qubit state, just keeps m particles and other agents (all controllers) n − 1 particles, that is, each controller only holds one particle in hand. Subsequently, Alice performs m Bell-basis measurements on her 2m particles and each controller only need take a single-particle measurement on his particle with the basis X. Finally, Bob can recover the original m-qubit state with the corresponding local unitary operations according to Alice and all controllers’ measurement results. Its intrinsic efficiency for qubits approaches 100%, and the total efficiency really approaches the maximal value, which is higher than those of the known symmetric schemes.     

A General Stochastic Programming Problem

Stochastic programming problems appear when we make decisions in situations with uncertainty and risk, when any action has an ambiguous outcome and to each solution x = (x₁ …, x_n) it is possible to associate certain indicators fⁱ (x, ω), i = 1, …, m, that depend on x and on the state of nature ω, which is an element of the probabilistic space (Ω, A, P).

Since for any x the value of the objective function f ¹ (x, ω) and of the constraints functions f(x, ω), i = 2,… m, will depend on the realization ω, we have great freedom in determining the feasible and the optimal solutions in stochastic programming problems; for example, deciding whether they should be deterministic or have random solutions.     

Symbolic decision procedure for termination of linear programs

Tiwari proved that the termination of a class of linear programs is decidable in Tiwari (Proceedings of CAV’04. Lecture notes in computer science, vol 3114, pp 70–82, 2004). The decision procedure proposed therein depends on the computation of Jordan forms. Thus, people may draw a wrong conclusion from this procedure, if they simply apply floating-point computation to compute Jordan forms. In this paper, we first use an example to explain this problem, and then present a symbolic implementation of the decision procedure. Thus, the rounding error problem is therefore avoided. Moreover, we also show that the symbolic decision procedure is as efficient as the numerical one given in Tiwari (Proceedings of CAV’04. Lecture notes in computer science, vol 3114, pp 70–82, 2004). The complexity of former is max{O(n ⁶), O(n ^m+3)}, while that of the latter is O(n ^m+3), where n is the number of variables of the program and m is the number of its Boolean conditions. In addition, for the case when the characteristic polynomial of the assignment matrix is irreducible, we design a more efficient symbolic algorithm whose complexity is max(O(n ⁶), O(mn ³)).