Cycles embedding in exchanged hypercubes

The exchanged hypercube EH(s,t), proposed by Loh et al., is obtained by systematically removing links from a binary hypercube. This paper investigates important properties related to embedding cycles into the exchanged hypercube EH(s,t). The authors show that EH(1,t) and EH(2,2) are not bipancyclic, but EH(s,t) (2?s?t) except EH(2,2) is bipancyclic and EH(s,t) (3?s?t) is vertex-bipancyclic. Moreover, every edge of EH(s,t) (2?s?t) lies on an even l-cycle where 8?l?²s+t+1.     

An Efficient Algorithm for the k-Pairwise Disjoint Paths Problem in Hypercubes

A graph G(V, E) (|V|⩾2k) satisfies property A_k if, given k pairs of distinct nodes (s₁, t₁), …, (s_k, t_k) of V(G), there are k mutually node-disjoint paths, one connecting s_i and t_i for each i, 1⩽i⩽k. A necessary condition for any graph to satisfy A_k is that it is (2k−1)-connected. Hypercubes are important interconnection topologies for parallel computation and communication networks. It has been known that hypercubes of dimension n (which are n-connected) satisfy A_⌈n/2⌉. In this paper we give an algorithm which, given k=⌈n/2⌉ pairs of distinct nodes (s₁, t₁), …, (s_k, t_k) in the n-dimensional hypercube, finds the k disjoint paths of length at most n+⌈log n⌉+1 in O(n² log* n) time.     

Recovering the initial state of an infinite-dimensional system using observers

Let A be the generator of a strongly continuous semigroup T on the Hilbert space X, and let C be a linear operator from D(A) to another Hilbert space Y (possibly unbounded with respect to X, not necessarily admissible). We consider the problem of estimating the initial state z₀∈D(A) (with respect to the norm of X) from the output function y(t)=CT_tz₀, given for all t in a bounded interval [0,τ]. We introduce the concepts of estimatability and backward estimatability for (A,C) (in a more general way than currently available in the literature), we introduce forward and backward observers, and we provide an iterative algorithm for estimating z₀ from y. This algorithm generalizes various algorithms proposed recently for specific classes of systems and it is an attractive alternative to methods based on inverting the Gramian. Our results lead also to a very general formulation of Russell’s principle, i.e., estimatability and backward estimatability imply exact observability. This general formulation of the principle does not require T to be invertible. We illustrate our estimation algorithms on systems described by wave and Schrödinger equations, and we provide results from numerical simulations.     

Fixed rank solutions of the matrix equation with statistical applications

By applying the canonical correlation decomposition of matrix pairs, the general fixed rank least square solutions of matrix equation Xβ=Y are derived. As statistical applications, an algorithm for computing the least square estimator of the multivariate reduced rank regression model Y=Xβ+?, r(β)=t is given.     

An iterative algorithm for solving a class of matrix equations

In this paper, an iterative algorithm is presented to solve the Sylvester and Lyapunov matrix equations. By this iterative algorithm, for any initial matrix X1, a solution X＊ can be obtained within finite iteration steps in the absence of roundoff errors. Some examples illustrate that this algorithm is very efficient and better than that of [ 1 ] and [2].     

Existence of solutions to singular integral equations

Nonnegative solutions are established for singular integral equations of the form y(t) = h(t) + ∫^T₀ k(t, s)f(s, y(s)) ds for t ∈ [0, T]. Here f may be singular at y = 0.     

Time-series decomposition and forecasting

