Characterization of 2<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>-periodic binary sequences with fixed 2-error or 3-error linear complexity

The linear complexity of sequences is an important measure of the cryptographic strength of key streams used in stream ciphers. The instability of linear complexity caused by changing a few symbols of sequences can be measured using k-error linear complexity. In their SETA 2006 paper, Fu et al. (SETA, pp. 88–103, 2006) studied the linear complexity and the 1-error linear complexity of 2 ⁿ -periodic binary sequences to characterize such sequences with fixed 1-error linear complexity. In this paper we study the linear complexity and the k-error linear complexity of 2 ⁿ -periodic binary sequences in a more general setting using a combination of algebraic, combinatorial, and algorithmic methods. This approach allows us to characterize 2 ⁿ -periodic binary sequences with fixed 2- or 3-error linear complexity. Using this characterization we obtain the counting function for the number of 2 ⁿ -periodic binary sequences with fixed k-error linear complexity for k = 2 and 3.     

How powerful is continuous nonlinear information for linear problems?

There are many papers dealing with the approximate solution of linear problems where only partial information is available. Two types of information have been considered: linear and discontinuous nonlinear. In particular, we know that discontinuous nonlinear information is far more powerful than linear information. In this paper we study continuous nonlinear information for linear problems, and we prove that:

• -it is no more powerful than linear information in the worst case setting,

• -it is much more powerful than linear information in the average case setting.

     

Suzuki群Sz(q)和线性空间的自同构群

本文研究了线性空间的几乎单的线传递自同构群.利用有限线性空间上线传递自同构群的经典结论,以及Suzuki群Sz(q)的性质,获得了线性空间上线传递且点本原的自同构群的基柱不是Sz(q)的结果,推广了关于线传递性空间的已有结果.     

Some results on linear arboricity

The linear arboricity of the graph G is the minimum number of linear forests whose union is G. In the paper exact values and bounds of linear arboricity for some additional classes of graphs are determined.     

反五对角与拟反五对角方程组的追赶法

本文研究了反五对角和拟五对角线性方程组的求解问题.利用矩阵分解方法以及将系数矩阵A分解成三个简单矩阵的乘积A=LUD,获得了反五对角线性方程组以及拟反五对角线性方程组的追赶法,从而推广了对角型线性方程组追赶法.     

Ein globales Ergebnis für Bifurkationsaufgaben mit schwach differenzierbaren Operatoren

In this paper we are dealing with positive linear functionals on W-algebras. We introduce the notion of a positive linear functional with ∑-property (see Definition 1.1). It is shown that each positive linear functional on a W-algebra possesses the ∑-property. This fact allows to give a short proof of UHLMANN's conjecture on unitary mixing in the state space of a W-algebra. In proving our main theorem (see Theorem 1.2.) we obtain some results on positive linear functionals and orthoprojections which are useful in other context, too.     

A disjoint idempotent decomposition for linear combinations produced from two commutative tripotent matrices and its applications

A square matrix A of order n is said to be tripotent if A ³?=?A. In this note, we give a nine-term disjoint idempotent decomposition for the linear combination of two commutative tripotent matrices and their products. Using the decomposition, we derive some closed-form formulae for the eigenvalues, determinant, rank, trace, power, inverse and group inverse of the linear combinations. In particular, we show that the linear combinations of two commutative tripotent elements and their products can produce 3⁹?=?19,683 tripotent elements.     

Irreducible Width 2 Posets of Linear Discrepancy 3

The linear discrepancy of a poset P is the least k such that there is a linear extension L of P such that if x and y are incomparable in P, then |h _L (x) − h _L (y)| ≤ k, where h _L (x) is the height of x in L. Tannenbaum, Trenk, and Fishburn characterized the posets of linear discrepancy 1 as the semiorders of width 2 and posed the problem for characterizing the posets of linear discrepancy 2. Howard et al. (Order 24:139–153, 2007) showed that this problem is equivalent to finding all posets of linear discrepancy 3 such that the removal of any point reduces the linear discrepancy. In this paper we determine all of these minimal posets of linear discrepancy 3 that have width 2. We do so by showing that, when removing a specific maximal point in a minimal linear discrepancy 3 poset, there is a unique linear extension that witnesses linear discrepancy 2. The first author was supported during this research by National Science foundation VIGRE grant DMS-0135290.     

Sufficiency and completeness in the linear model

This paper provides further contributions to the theory of linear sufficiency and linear completeness. The notion of linear sufficiency was introduced by [2], Ann. Statist. 9, 913–916) and Drygas (in press, Sankhya) with respect to the linear model Ey = Xβ, var y = V. In addition to correcting an inadequate proof of [8], the relationship to an earlier definition and to the theory of linear prediction is also demonstrated. Moreover, the notion is extended to the model Ey = Xβ, var y = δ²V. Its connection with sufficiency under normality is investigated. An example illustrates the results.     

