International Journal of Foundations of Computer Science

A 3.8165-competitive 2-space bounded 2-dimensional bin packing algorithm is described. Moreover, a 3.6-competitive online square packing algorithm with two active bins is presented.

We discuss the notion of privileged word, recently introduced by Kellendonk, Lenz and Savinien. A word w is privileged if it is of length ≤ 1, or has a privileged border that occurs exactly twice in w. We prove the following results: (1) if w^k is privileged for some $k\ge 1$, then w^j is privileged for all $j\ge 0$; (2) the language of privileged words is not context-free; (3) there is a linear-time algorithm to check if a given word is privileged; and (4) there are at least ${\text{2}}^{\text{n-4}}{\text{/n}}^{\text{2}}$ privileged binary words of length n.

In this paper, a kind of generalized cyclotomy with respect to the square of a prime is presented and the properties of the corresponding generalized cyclotomic numbers are investigated. Based on the generalized cyclotomy, a class of frequency-hopping sequence (FHS) set is constructed. By means of some basic properties of the generalized cyclotomy, we derive the Hamming correlation distribution of the new set. The results show that the proposed FHS set is optimal with regard to the average Hamming correlation (AHC) bound. By choosing suitable parameters, the construction also leads to the optimal FHS set and the optimal FHSs with regard to the maximum Hamming correlation (MHC) bound and Lempel-Greenberger bound, respectively.

By embedding a Toeplitz matrix-vector product (MVP) of dimension n into a circulant MVP of dimension $\text{N = 2n +}\delta \text{-1}$, where δ can be any nonnegative integer, we present a GF(2ⁿ) multiplication algorithm. This algorithm leads to a new redundant representation, and it has two merits: (1) The flexible choices of δ make it possible to select a proper N such that the multiplication operation in ring ${\text{GF(2)[x]/(x}}^{\text{N}}\text{ + 1)}$ can be performed using some asymptotically faster algorithms, e.g. the Fast Fourier Transformation (FFT)-based multiplication algorithm; (2) The redundant degrees, which are defined as N/n, are smaller than those of most previous GF(2ⁿ) redundant representations, and in fact they are approximately equal to 2 for all applicable cases.

This paper discusses some algebraic properties of Parikh q-matrices. A new way of q-counting of the subwords of a given word w is introduced. It has been shown that the notion of alternating Parikh q-matrices can be characterized using the q-counting polynomials. We also show that a Minor of a Parikh q-matrix is a polynomial in q with non-negative coefficients. Further this work provides an extension of the definition of partial sum ⊕ to Parikh q-matrices. A characterization on words x and y such that the partial sum of their Parikh q-matrices is always a Parikh q-matrix is also given. We also provide some partial results for the case q = 1.

Let G be a connected graph. A set of vertices $\text{S }\subseteq \text{ V (G)}$ is called subverted from G if each of the vertices in S and the neighbor of S in G are deleted from G. By G/S we denote the survival subgraph that remains after S is subverted from G. A vertex set S is called a cut-strategy of G if G/S is disconnected, a clique, or ø. The vertex-neighbor-scattering number of G is defined by $\text{VNS(G) = }\underset{\text{S}\subseteq \text{V(G)}}{\text{max}}\text{{}\omega \text{(G/S)}\text{-}\mathrm{|S|}\text{}}$, where S is any cut-strategy of G, and ø(G/S) is the number of components of G/S. It is known that this parameter can be used to measure the vulnerability of spy networks and the computing problem of the parameter is NP-complete. In this paper, we discuss the vertex-neighbor-scattering number of bipartite graphs. The NP-completeness of the computing problem of this parameter is proven, and some upper and lower bounds of the parameter are also given.

We show the use of a reconfigurable computer in computing the correlation immunity of Boolean functions of up to 6 variables. Boolean functions with high correlation immunity are desired in cryptographic systems because they are immune to correlation attacks. The SRC-6 reconfigurable computer was programmed in Verilog to compute the correlation immunity of functions. This computation is performed at a rate that is 190 times faster than a conventional computer. Our analysis of the correlation immunity is across all n-variable Boolean functions, for 2 ≤ n ≤ 6, thus obtaining, for the first time, a complete distribution of such functions. We also compare correlation immunity with two other cryptographic properties, nonlinearity and degree.