Any stationary time-series can be decomposed by means of an optimization operator, called the ζ-optimator, into several components (the time-series){Y _t ⁱ}, i =1,2,…, p, such that the first component {V _t ⁱ} t = 1,2,…,v is a smooth process having a larger autocorrelation in comparison with the original process {Y _t}, i.e. ρ_vi > ρ_y. Usually only a few such components are sufficient for approximating the time-series with good accuracy. The ζ-optimator involves a shape parameter a, so the decomposition is unique provided that a. is fixed. Since the component {V _t ¹} involves much of the useful information it can be used for computing predictors for control purposes. Thus, given the observations Y_v, Y_v-1, Y_v-2,…, a predictor of Y_v+1 is ρ_vi V _v ¹ (q) where, V_v ¹(q) = qY^v + q(1-q)² Y_v-2, …, the weights q(1-q)^r, r=0,1,2,…, decreasing rapidly as q = q(α) ε (0,1) Further, one may choose q rather than choosing α, since q(α) is a one-one mapping. Once q is fixed, the predictor ρ_v1 V _v ¹(q) is obtained in a straightforward way by using the formula above. It is shown that ρ_v1 V _v ¹(q) converges to the best predictor as α → 0. Some examples are worked out, illustrating both the decomposition and the forecasting procedures.     

特殊权限下权重不同参与者的广义门限方案

在秘密共享案中,一般集中于（n,t）门限秘密共享方案的研究。文中给出的是具有特殊权限的参与者权重不同的（m+n₁+n₂+…+n_l,t+1+1+…+1）门限秘密共享方案和（m+n₁+…+n_l,t+t₁+…+t_l）门限秘密共享方案,它们是（m+n,t+1）门限秘密共享方案的推广形式。基于中国剩余定理分别给出具有特殊权限的且参与者具有不同权重的（m+n₁+n₂+…+n_l,t+1+1+…+1）门限秘密共享方案和（m+n₁+…+n_l,t+t₁+…+t_l）门限秘密共享方案。     

Computing an st-numbering

Lempel, Even and Cederbaum proved the following result: Given any edge {st} in a biconnected graph G with n vertices, the vertices of G can be numbered from 1 to n so that vertex s receives number 1, vertex t receives number n, and any vertex except s and t is adjacent both to a lower-numbered and to a higher-numbered vertex (we call such a numbering an st-numbering for G). They used this result in an efficient algorithm for planarity-testing. Here we provide a linear-time algorithm for computing an st-numbering for any biconnected graph. This algorithm can be combined with some new results by Booth and Lueker to provide a linear-time implementation of the Lempel-Even-Cederbaum planarity-testing algorithm.     

A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings

Let X and Y be two strings of lengths n and m, respectively, and k and l, respectively, be the numbers of runs in their corresponding run-length encoded forms. We propose a simple algorithm for computing the longest common subsequence of two given strings X and Y in O(kl+min{p₁,p₂}) time, where p₁ and p₂ denote the numbers of elements in the bottom and right boundaries of the matched blocks, respectively. It improves the previously known time bound O(min{nl,km}) and outperforms the time bounds O(kllogkl) or O((k+l+q)log(k+l+q)) for some cases, where q denotes the number of matched blocks.     

Fault diagnosis in loop-connected systems

The paper considers fault diagnosis in a large system comprising a collection of small subsystems or units which can test one another for the existence of a faulty condition. If subsystem α is not faulty and tests subsystem β, a correct indication of the status of β is obtained; if α is faulty, the test outcome contains meaningless information. A particular form of interconnection is examined. For a system with n units u_o,u₁,…,u_{n ? 1}, for each i unit u_i tests u_{i + 1},u_{i + 2},…,u_{i + A} (modulo n arithmetic being understood), where A is a preselected integer. If t is the maximum number of faulty units, we show that when t ? A, all faults are immediately diagnosable if n ? 2t + 1; we also show that when t ? A, at least A faults can be diagnosed if and only if n ? s(t ? As) + t + A + 1, where s is the integer which maximizes the quadratic function f(x) = x(t ? Ax) of the integer variable x.     

An iterative algorithm for solving a pair of matrix equations over generalized centro-symmetric matrices

