The adjacency graphs of some feedback shift registers

In this paper, we consider the adjacency graphs of some feedback shift registers (FSRs), namely, the FSRs with characteristic functions of the form \(g=(x_0+x_1)*f\). Firstly, we give some properties about these FSRs. We prove that these FSRs generate only prime cycles, and these cycles can be divided into two sets such that each set contains no adjacent cycles. When f is a linear function, more properties about these FSRs are derived. For example, it is shown that, when f contains an odd number of terms, the adjacency graph of \({\mathrm {FSR}}((x_0+x_1)*f)\) can be determined directly from the adjacency graph of \({\mathrm {FSR}}(f)\). Then, as an application of these results, we continue the work of Li et al. (IEEE Trans Inf Theory 60(5):3052–3061, 2014) to determine the adjacency graphs of \({\mathrm {FSR}}((1+x)^4p(x))\) and \({\mathrm {FSR}}((1+x)^5p(x))\), where p(x) is a primitive polynomial, and construct a large class of De Bruijn sequences from them.     

On nonlinear feedback shift registers with short periods

Motivated by certain cryptological problems, some specific properties of two classes of feedback shift registers with short periods are discussed in this paper.     

On the number of irreducible linear transformation shift registers

We deal with the problem of counting the number of irreducible linear transformation shift registers (TSRs) over a finite field. In a recent paper, Ram reduced this problem to calculate the cardinality of some set of irreducible polynomials and got explicit formulae for the number of irreducible TSRs of order two. We find a bijection between Ram’s set to another set of irreducible polynomials which is easier to count, and then give a conjecture about the number of irreducible TSRs of any order. We also get explicit formulae for the number of irreducible TSRs of order three.     

On the cycle structure of a set of nonlinear shift registers with symmetric feedback functions

We show that all sequences generated by a set of nonlinear shift registers with symmetric feedback functions have minimal periods dividing n(n + 1). Here n is the number of shift register stages.     

Chromatic polynomials and broken cycles

We study the “broken circuits” introduced by H. Whitney, and their applications to chromatic polynomials, using as a main tool the idea of the cycle space.     

An iterative algorithm for parametrization of shortest length linear shift registers over finite chain rings

The construction of shortest feedback shift registers for a finite sequence \(S_1,\ldots ,S_N\) is considered over finite chain rings, such as \({\mathbb Z}_{p^r}\). A novel algorithm is presented that yields a parametrization of all shortest feedback shift registers for the sequence of numbers \(S_1,\ldots ,S_N\), thus solving an open problem in the literature. The algorithm iteratively processes each number, starting with \(S_1\), and constructs at each step a particular type of minimal basis. The construction involves a simple update rule at each step which leads to computational efficiency. It is shown that the algorithm simultaneously computes a similar parametrization for the reverse sequence \(S_N,\ldots ,S_1\). The complexity order of the algorithm is shown to be \(O(r N^2)\).     

Synthesis of a minimal shift register with linear feedback and prescribed state cycle

Translated fromIssledovaniya po Prikladnoi Matematike, No. 19, 1992, pp. 51–56.     

LLT polynomials,chromatic quasisymmetric functions and graphs with cycles

We use a Dyck path model for unit-interval graphs to study the chromatic quasisymmetric functions introduced by Shareshian and Wachs, as well as unicellular LLT polynomials, revealing some parallel structure and phenomena regarding their $\mathrm{e}$-positivity.The Dyck path model is also extended to circular arc digraphs to obtain larger families of polynomials, giving a new extension of LLT polynomials. Carrying over a lot of the non-circular combinatorics, we prove several statements regarding the $\mathrm{e}$-coefficients of chromatic quasisymmetric functions and LLT polynomials, including a natural combinatorial interpretation for the $\mathrm{e}$-coefficients for the line graph and the cycle graph for both families. We believe that certain $\mathrm{e}$-positivity conjectures hold in all these families above.Furthermore, beyond the chromatic analogy, we study vertical-strip LLT polynomials, which are modified Hall–Littlewood polynomials.     

A construction for strength-3 covering arrays from linear feedback shift register sequences

