Jianqin Zhou

Jianqin Zhou, Sichun Yang, Xifeng Wang et al.

Based on rectangle theory of formal concept and set covering theory, the concept reduction preserving binary relations is investigated in this paper. It is known that there are three types of formal concepts: core concepts, relative necessary concepts and unnecessary concepts. First, we present the new judgment results for relative necessary concepts and unnecessary concepts. Second, we derive the bounds for both the maximum number of relative necessary concepts and the maximum number of unnecessary concepts and it is a difficult problem as either in concept reduction preserving binary relations or attribute reduction of decision formal contexts, the computation of formal contexts from formal concepts is a challenging problem. Third, based on rectangle theory of formal concept, a fast algorithm for reducing attributes while preserving the extensions for a set of formal concepts is proposed using the extension bit-array technique, which allows multiple context cells to be processed by a single 32-bit or 64-bit operator. Technically, the new algorithm could store both formal context and extent of a concept as bit-arrays, and we can use bit-operations to process set operations "or" as well as "and". One more merit is that the new algorithm does not need to consider other concepts in the concept lattice, thus the algorithm is explicit to understand and fast. Experiments demonstrate that the new algorithm is effective in the computation of attribute reductions.

Jianqin Zhou, Sichun Yang, Xifeng Wang et al.

Concise granule descriptions for definable granules and approaching descriptions for indefinable granules are challenging and important issues in granular computing. The concept with only common attributes has been intensively studied. To investigate the granules with some special needs, we propose a novel type of compound concepts in this paper, i.e., common-and-necessary concept. Based on the definitions of concept-forming operations, the logical formulas are derived for each of the following types of concepts: formal concept, object-induced three-way concept, object oriented concept and common-and-necessary concept. Furthermore, by utilizing the logical relationship among various concepts, we have derived concise and unified equivalent conditions for definable granules and approaching descriptions for indefinable granules for all four kinds of concepts.

Jianqin Zhou, Sichun Yang, Xifeng Wang et al.

The emergence of Formal Concept Analysis (FCA) as a data analysis technique has increased the need for developing algorithms which can compute formal concepts quickly. The current efficient algorithms for FCA are variants of the Close-By-One (CbO) algorithm, such as In-Close2, In-Close3 and In-Close4, which are all based on horizontal storage of contexts. In this paper, based on algorithm In-Close4, a new algorithm based on the vertical storage of contexts, called In-Close5, is proposed, which can significantly reduce both the time complexity and space complexity of algorithm In-Close4. Technically, the new algorithm stores both context and extent of a concept as a vertical bit-array, while within In-Close4 algorithm the context is stored only as a horizontal bit-array, which is very slow in finding the intersection of two extent sets. Experimental results demonstrate that the proposed algorithm is much more effective than In-Close4 algorithm, and it also has a broader scope of applicability in computing formal concept in which one can solve the problems that cannot be solved by the In-Close4 algorithm.

Jianqin Zhou, Wanquan Liu, Guanglu Zhou

The linear complexity and the $k$-error linear complexity of a binary sequence are important security measures for key stream strength. By studying binary sequences with the minimum Hamming weight, a new tool named as hypercube theory is developed for $p^n$-periodic binary sequences. In fact, hypercube theory is based on a typical sequence decomposition and it is a very important tool in investigating the critical error linear complexity spectrum proposed by Etzion et al. To demonstrate the importance of hypercube theory, we first give a standard hypercube decomposition based on a well-known algorithm for computing linear complexity and show that the linear complexity of the first hypercube in the decomposition is equal to the linear complexity of the original sequence. Second, based on such decomposition, we give a complete characterization for the first decrease of the linear complexity for a $p^n$-periodic binary sequence $s$. This significantly improves the current existing results in literature. As to the importance of the hypercube, we finally derive a counting formula for the $m$-hypercubes with the same linear complexity.

Jianqin Zhou, Wanquan Liu, Xifeng Wang

In this paper, in order to characterize the critical error linear complexity spectrum (CELCS) for $2^n$-periodic binary sequences, we first propose a decomposition based on the cube theory. Based on the proposed $k$-error cube decomposition, and the famous inclusion-exclusion principle, we obtain the complete characterization of $i$th descent point (critical point) of the k-error linear complexity for $i=2,3$. Second, by using the sieve method and Games-Chan algorithm, we characterize the second descent point (critical point) distribution of the $k$-error linear complexity for $2^n$-periodic binary sequences. As a consequence, we obtain the complete counting functions on the $k$-error linear complexity of $2^n$-periodic binary sequences as the second descent point for $k=3,4$. This is the first time for the second and the third descent points to be completely characterized. In fact, the proposed constructive approach has the potential to be used for constructing $2^n$-periodic binary sequences with the given linear complexity and $k$-error linear complexity (or CELCS), which is a challenging problem to be deserved for further investigation in future.

Jianqin Zhou, Jun Liu, Wanquan Liu

By using the sieve method of combinatorics, we study $k$-error linear complexity distribution of $2^n$-periodic binary sequences based on Games-Chan algorithm. For $k=4,5$, the complete counting functions on the $k$-error linear complexity of $2^n$-periodic balanced binary sequences (with linear complexity less than $2^n$) are presented. As a consequence of the result, the complete counting functions on the 4-error linear complexity of $2^n$-periodic binary sequences (with linear complexity $2^n$ or less than $2^n$) are obvious. Generally, the complete counting functions on the $k$-error linear complexity of $2^n$-periodic binary sequences can be obtained with a similar approach.

Jianqin Zhou, Wanquan Liu

The linear complexity and k-error linear complexity of a sequence have been used as important measures of keystream strength, hence designing a sequence with high linear complexity and $k$-error linear complexity is a popular research topic in cryptography. In this paper, the concept of stable $k$-error linear complexity is proposed to study sequences with stable and large $k$-error linear complexity. In order to study k-error linear complexity of binary sequences with period $2^n$, a new tool called cube theory is developed. By using the cube theory, one can easily construct sequences with the maximum stable $k$-error linear complexity. For such purpose, we first prove that a binary sequence with period $2^n$ can be decomposed into some disjoint cubes and further give a general decomposition approach. Second, it is proved that the maximum $k$-error linear complexity is $2^n-(2^l-1)$ over all $2^n$-periodic binary sequences, where $2^{l-1}\le k<2^{l}$. Thirdly, a characterization is presented about the $t$th ($t>1$) decrease in the $k$-error linear complexity for a $2^n$-periodic binary sequence $s$ and this is a continuation of Kurosawa et al. recent work for the first decrease of k-error linear complexity. Finally, A counting formula for $m$-cubes with the same linear complexity is derived, which is equivalent to the counting formula for $k$-error vectors. The counting formula of $2^n$-periodic binary sequences which can be decomposed into more than one cube is also investigated, which extends an important result by Etzion et al..