A matrix is said to be a symmetric orthogonal matrix if . A matrix is said to be generalized centro-symmetric (generalized central anti-symmetric) with respect to P, if A=PAP (A=−PAP). The generalized centro-symmetric matrices have wide applications in information theory, linear estimate theory and numerical analysis. In this paper, we propose a new iterative algorithm to compute a generalized centro-symmetric solution of the linear matrix equations . We show, when the matrix equations are consistent over generalized centro-symmetric matrix Y, for any initial generalized centro-symmetric matrix Y₁, the sequence {Y_k} generated by the introduced algorithm converges to a generalized centro-symmetric solution of matrix equations . The least Frobenius norm generalized centro-symmetric solution can be derived when a special initial generalized centro-symmetric matrix is chosen. Furthermore, the optimal approximation generalized centro-symmetric solution to a given generalized centro-symmetric matrix can be derived. Several numerical examples are given to show the efficiency of the presented method.     

Application of the method of incremental coefficients (MIC) algorithm to inertial systems

Detection of two of the most dominant errors in an inertial navigation system, the schulering and the earth-rate error components, are studied using the Kalman filtering technique. Dynamics of the inertial system are modelled by a combination of two coupled oscillators subjected to additive noise, by using the state variables method, contrary to the technique used in the literature using equations of classical mechanics.

In this paper the utilization of the method of incremental coefficients (MIC) algorithm is presented. The variance equation (appearing in the filter) is given by the differential equation in P ₁₂(t, t ₀). (The matrices P _ij (t, t ₀) belong to the MIC algorithm) ; and it was solved by the semi-group property of this algorithm.

Both schemes, non-adaptive and adaptive, from an accuracy standpoint are simulated. It is shown that using an adaptive filter approach, the Kalman filter is able to filter out the schulering and the earth-rate oscillations to an acceptable level.

The controllability matrix in the linear regulator problem (or the observability matrix in the filter problem) is given by P ₂₁(t ₀, t) matrix, and also P ₁₁(t, t ₀) gives the impulse response of the optimal filter. The duality of the MIC algorithm has been stated.     

Optimal evaluation of generalized Euler angles with applications to control

Given two linearly independent matrices in so(3), Z₁ and Z₂, every rotation matrix, X_f∈SO(3), can be written as the product of alternate elements from the one-dimensional subgroups corresponding to Z₁ and Z₂, namely X_f=e^Z₁t₁e^Z₂t₂e^Z₁t₃?e^Z₁t_s. The parameters t_i, i=1,…,s are called Generalized Euler Angles. In this paper, the minimum number of factors required for the factorization of X_f∈SO(3), as a function of X_f, is evaluated. An algorithm is given to determine the generalized Euler angles, in the optimal factorization. The results can be applied to the bang-bang control, with minimum number of switches, of some classical and quantum systems.     

Scheduling on machines with variable service rates

This paper deals with scheduling on single and parallel machines where the service rate of a machine remains constant while a job is being processed and is changed upon its completion. Associated with machine M_l there is a vector of service factors α_l = (α_1l, α_2l,…,); it is described as cyclic of order k iff α₁(k) = (α_1l,…, α_kl, α_1l,…,). Processing job J_i in the jth position on M_l consumes α_jlt_i time units. We present an 0(n log n) algorithm for l/vsr/C_max and an 0(n^m log n) algorithm for Pm/vsr/∑ C_i, m ⩾ 1. It is proved that l/vsr/L_max is NP-hard even for a monotone non-decreasing or a cyclic series of service factors, thus l/vsr/δ, δ_ϵ {∑ U_i, ∑ T_i} are NP-hard as well. Finally, efficiently solvable special cases of l/vsr/δ, δ_ϵ{L_max, ∑ U_i, ∑ T_i} are studied.     

Texture classification using features derived from random field models

This paper presents a new feature extraction method for classifying a texture image into one of the l possible classes C_i, i=1,…,l. It is assumed that the given M × M image characterized by a set of intensity levels, {y(s₁,S₂), 0≤s_s,s₂≤M?1}, is a realization of an underlying random field model, known as the Simultaneous Autoregressive Model (SAR). This model is characterized by a set of parameters φ whose probability density function p_i(φ), depends on the class to which the image belongs. First it is shown that the maximum likelihood estimate (M.L.E.) $\text{φ}{}^1$, of φ is an appropriate feature vector for classification purposes. The optimum Bayes classifier which minimizes the average probability of classification error, is then designed using $\text{φ}{}^1$. Finally the efficiency of the feature vector is demonstrated through experimental results obtained with some natural texture data and a simpler quadratic mean classifier.     