We present a new construction for covering arrays inspired by ideas from Munemasa (Finite Fields Appl 4:252–260, 1998) using linear feedback shift registers (LFSRs). For a primitive polynomial \(f\) of degree \(m\) over \(\mathbb F _q\) , by taking all unique subintervals of length \(\frac{q^m-1}{q-1}\) from the LFSR generated by \(f\) , we derive a general construction for optimal variable strength orthogonal arrays over an infinite family of abstract simplicial complexes. For \(m=3\) , by adding the subintervals of the reversal of the LFSR to the variable strength orthogonal array, we derive a strength-3 covering array over \(q^2+q+1\) factors, each with \(q\) levels that has size only \(2q^3-1\) , i.e. a \(\text {CA}(2q^3-1; 3, q^2+q+1, q)\) whenever \(q\) is a prime power. When \(q\) is not a prime power, we obtain results by using fusion operations on the constructed array for higher prime powers and obtain improved bounds. Colbourn maintains a repository of the best known bounds for covering array sizes for all \(2 \le q \le 25\) . Our construction, with fusing when applicable, currently holds records of the best known upper bounds in this repository for all \(q\) except \(q = 2,3,6\) . By using these covering arrays as ingredients in recursive constructions, we build covering arrays over larger numbers of factors, again providing significant improvements on the previous best upper bounds.     

A relationship between the Berlekamp-Massey and the euclidean algorithms for linear feedback shift register synthesis

A relationship between the Berlekamp-Massey and the Euclidean algorithms for linear feedback shift register synthesis is established. In fact, by refining a sequence of polynomials appearing in the Euclidean algorithm, the sequence of characteristic polynomials computed by the Berlekamp-Massey algorithm will be achieved. A preliminary version of this paper was presented at the Oberwolfach Information Theory Meeting, May 12–16, 1986.     

Hamiltonian cycles and dominating cycles passing through a linear forest

Let G be an (m+2)-graph on n vertices, and F be a linear forest in G with |E(F)|=m and ω₁(F)=s, where ω₁(F) is the number of components of order one in F. We denote by σ₃(G) the minimum value of the degree sum of three vertices which are pairwise non-adjacent. In this paper, we give several σ₃ conditions for a dominating cycle or a hamiltonian cycle passing through a linear forest. We first prove that if σ₃(G)≥n+2m+2+max{s−3,0}, then every longest cycle passing through F is dominating. Using this result, we prove that if σ₃(G)≥n+κ(G)+2m−1 then G contains a hamiltonian cycle passing through F. As a corollary, we obtain a result that if G is a 3-connected graph and σ₃(G)≥n+κ(G)+2, then G is hamiltonian-connected.     

Real meromorphic functions and linear differential polynomials

We determine all real meromorphic functions f in the plane such that f has finitely many zeros, the poles of f have bounded multiplicities, and f and F have finitely many non-real zeros, where F is a linear differential polynomial given by F = f (k) +Σk-1j=0ajf(j) , in which k≥2 and the coefficients aj are real numbers with a0≠0.     

Dual exponential polynomials and linear differential equations

We study linear differential equations with exponential polynomial coefficients, where exactly one coefficient is of order greater than all the others. The main result shows that a nontrivial exponential polynomial solution of such an equation has a certain dual relationship with the maximum order coefficient. Several examples illustrate our results and exhibit possibilities that can occur.     

The quantum general linear supergroup,canonical bases and Kazhdan-Lusztig polynomials

Canonical bases of the tensor powers of the natural -module V are constructed by adapting the work of Frenkel, Khovanov and Kirrilov to the quantum supergroup setting. This result is generalized in several directions. We first construct the canonical bases of the ℤ₂-graded symmetric algebra of V and tensor powers of this superalgebra; then construct canonical bases for the superalgebra O _q (M _m|n ) of a quantum (m,n) × (m,n)-supermatrix; and finally deduce from the latter result the canonical basis of every irreducible tensor module for by applying a quantum analogue of the Borel-Weil construction. This work was supported by National Natural Science Foundation of China (Grant No. 10471070)     

Greedily constructing Hamiltonian paths, Hamiltonian cycles and maximum linear forests

There are various greedy schemas to construct a maximal path in a given input graph. Associated with each such schema is the family of graphs where it always results a path of maximum length, or a Hamiltonian path/cycle, if there exists one. Considerable amount of work has been carried out, regarding the characterization and recognition problems of such graphs. We present here a systematic listing of previous results of this type and fill up most of the remaining empty entries.