Reconstruction of a word from a multiset of its factors

Let be the multiset containing all factors of w of length k including repetitions. One of the main results is that if for all , then w=v. The bound is optimal; however we will also show that if for all , then w and v are structurally similar.     

The global existence of nonlinear observers with linear error dynamics: A topological point of view

In this paper we show that under suitable assumptions, there exists a global homeomorphism Ψ(=Φ^-1) of which maps a nonlinear system onto a linear system with output injection . Thus, an observer for state x can be directly constructed as , which is a generalized version of Luenberger observer. An important feature of the obtained result is that there is no need to find the corresponding change of coordinates Ψ explicitly, which is different from current various existing approaches.     

Polyomino coloring and complex numbers

Usually polyominoes are represented as subsets of the lattice . In this paper we study a representation of polyominoes by Gaussian integers. Polyomino is represented by the set

Then we consider functions of type from the set of all polyominoes to an abelian group G, given by , where v is prime in (N(v) is the norm of v). Using the arithmetic of the ring we find necessary and sufficient conditions for such a function to be a coloring map.     

Minimality considerations for graph energy over a class of graphs

Let G be a graph on n vertices, and let CHP(G;λ) be the characteristic polynomial of its adjacency matrix A(G). All n roots of CHP(G;λ), denoted by , are called to be its eigenvalues. The energy E(G) of a graph G, is the sum of absolute values of all eigenvalues, namely, . Let be the set of n-vertex unicyclic graphs, the graphs with n vertices and n edges. A fully loaded unicyclic graph is a unicyclic graph taken from with the property that there exists no vertex with degree less than 3 in its unique cycle. Let be the set of fully loaded unicyclic graphs. In this article, the graphs in with minimal and second-minimal energies are uniquely determined, respectively.     

Robustness of exponential stability of a class of stochastic functional differential equations with infinite delay

We regard the stochastic functional differential equation with infinite delay as the result of the effects of stochastic perturbation to the deterministic functional differential equation , where is defined by x_t(θ)=x(t+θ),θ(−∞,0]. We assume that the deterministic system with infinite delay is exponentially stable. In this paper, we shall characterize how much the stochastic perturbation can bear such that the corresponding stochastic functional differential system still remains exponentially stable.     

Rewrite-Based Decision Procedures

The rewrite-based approach to satisfiability modulo theories consists of using generic theorem-proving strategies for first-order logic with equality. If one can prove that an inference system generates finitely many clauses from the presentation of a theory and a finite set of ground unit clauses, then any fair strategy based on that system can be used as a -satisfiability procedure. In this paper, we introduce a set of sufficient conditions to generalize the entire framework of rewrite-based -satisfiability procedures to rewrite-based -decision procedures. These conditions, collectively termed subterm-inactivity, will allow us to obtain rewrite-based -decision procedures for several theories, namely those of equality with uninterpreted functions, arrays with or without extensionality and two of its extensions, finite sets with extensionality and recursive data structures.     

On systems of word equations with simple loop sets

Consider the infinite system S of word equations

For each , let T_k be the subsystem of S given by i{k,k+1,k+2}. We prove two properties of the above system.

(1) Let k≥1. If φ is a solution of T_k such that primitive roots of are of equal length, as well as primitive roots of , then φ is a solution of the whole S.

(2) If n=1 then, for any k≥2, a solution φ of T_k is also a solution of S.

Structural properties of oracle classes

Denote by the class of oracles relative to which (collapsing oracles), and by the class of oracles relative to which (separating oracles). We present structural results on and . Using a diagonalization argument, we show that neither nor is closed under disjoint union, also known as join. We show that this implies that neither nor is closed under union, intersection, or symmetric difference. Consequently , the first level of the extended low hierarchy, is not closed under join.     

Computation of bases of free modules over the Weyl algebras

A well-known result due to J.T. Stafford asserts that a stably free left module M over the Weyl algebras D=A_n(k) or B_n(k)–where k is a field of characteristic 0–with is free. The purpose of this paper is to present a new constructive proof of this result as well as an effective algorithm for the computation of bases of M. This algorithm, based on the new constructive proofs [Hillebrand, A., Schmale, W., 2001. Towards an effective version of a theorem of Stafford. J. Symbolic Comput. 32, 699–716; Leykin, A., 2004. Algorithmic proofs of two theorems of Stafford. J. Symbolic Comput. 38, 1535–1550] of J.T. Stafford’s result on the number of generators of left ideals of D, performs Gaussian elimination on the formal adjoint of the presentation matrix of M. We show that J.T. Stafford’s result is a particular case of a more general one asserting that a stably free left D-module M with is free, where denotes the stable rank of a ring D. This result is constructive if the stability of unimodular vectors with entries in D can be tested. Finally, an algorithm which computes the left projective dimension of a general left D-module M defined by means of a finite free resolution is presented. It allows us to check whether or not the left D-module M is stably free.     

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.