An effective algorithm for string correction using generalized edit distances—I. Description of the algorithm and its optimality

This paper deals with the problem of estimating a transmitted string X_s from the corresponding received string Y, which is a noisy version of X_s. We assume that Y contains any number of substitution, insertion, and deletion errors, and that no two consecutive symbols of X_s were deleted in transmission. We have shown that for channels which cause independent errors, and whose error probabilities exceed those of noisy strings studied in the literature [12], at least 99.5% of the erroneous strings will not contain two consecutive deletion errors. The best estimate X⁺ of X_s is defined as that element of H which minimizes the generalized Levenshtein distance $\text{D(}\text{X}\text{Y}\text{)}$ between X and Y. Using dynamic programming principles, an algorithm is presented which yields X⁺ without computing individually the distances between every word of H and Y. Though this algorithm requires more memory, it can be shown that it is, in general, computationally less complex than all other existing algorithms which perform the same task.     

On the structure of binary feedforward inverses with delay 2

Let M‘=S(Mα,f)be a semi-input-memory finite automaton with input alphabet Y and output alphabet X.If X=Y={0,1},then M‘ is a feedforware inverse with delay 2 if and only if there exists a cycle c of state diagram of Mαsuch that f(y0,…,yc,λα（t)0 can be expressed in the form of f ^(1)(y0,…,yc-1,λα（t)) yc for any state t in C and y0,y1,…,yc in Y;or of f^(2)(y0,…,yc-2,λα（t)) yc-c for any state t in Cand y0,y1,…,yc in Y;or for any state t in Cand y0,y1,…yc,in Y,y0,y1…yc satisfies the D[t] condition.The socalled y0,y1…yc satisfying the D[t] condition is that:for some i,j,(i,j)∈{(1,2),(1,3),(2,1),(2,2),(3,1),(3,2)},there exists a (c 2-k)-ary function f^(k),k=1,2,3,such that the Equation(1)and Equation (2)hokl simultaneously for all y‘c-2,…,y‘c 1∈Y. Equation (1);f(y0,…,yc-i,y‘c-i 1,…y‘c,λα（t))=f^(j)(y0,…yc-i,λα（t）） y‘c-i 1 Equation (2):f(y1,…,yc-j 1,y‘c-j 2,…,y‘c 1,λα（t））=f^(j)(y1,…,yc-j 1,λα（t）） y‘c-j s where t=δα（t）and if (i,j)=(1,2)then one and only one of the following conditions C1 and C2 holds for all y‘c-1,y‘c,y‘c 1∈Y.Condition C1:there exists a c-ary function g^(1),such that f(y0,…,yc-2,y‘c-1,y‘c,λα（t））=g^(1),(y0,…,yc-2,λα（t）） y‘c-1( )y‘c;Condition C2:there exists a (c-1)-ary functiong g^(2)such that f(y1,…,yc-2,y‘c-1,y‘c,y‘c 1,λα（t））=g^(2)(y1,…,yc-2,λα（t）） y‘c-1 y‘c,where t=δα(t).     

A Simpler and More Efficient Algorithm for the Next-to-Shortest Path Problem

Given an undirected graph G=(V,E) with positive edge lengths and two vertices s and t, the next-to-shortest path problem is to find an st-path which length is minimum amongst all st-paths strictly longer than the shortest path length. In this paper we show that the problem can be solved in linear time if the distances from s and t to all other vertices are given. Particularly our new algorithm runs in O(|V|log|V|+|E|) time for general graphs, which improves the previous result of O(|V|²) time and takes only linear time for unweighted graphs, planar graphs, and graphs with positive integer edge lengths.