International Journal of Foundations of Computer Science

A two-dimensional (2D) word is a 2D palindrome if it is equal to its reverse and it is an HV-palindrome if all its columns and rows are 1D palindromes. We characterize such words and study some of their combinatorial and structural properties. We also find the number of possible palindromic conjugates of a 2D word. We investigate an upper bound on the number of distinct non-empty HV-palindromic subwords in any finite 2D word, thus, proving the conjecture given by Anisiu et al. We also identify the minimum number of HV-palindromic subwords in an infinite 2D word over a finite alphabet.

We present a more efficient CREW PRAM algorithm for integer sorting. This algorithm sorts $n$ integers in $\{0,1,2,\dots ,n^{1/2}\}$ in $O({(logn)}^{3/2}/loglogn)$ time and $O(n(logn/loglogn{)}^{1/2})$ operations. It also sorts $n$ integers in $\{0,1,2,\dots ,n-1\}$ in $O({(logn)}^{3/2}/loglogn)$ time and $O(n{(logn/loglogn)}^{1/2}logloglogn)$ operations. Previous best algorithm [15] on both cases has time complexity $O(logn)$ but operation complexity $O(n{(logn)}^{1/2})$.

The robustness evaluates the capability of networks in resisting failures or attacks on some parts of networks. The concept of vulnerability is very important in network analysis. Isolated rupture degree is a novel graph-theoretic concept defined as a measure of network vulnerability. In this paper, the relationships between isolated rupture degree and some other vulnerability parameters such as isolated scattering number and isolated toughness are established. Exact values for isolated rupture degree of thorny networks are obtained.

The $(n,k)$-star graph $S_{n,k}$, which is introduced to address scaling issues of the star graph, is recognized as an attractive interconnection network topology for building multiprocessor systems because of its desirable properties. Let $F_m(S_{n,k})$ be the minimum number of faulty vertices that make every subgraph isomorphic to $S_{n-m,k-m}$ faulty in $S_{n,k}$ under vertex-failure model, where $0\le m\le k-1$. In this paper, we prove that $F_0(S_{n,k})=1$, $F_1(S_{n,k})=n$, $F_{k-1}(S_{n,k})=n!/(n-k+1)!$, and $n!/(n-m)!\le F_m(S_{n,k})\le \left(\genfrac{}{}{0.0pt}{}{k-2}{m-1}\right)n!/(n-m)!-2\left(\genfrac{}{}{0.0pt}{}{k-3}{m-1}\right)n!/(n-m+1)!$ for $1\le k\le n-2$ and $2\le m\le k-2$.

Boolean functions are fundamental bricks in the development of various applications in Cryptography and Coding theory by making benefit from the weights of related Boolean functions (Walsh spectrum). Towards this, the discrete Fourier transform (Walsh–Hadamard) plays a pivotal tool. The work in this paper is dedicated towards the algebraic and numerical degrees, together with the relationship between weights of Boolean function and their Walsh transforms. We introduce Walsh matrices and generalize them to any arbitrary Boolean function. This improves the complexity in computation of Walsh–Hadamard and Fourier transform in certain cases. We also discuss some useful results related to the degree of the algebraic normal form using Walsh–Hadamard transform.