On probabilistic n-ary hypergroups

The T-fuzzy n-ary subhypergroups of an n-ary hypergroup are defined by using triangular norms and some related properties are hence obtained. In particular, we consider the probabilistic version of n-ary hypergroups by using random sets and show that the fuzzy n-ary hypergroups defined by triangular norms are consequences of some probabilistic n-ary hypergroups under certain conditions. Some results on n-ary hypergroups recently given by Davvaz and Corsini are extended.     

The linear complexity of new generalized cyclotomic binary sequences of order four

Whiteman generalized cyclotomic sequences are proven to exhibit a number of good randomness properties. In this paper we determine the linear complexity of some newly generalized cyclotomic sequences, of order four with period pq which are defined by Ding and Helleseth. The results show that all of these sequences have high linear complexity.     

计算p^n-周期二元序列的最小错线性复杂度新算法

传统的计算序列k-错线性复杂度的算法,每一步都要计算和存储序列改变的代价,基于节省计算量和存储空间的考虑,提出了一种计算周期为pn的二元序列的最小错线性复杂度的新算法,其中p为素数,2为模p2的一个本原根。新算法省去了序列代价的存储和计算,主要研究在k为最小错,即使得序列线性复杂度第一次下降的k值时,序列线性复杂度的计算方法,给出了理论证明,并用穷举法与传统算法对序列的计算结果进行了比对。结果完全一致且比传统算法节省了一半以上的存储空间和计算时间,是一种有效的研究特殊周期序列稳定性的计算方法。     

Trace representation of some generalized cyclotomic sequences of length pq

This paper contributes to trace representation of some generalized cyclotomic sequences of length which are defined by Ding and Helleseth. From the relations between these sequences and the Legendre sequence, we firstly confirm the defining pairs of these sequences of arbitrary order. Then, we obtain their trace representation, from which we give their linear complexity using Key’s method. It can be seen that Bai et al.’s conclusion is a special case of our result when the order is two. Finally, an example is given to illustrate the validity of our result.     

On the linear span of the p -ary cascaded GMW sequences

In this paper, a recursion is derived to compute the linear span of the p-ary cascaded GMW sequences. It is the first time to determine the linear span of the p-ary cascaded GMW sequence without any restriction on the parameters completely. Whereas, the known result on the p-ary cascaded GMW sequence with the specific parameters in the literature could be viewed as a special case of the new result. Supported by the National Natural Science Foundation of China (Grant No. 60302015), the Foundation for the Author of National Excellent Doctoral Dissertation of China (Grant No. 200341), and Sichuan Youth Science Foundation (Grant No. 04ZQ026-048)     

Augmented k-ary n-cubes

We define an interconnection network AQ_n,k which we call the augmented k-ary n-cube by extending a k-ary n-cube in a manner analogous to the existing extension of an n-dimensional hypercube to an n-dimensional augmented cube. We prove that the augmented k-ary n-cube AQ_n,k has a number of attractive properties (in the context of parallel computing). For example, we show that the augmented k-ary n-cube AQ_n,k: is a Cayley graph, and so is vertex-symmetric, but not edge-symmetric unless n = 2; has connectivity 4n − 2 and wide-diameter at most max{(n − 1)k − (n − 2), k + 7}; has diameter , when n = 2; and has diameter at most , for n ? 3 and k even, and at most , for n ? 3 and k odd.     

GF(pm)上周期为pn序列的m紧错线性复杂度*

综合线性复杂度、k错线性复杂度、k错线性复杂度曲线和最小错误minerror(S)的概念,提出紧错线性复杂度的概念。在GF(pm)上周期为pn序列的k错线性复杂度快速算法的基础上,给出m紧错线性复杂度的快速算法。其中p是素数。 编程实现了该算法, 并给出实验结果。     

若干二元周期序列的紧错线性复杂度

综合线性复杂度、k错线性复杂度、k错线性复杂度曲线和最小错误minerror（S）的概念,提出m紧错线性复杂度的概念。 序列S的m紧错线性复杂度是一个二元组（km,LCm）。序列S的k错线性复杂度曲线的第m个跃变点对应的km值和对应km错线性复杂度LCm,称为序列S的m紧错线性复杂度。通过使用简洁的cost二维结构,给出了周期为2n的二元序列的紧错线性复杂度算法,并证明具有Stamp-Martin模式的线性复杂度算法均可以简单地推广为求紧错线性复杂度的算法。与现有k错线性复杂度算法不同,该算法中省去了原来序列元素的运算。在王-张-肖算法基础上,通过使用cost二维结构,给出了周期为pn的二元序列的紧错线性复杂度算法,其中p是一个素数,2是一个模p2的本原根。     

Upper bounds on the queuenumber of k-ary n-cubes