Pointwise superconvergence of recovered gradients for piecewise linear finite element approximations to problems of planar linear elasticity

In this paper we consider piecewise linear finite element approximations to the problem of planar linear elasticity, and present some new estimates for the pointwise (L_∞) superconvergence of a recovered gradient function to the gradient of the true solution. This extends to linear elasticity the previous work of the present and other authors on L_∞ results for Poisson problems, and at the same time, to the L_∞ norm the previous L₂ results of the authors for linear elasticity.     

Local Bahadur efficiency of rank tests for the independence problem

In previous papers [Approximate and local Bahadur efficiency of linear rank tests in the two-sample problem, Ann. Statist.7, 1246–1255, 1979; Local comparison of linear rank tests in the Bahadur sense, Metrika, 1979] the author developed for linear rank tests of the one-sample symmetry and the k-sample problem (k ≥ 2) a theory of local comparison, based on the concept of Bahadur efficiency. In the present article this theory is carried over to rank tests of the independence problem.     

A short proof of Totten's classification of restricted linear spaces

A restricted linear space is one which satisfies (b–v)²v, where b is the number of lines and v is the number of points. In 1976, Totten classified all restricted linear spaces as being of essentially three types. In this paper we give a short, self-contained proof of this result. Our approach is greatly simplified by the use of techniques from linear algebra.This work was supported in part by National Science Foundation Grant MCS-8217596.     

Homomorphic solution of fully fuzzy linear systems

In this paper, a fully fuzzy linear system (FFLS) is considered. By defuzzifying, the (n × n) FFLS can be replaced by three (n × n) crisp linear systems, and consequently its homomorphic solution in canonical trapezoidal form based on three (n × n) crisp linear solutions associated with three parameters, value, ambiguity, and fuzziness, is calculated.     

Approximation of RNA multiple structural alignment

In the context of non-coding RNA (ncRNA) multiple structural alignment, Davydov and Batzoglou (2006) introduced in [7] the problem of finding the largest nested linear graph that occurs in a set G of linear graphs, the so-called Max-NLS problem. This problem generalizes both the longest common subsequence problem and the maximum common homeomorphic subtree problem for rooted ordered trees.In the present paper, we give a fast algorithm for finding the largest nested linear subgraph of a linear graph and a polynomial-time algorithm for a fixed number (k) of linear graphs. Also, we strongly strengthen the result of Davydov and Batzoglou (2006) [7] by proving that the problem is NP-complete even if G is composed of nested linear graphs of height at most 2, thereby precisely defining the borderline between tractable and intractable instances of the problem. Of particular importance, we improve the result of Davydov and Batzoglou (2006) [7] by showing that the Max-NLS problem is approximable within ratio in O(kn²) running time, where mopt is the size of an optimal solution. We also present O(1)-approximation of Max-NLS problem running in O(kn) time for restricted linear graphs. In particular, for ncRNA derived linear graphs, a -approximation is presented.     

Informativeness of Linear Functionals

In this paper, we study the informativeness of linear functionals in reconstruction problems and obtain exact orders of the informativeness of linear functionals in the Besov and Sobolev classes W and SW.     

On finite {s-2, s}-semiaffine linear spaces

In this paper finite {s-2, s}-semiaffine linear spaces of order n are studied. It is proved that if s= 6 or then there is only a finite number of such linear spaces. Received 28 May 1999; revised 28 December 1999.     

On the rank of truncated incidence matrices of linear spaces

It is well known that for every finite linear space the number b of lines is greater or equal to the number v of points of the space. In this paper we investigate the relation between the nonnegative integer b - v and suitable configurations of subspaces of a linear space.     

Continuation of a linear operator to an involution operator

A bounded linear operatorA:X→X in a linear topological spaceX is called ap-involution operator,p≥2, ifA ^p=I, whereI is the identity operator. In this paper, we describe linearp-involution operators in a linear topological space over the field ℂ and prove that linear operators can be continued to involution operators. Translated fromMatematicheskie Zametki, Vol. 61, No. 5, pp. 671–676, May, 1997. Translated by M. A. Shishkova     

Linear differential equations in <Emphasis Type="Italic">L</Emphasis><Subscript>2</Subscript> with radial derivatives

We obtain a solution of a linear differential equation with a radial derivative. The coefficients and the solution are functionals on L ₂[a, b]. In the same space, we study the properties of solutions of second-order linear homogeneous equations.     

Model-theory of vector-spaces over unspecified fields

Vector spaces over unspecified fields can be axiomatized as one-sorted structures, namely, abelian groups with the relation of parallelism. Parallelism is binary linear dependence. When equipped with the n-ary relation of linear dependence for some positive integer n, a vector-space is existentially closed if and only if it is n-dimensional over an algebraically closed field. In the signature with an n-ary predicate for linear dependence for each positive integer n, the theory of infinite-dimensional vector spaces over algebraically closed fields is the model-completion of the theory of vector spaces.