共查询到20条相似文献,搜索用时 31 毫秒
1.
Itai A. Kutten S. Wolfstahl Y. Zaks S. 《IEEE transactions on pattern analysis and machine intelligence》1990,16(4):415-420
The problem of distributed leader election in an asynchronous complete network, in the presence of faults that occurred prior to the execution of the election algorithm, is discussed. Failures of this type are encountered, for example, during a recovery from a crash in the network. For a network with n processors, k of which start the algorithm that uses at most O (n log k +n +kt ) messages is presented and shown to be optimal. An optimal algorithm for the case where the identities of the neighbors are known is also presented. It is noted that the order of the message complexity of a t -resilient algorithm is not always higher than that of a nonresilient one. The t -resilient algorithm is a systematic modification of an existing algorithm for a fault-free network 相似文献
2.
Helmbold D.P. McDowell C.E. 《Parallel and Distributed Systems, IEEE Transactions on》1990,1(2):250-256
A simple model of parallel computation which is capable of explaining speedups greater than n on n processors is presented. Necessary and sufficient conditions for these exceptional speedups are derived from the model. Several of the contradictory previous results relating to parallel speedup are resolved by using the model 相似文献
3.
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 相似文献
4.
Guang-Ren Duan 《Automatic Control, IEEE Transactions on》1993,38(2):276-280
Two new simple, complete, analytical, and restriction-free solutions with complete and explicit freedom of the matrix equation AV +BW =VF are proposed. Here [AB ] is known and is controllable, and F is in the Jordan form with arbitrary given eigenvalues. Based on the proposed solutions of this matrix equation, a complete parametric approach for eigenstructure assignment in linear systems via state feedback is proposed, and two new algorithms are presented. The proposed solutions of the matrix equation and the eigenstructure assignment result are generalizations of some previous results and are simpler and more effective 相似文献
5.
Linderbaum M. Bruckstein A. 《IEEE transactions on pattern analysis and machine intelligence》1993,15(9):949-953
A simple online algorithm for partitioning of a digital curve into digital straight-line segments of maximal length is given. The algorithm requires O (N ) time and O (1) space and is therefore optimal. Efficient representations of the digital segments are obtained as byproducts. The algorithm also solves a number-theoretical problem concerning nonhomogeneous spectra of numbers 相似文献
6.
Multiple-instruction multiple-data (MIMD) algorithms that use multiple processors to do median splitting, k -splitting and parallel splitting into t equal sections are presented. Both concurrent read, exclusive write (CREW) and exclusive read, exclusive write (EREW) versions of the algorithms are given. It is shown that a k -splitting problem can be easily converted into a median-splitting problem. Methods for finding multiple split points quickly and application of k -splitting to merging and sorting are discussed 相似文献
7.
Linear matrix equations in the ring of polynomials in n indeterminates (n -D ) are studied. General- and minimum-degree solutions are discussed. Simple and constructive, necessary and sufficient solvability conditions are derived. An algorithm to solve the equations with general n -D polynomial matrices is presented. It is based on elementary reductions in a greater ring of polynomials in one indeterminate, having as coefficients polynomial fractions in the other n -1 indeterminates, which makes the use of Euclidean division possible 相似文献
8.
The theorem states that every block square matrix satisfies its own m -D (m -dimensional, m ⩾1) matrix characteristic polynomial. The exact statement and a simple proof of this theorem are given. The theorem refers to a matrix A subdivided into m blocks, and hence having dimension at least m . The conclusion is that every square matrix A with dimension M satisfies several m -D characteristic matrix polynomials with degrees N 1 . . ., N m, such that N 1+ . . . +N m ⩽M 相似文献
9.
The problem of finding an internally stabilizing controller that minimizes a mixed H 2/H ∞ performance measure subject to an inequality constraint on the H ∞ norm of another closed-loop transfer function is considered. This problem can be interpreted and motivated as a problem of optimal nominal performance subject to a robust stability constraint. Both the state-feedback and output-feedback problems are considered. It is shown that in the state-feedback case one can come arbitrarily close to the optimal (even over full information controllers) mixed H 2/H ∞ performance measure using constant gain state feedback. Moreover, the state-feedback problem can be converted into a convex optimization problem over a bounded subset of (n ×n and n ×q , where n and q are, respectively, the state and input dimensions) real matrices. Using the central H ∞ estimator, it is shown that the output feedback problem can be reduced to a state-feedback problem. In this case, the dimension of the resulting controller does not exceed the dimension of the generalized plant 相似文献
10.
Necessary and sufficient criteria in the frequency domain for robust stability are given under the assumption that coefficients of a characteristic polynomial belong to a transformed l p-ball. Three cases are considered in detail: p =∞ (interval uncertainty), p =2 (ellipsoidal uncertainty), and p =1 (octahedral uncertainty). It is shown that frequency-domain-stability criteria are efficient when one deals with robust stability problems. The frequency-domain approach considered can be extended to various problems of robust stability 相似文献
11.
Bestul T. Davis L.S. 《IEEE transactions on pattern analysis and machine intelligence》1989,11(2):212-213
An algorithm for the computation of the histogram of limited-width (such as gray-level) values on a SIMD (single-instructions multiple-data) hypercube multiprocessor is proposed, which does not require the use of a general interconnection capability such as that on the connection machine. The computation of the complete histogram of n such values takes place in a series of log n steps, after which the histogram for value i can be found in the lowest-addressed processor whose address ends in i . The algorithm makes use of the association of suffixes of data values of increasing width with suffixes of processor addresses 相似文献
12.
The author analyzes the computational complexity of an algorithm by F.D. Groutage et al. (ibid., vol.AC-32, no.7, p.635-7, July 1987) for performing the transformation of a continuous transfer function to a discrete equivalent by a bilinear transformation. Groutage et al. defend their method by noting that their technique is not limited to the bilinear transformation. Rather, it can be extended to any higher-order integration rule (Simpson, Runge-Kutta, etc.), or to any higher-order expansion of the ln function. In general, using the method, s can be any appropriate mapping function s =f (z ) 相似文献
13.
Let φ(s ,a )=φ0(s ,a )+ a 1φ1(s )+a 2 φ2(s )+ . . .+a kφ k(s )=φ0(s )-q(s , a ) be a family of real polynomials in s , with coefficients that depend linearly on parameters a i which are confined in a k -dimensional hypercube Ωa . Let φ0(s ) be stable of degree n and the φi(s ) polynomials (i ⩾1) of degree less than n . A Nyquist argument shows that the family φ(s ) is stable if and only if the complex number φ0(j ω) lies outside the set of complex points -q (j ω,Ωa) for every real ω. In a previous paper (Automat. Contr. Conf., Atlanta, GA, 1988) the authors have shown that -q (j ω,Ωa ), the so-called `-q locus', is a 2k convex parpolygon. The regularity of this figure simplifies the stability test. In the present paper they again exploit this shape and show that to test for stability only a finite number of frequency checks need to be done; this number is polynomial in k , 0(k 3), and these critical frequencies correspond to the real nonnegative roots of some polynomials 相似文献
14.
The problem of tightly bounding and shaping the frequency responses of two objective functions T i(s )( i =1,2) associated with a closed-loop system is considered. It is proposed that an effective way of doing this is to minimize (or bound) the function max {∥T 1(s )∥ ∞, ∥T 2(s)∥∞} subject to internal stability of the closed-loop system. The problem is formulated as an H ∞ control problem, and an iterative solution is given 相似文献
15.
It is shown that for a given p (1<p ⩽n ), the n -cube network can tolerate up to p 2(n-p)-1 processor failures and remains connected provided that at most p neighbors of any nonfaulty processor are allowed to fail. This generalizes the result for p =n-1, obtained by A.-M Esfahanian (1989). It is also shown that the n -cube network with n ⩾5 remains connected provided that at most two neighbors of any processor are allowed to fail 相似文献
16.
Huang T.S. Faugeras O.D. 《IEEE transactions on pattern analysis and machine intelligence》1989,11(12):1310-1312
In the eight-point linear algorithm for determining 3D motion/structure from two perspective views using point correspondences, the E matrix plays a central role. The E matrix is defined as a skew-symmetrical matrix (containing the translation components) postmultiplied by a rotation matrix. The authors show that a necessary and sufficient condition for a 3×3 matrix to be so decomposable is that one of its singular values is zero and the other two are equal. Several other forms of this property are presented. Some applications are briefly described 相似文献
17.
《Automatic Control, IEEE Transactions on》1991,36(1):95-102
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 相似文献
18.
It is shown that there is a continuously parameterized family F of n -dimensional single-input single-output (SISO) stabilizable detectable linear system Σ(p ) which contains at least one realization of each reduced, strictly proper transfer function of McMillan degree not exceeding n . The parameterization map p →Σ(p ) is a polynomial function in 2n indeterminates from an open convex polyhedron in R 2n to the linear space of all SISO n -dimensional linear systems 相似文献
19.
The problem of determining whether a polytope P of n ×n matrices is D -stable-i.e. whether each point in P has all its eigenvalues in a given nonempty, open, convex, conjugate-symmetric subset D of the complex plane-is discussed. An approach which checks the D -stability of certain faces of P is used. In particular, for each D and n the smallest integer m such that D -stability of every m -dimensional face guarantees D -stability of P is determined. It is shown that, without further information describing the particular structure of a polytope, either (2n -4)-dimensional or (2n -2)-dimensional faces need to be checked for D -stability, depending on the structure of D . Thus more work needs to be done before a computationally tractable algorithm for checking D -stability can be devised 相似文献
20.
The one-dimensional system dx (t =bu (t )dt +(ct 2)1/2dW (t ), where b (≠0) and c (⩾0) are real constants and W (t ) is a standard Brownian motion, is considered. The aim is to obtain the control u * that minimizes the expected value of a cost function with terminal cost equal to 0 or +∞ depending on whether the survival time in a given region is at least equal to or less than a fixed time 相似文献