A queue layout of a graph consists of a linear order of its vertices, and a partition of its edges into queues, such that no two edges in the same queue are nested. The minimum number of queues in a queue layout of a graph G, denoted by qn(G), is called the queuenumber of G. Heath and Rosenberg [SIAM J. Comput. 21 (1992) 927-958] showed that boolean n-cube (i.e., the n-dimensional hypercube) can be laid out using at most n−1 queues. Heath et al. [SIAM J. Discrete Math. 5 (1992) 398-412] showed that the ternary n-cube can be laid out using at most 2n−2 queues. Recently, Hasunuma and Hirota [Inform. Process. Lett. 104 (2007) 41-44] improved the upper bound on queuenumber to n−2 for hypercubes. In this paper, we deal with the upper bound on queuenumber of a wider class of graphs called k-ary n-cubes, which contains hypercubes and ternary n-cubes as subclasses. Our result improves the previous bound in the case of ternary n-cubes. Let denote the n-dimensional k-ary cube. This paper contributes three main results as follows:

(1)

if n?3.

(2)

if n?2 and 4?k?8.

(3)

if n?1 and k?9.

     

Q-ary search with one lie and bi-interval queries

The following search game is considered: there are two players, say Paul (or questioner) and Carole (or responder). Carole chooses a number x^*∈Sn={1,2,…,n}, Paul has to find the number x^* by asking q-ary bi-interval queries and Carole is allowed to lie at most once throughout the game. The minimum worst-case number LB(n,q,1) of q-ary bi-interval queries necessary to guess the number x^* is determined exactly for all integers n?1 and q?2. It turns out that LB(n,q,1) coincides with the minimum worst-case number L(n,q,1) of arbitrary q-ary queries.     

The rotation graph of k-ary trees is Hamiltonian

In this paper we show that the graph of k-ary trees, connected by rotations, contains a Hamilton cycle. Our proof is constructive and thus provides a cyclic Gray code for k-ary trees. Furthermore, we identify a basic building block of this graph as the 1-skeleton of the polytopal complex dual to the lower faces of a certain cyclic polytope.     

On the linear complexity of the Naor-Reingold sequence

We obtain a lower bound on the linear complexity of the Naor-Reingold sequence. This result solves an open problem proposed by Igor Shparlinski and improves known results in some cases.     

On the linear complexity of bounded integer sequences over different moduli

We give a relation between the linear complexity over the integers and over the residue rings modulo m of a bounded integer sequence. This relation can be used to obtain a variety of new results for several sequences widely studied in the literature. In particular we apply it to Sidelnikov sequences.     

A representation theorem for (q-)holonomic sequences

Chomsky and Schützenberger showed in 1963 that the sequence _dL(n)$d_L(n)$, which counts the number of words of a given length n in a regular language L, satisfies a linear recurrence relation with constant coefficients for n  , i.e., it is C-finite. It follows that every sequence s(n)$s(n)$ which satisfies a linear recurrence relation with constant coefficients can be represented as _dL1(n)−_dL2(n)$d_{L_1}(n)-d_{L_2}(n)$ for two regular languages. We view this as a representation theorem for C-finite sequences. Holonomic or P-recursive sequences are sequences which satisfy a linear recurrence relation with polynomial coefficients. q-Holonomic sequences are the q-analog of holonomic sequences. In this paper we prove representation theorems of holonomic and q-holonomic sequences based on position specific weights on words, and for holonomic sequences, without using weights, based on sparse regular languages.     

线性复杂度为2n-2m的2n-周期序列的k-错线性复杂度*

线性复杂度和k-错线性复杂度是衡量密钥序列随机性的两个重要标准,运用Chan-Games算法,得到线性复杂度为2n-2m的2n-周期二元序列的k-错线性复杂度的所有可能的值,LCk(s)=0或2n－2m－2r+1+c,2n-2r+1+c。这一结果对于进一步探讨流密码密钥序列的安全性有重要的应用价值。     

New bounds on D-ary optimal codes

We propose a simple method that, given a symbol distribution, yields upper and lower bounds on the average code length of a D-ary optimal code over that distribution. Thanks to its simplicity, the method permits deriving analytical bounds for families of parametric distributions. We demonstrate this by obtaining new bounds, much better than the existing ones, for Zipf and exponential distributions when D>2.     

一类新的六次剩余序列的线性复杂度

本文构造了一类新的六次剩余序列,给出了该类序列的特征多项式和线性复杂度。结果表明该类序列具有较好的线性复杂度性质。     

多重周期序列联合线性复杂度及其快速算法

周期序列的线性复杂度是衡量流密码系统安全性能的一个重要指标。近几年人们注重对多重周期序列的联合线性复杂度的研究。该文给出了Fp上周期为Pn的多重周期序列联合线性复杂度的一个新的表达式，介绍了周期为Pn的随机多重周期序列联合线性复杂度分布的计算方法，提出了一种周期为Pn的多重周期序列联合线性复杂度的快速算法。     

A new type of fuzzy n-ary hyperstructures

The aim of this paper is to consider and study a new kind of fuzzy n-ary hyperstructures, such as fuzzy n-ary hypergroups and fuzzy (m,n)-ary hyperrings.