Explicit expressions for cascade factorization of generalnonminimum phase systems

Explicit expressions for two different cascade factorizations of any detectable left invertible nonminimum phase systems are given. The first one is a well known minimum phase/all-pass factorization by which all nonminimum phase zeros of a transfer function G(s) are collected into an all-pass factor V(s), and G (s) is written G_m(s)V$ where G_ms is considered as a minimum phase image of G(s). The second one is a new cascade factorization by which G(s) is rewritten as G_M( s)U(s) where U(s) collects all `awkward' zeros including all nonminimum phase zeros of G( s). Both G_m(s) and G_M(s) retain the given infinite zero structure of G(s). Further properties of G _m(s), G_M(s), and U (s) are discussed. These factorizations are useful in several applications including loop transfer recovery     

Distributed detection with consulting sensors and communicationcost

The problem of distributed detection with consulting sensors in the presence of communication cost associated with any exchange of information (consultation) between sensors is considered. The system considered has two sensors, S1 and S2; S1 is the primary sensor responsible for the final decision u₀ , and S2 is a consulting sensor capable of relaying its decision u₂ to S1 when requested by S 1. The final decision u₀ is either based on the raw data available to S1 only, or, under certain request conditions, also takes into account the decision u₂ of sensor S2. Random and nonrandom request schemes are analyzed and numerical results are presented and compared for Gaussian and slow-fading Rayleigh channels. For each decision-making scheme, an associated optimization problem is formulated whose solution is shown to satisfy certain set design criteria that the authors consider essential for sensor fusion     

Decentralized stabilization and pole assignment for general propersystems

Considered is the problem of finding existence conditions and a controller synthesis procedure, using decentralized control, for assigning the poles of a linear time-invariant proper system described by a state-space model (C, A, B, D), where no assumption is made regarding the structure of D. This problem has direct application to the decentralized stabilization problem, decentralized robust servomechanism problem, etc., and is a nontrivial extension to the standard decentralized problem where it is assumed that the direct feedthrough terms either are absent or have a block-diagonal structure     

On a weaker notion of controllability of a language K withrespect to a language L

A necessary and sufficient condition for a prefix-closed language K⊆Σ* to be controllable with respect to another prefix-closed language L⊆Σ* is that K⊆ L. A weaker notion of controllability where it is not required that K⊆L is considered here. If L is the prefix-closed language generated by a plant automaton G, then essentially there exists a supervisor Θ that is complete with respect to G such that L(Θ|G)=K ∩ L if and only if K is weakly controllable with respect to L. For an arbitrary modeling formalism it is shown that the inclusion problem is reducible to the problem of deciding the weaker notion of controllability. Therefore, removing the requirement that K ⊆ L from the original definition of controllability does not help the situation from a decidability viewpoint. This observation is then used to identify modeling formalisms that are not viable for supervisory control of the untimed behaviors of discrete-event dynamic systems     

Output stabilizability of discrete-event dynamic systems

The authors investigate the problem of designing stabilizing feedback compensators for discrete-event dynamic systems (DEDS) modeled as finite-state automata in which some transition events are controllable and some events are observed. The problem of output stabilization is defined as the construction of a compensator such that all state trajectories in the closed-loop system go through a given set E infinitely often. The authors also define a stronger notion of output stabilizability which requires that the state not only pass through E infinitely often but that the set of instants when the state is in E and one knows it is in E is also infinite. Necessary and sufficient conditions are presented for both notions. The authors also introduce and characterize a notion of resiliency that corresponds to the system being able to recover from observation errors. In addition, they provide some general bounds for the algorithms considered and discuss several conditions under which far smaller bounds can be achieved     

Parallel binary search

Two arrays of numbers sorted in nondecreasing order are given: an array A of size n and an array B of size m, where n<m. It is required to determine, for every element of A, the smallest element of B (if one exists) that is larger than or equal to it. It is shown how to solve this problem on the EREW PRAM (exclusive-read exclusive-write parallel random-access machine) in O(logm logn/log log m) time using n processors. The solution is then extended to the case in which fewer than n processors are available. This yields an EREW PRAM algorithm for the problem whose cost is O(n log m, which is O(m)) for n⩽m/log m. It is shown how the solution obtained leads to an improved parallel merging algorithm     

Simultaneous stabilization of single-input single-output discretetime systems

The problem of finding one compensator which simultaneously stabilizes a family of single-input-single-output (SISO) discrete-time plants is considered. The family of plants is described by the transfer functions {Pz, q): q∈Q}, which are generated via a z-transformation. A number of assumptions describing the set of allowable plants are then given. These assumptions include some regularity conditions on the plants and a minimum-phase requirement. The satisfaction of these assumptions guarantees the existence of a strictly proper stable compensator C(z) for simultaneous stabilization. An iterative computation method is provided for control design     

A class of weak Kharitonov regions for robust stability of linearuncertain systems

Kharitonov's theorems are generalized to the problem of so-called weak Kharitonov regions for robust stability of linear uncertain systems. Given a polytope of (characteristic) polynomials P and a stability region D in the complex plane, P is called D-stable if the zeros of every polynomial in P are contained in D. It is of interest to know whether the D-stability of the vertices of P implies the D-stability of P. A simple approach is developed which unifies and generalizes many known results on this problem     

Solution to Morgan's problem

A necessary and sufficient condition is presented for the solution of the row-by-row decoupling problem (known as Morgan's problem) in the general case, that is, without any restrictive assumption added to the system to the feedback law u=Fx+Gy (G may be noninvertible). This is a structural condition in terms of invariant lists of integers which are easily computable from a given state realization of the system. These integers are the infinite zero orders (Morse's list I₄) and the essential orders of the system, which only depend on the input-output behavior, and Morse's list I₂ of the system, which depends on the choice of a particular state realization     

Properties of optimal hop-by-hop allocation policies in networkswith multiple transmitters and linear equal holding costs

Flow control between one receiving node and its adjacent transmitting nodes in a computer network is modeled as a Markov decision problem. By deriving several qualitative properties of an optimal allocation policy, it is shown that finding dynamic optimal allocations for only T states suffices to completely describe an optimal allocation policy. When the number of transmitters M=2, for all but one of the T states there are only two allocations that are candidates for optimality. It is desirable to extend this property to M>2. However, it appears that the technique used for M =2 does not generalize to M>2     

Network communication in edge-colored graphs: gossiping

A mechanism for scheduling communications in a network in which individuals exchange information periodically according to a fixed schedule is presented. A proper k edge-coloring of the network is considered to be a schedule of allowed communications such that an edge of color i can be used only at times i modulo k. Within this communication scheduling mechanism, the information exchange problem known as gossiping is considered. It is proved that there is a proper k edge-coloring such that gossip can be completed in a path of n edges in a certain time for n⩾k⩾1. Gossip can not be completed in such a path any earlier under any proper k edge-coloring. In any tree of bounded degree Δ and diameter d, gossip can be completed under a proper Δ edge-coloring in time (Δ-1)d +1. In a k edge-colored cycle of n vertices, other time requirements of gossip are determined     

Image representation by sign information

Image representation by sign data in its most general context is considered for the case when f is a two-dimensional signal. The authors study conditions under which f is determined by its sign or, in other words, by its quantization to 1 bit of information. This study is carried out in two different directions. First, theoretical results are presented that set an algebraic condition under which real zero-crossings uniquely specify a band-limited image. An interesting paradigm arising in theoretical computer vision is then posed: are the zero-crossing of f convolved with a Laplacian-of-a-Gaussian at a single channel enough for unambiguously representing f? Second, the problem of the completeness of the representation when the position of the zero-crossings is known only approximately is addressed. It is shown that when sign(f) is sampled, significant ambiguities are introduced in the representation. Experimental results are presented which were obtained from an iterative algorithm devised to reconstruct real images from multiscale sign information     

An efficient distributed protocol for finding shortest paths innetworks with negative weights

The design is discussed of distributed algorithms for the single-source shortest-path problem to run on an asynchronous directed network in which some of the edges may be associated with negative weights, and thus in which a cycle of negative total weight may also exist. The only existing solution in the literature for this problem is due to K.M. Chandy and J. Misra (1982), and it has, in the worst case, an unbounded message complexity. A synchronous version of the Chandy-Misra algorithm is described and studied, and it is proved that for a network with m edges and n nodes, the worst case message and time complexities of this algorithm are O(mn ) and O(n), respectively. This algorithm is then combined with an efficient synchronizer to yield an asynchronous protocol that retains the same message and time complexities     

Decoupling of square singular systems via proportional statefeedback

Necessary and sufficient conditions for the decoupling of a solvable square singular system Ex˙(t)=Ax(t)+Bu(t ) with output y(t)=Dx(t), through an admissible control law of the form u(t)=Kx(t)+Hr(t) where H is a square nonsingular matrix. It has been shown that for a given singular system that satisfies these conditions, a propagational state feedback exists for which the system's transfer function is a diagonal, nonsingular, and proper rational matrix. The proofs of the main results are constructive and provide a procedure for computing an appropriate proportional state feedback     

Feedback control for linear time-invariant systems with state andcontrol bounds in the presence of disturbances

The problem of the stabilizing linear control synthesis in the presence of state and input bounds for systems with additive unknown disturbances is considered. The only information required about the disturbances is a finite convex polyhedral bound. Discrete- and continuous-time systems are considered. The property of positive D -invariance of a region is introduced, and it is proved that a solution of the problem is achieved by the selection of a polyhedral set S and the computation of a feedback matrix K such that S is positively D-invariant for the closed-loop system. It is shown that if polyhedral sets are considered, the solution involves simple linear programming algorithms. However, the procedure suggested requires a great amount of computational work offline if the state-space dimension is large, because the feedback matrix K is obtained as a solution of a large set of linear inequalities. All of the vertices of S are required     

An approach for pole assignment in singular systems

Pole assignment in a singular system Edx/dt=Ax+Bu is discussed. It is shown that the problem of assigning the roots of det(sE-(A +BF)) by applying a proportional feedback u=Fx+r in a given singular system is equivalent to the problem of pole assignment of an appropriate regular system. An immediate application of this result is that procedures and computational algorithms that were originally developed for assigning eigenvalues in regular systems become useful tools for pole assignment in singular systems. The approach provides a useful tool for the combined problem of eliminating impulsive behavior and stabilizing a singular system     

Optimal resilient distributed algorithms for ring election

The problem of electing a leader in a dynamic ring in which processors are permitted to fail and recover during election is discussed. It is shown that &thetas;(n log n+k_r) messages, counting only messages sent by functional processors, are necessary and sufficient for dynamic ring election, where k_r is the number of processor recoveries experienced     

Computational observer design techniques for linear systems withunknown inputs using the concept of transmission zeros

Computational observer design techniques for linear systems subject to unknown inputs are presented. Complete and intuitive geometric conditions for the solution of the problem which result in design matrix equations are provided. These design equations are solved in a computationally efficient way. The synthesis of the reduced-order observer takes full advantage of the concept of transmission zeros. In particular, the necessary and sufficient conditions obtained are given in terms of the transmission zeros of the triple (A,D, C)     

Simultaneous controller design for linear time-invariant systems

The use of generalized sampled-data hold functions (GSHF) in the problem of simultaneous controller design for linear time-invariant plants is discussed. This problem can be stated as follows: given plants P₁, P₂, . . ., P_N , find a controller C which achieves not only simultaneous stability, but also simultaneous optimal performance in the N given systems. By this, it is meant that C must optimize an overall cost function reflecting the closed-loop performance of each plant when it is regulated by C. The problem is solved in three aspects: simultaneous stabilization, simultaneous optimal quadratic performance, and simultaneous pole assignment in combination with simultaneous intersampling performance     

Geometric theory for the singular Roesser model

(A,E,B)-invariant and (E,A ,B)-invariant subspaces for the two-dimensional singular Roesser model are investigated. These subspaces are related to the existence of the solutions when the boundary conditions are in these subspaces. Also, the existence of a solution sequence in certain subspaces derived from the invariant subspaces is shown. The boundary conditions that appear in the solution when some semistates in the solution are restricted to zero are also investigated