International Journal of Foundations of Computer Science

In [A. Frid, S. Puzynina and L. Q. Zamboni, On palindromic factorization of words, Adv. in Appl. Math. 50 (2013) 737–748], it was conjectured that any infinite word whose palindromic lengths of factors are bounded is ultimately periodic. We introduce variants of this conjecture and prove this conjecture when the bound is 2. Especially we introduce left and right greedy palindromic lengths. These lengths are always greater than or equals to the initial palindromic length. When the greedy left (or right) palindromic lengths of prefixes of a word are bounded then this word is ultimately periodic.

Universal hashing, discovered by Carter and Wegman in 1979, has many important applications in computer science. MMH${}^{\ast }$, which was shown to be $\mathrm{\Delta }$-universal by Halevi and Krawczyk in 1997, is a well-known universal hash function family. We introduce a variant of MMH${}^{\ast }$, that we call GRDH, where we use an arbitrary integer $n>1$ instead of prime $p$ and let the keys $x=〈x_1,\dots ,x_k〉\in {\mathbb{Z}}_n^k$ satisfy the conditions $gcd(x_i,n)=t_i$ ($1\le i\le k$), where $t_1,\dots ,t_k$ are given positive divisors of $n$. Then via connecting the universal hashing problem to the number of solutions of restricted linear congruences, we prove that the family GRDH is an $𝜀$-almost-$\mathrm{\Delta }$-universal family of hash functions for some $𝜀<1$ if and only if $n$ is odd and $gcd(x_i,n)=t_i=1$ $(1\le i\le k)$. Furthermore, if these conditions are satisfied then GRDH is $\frac{1}{p-1}$-almost-$\mathrm{\Delta }$-universal, where $p$ is the smallest prime divisor of $n$. Finally, as an application of our results, we propose an authentication code with secrecy scheme which strongly generalizes the scheme studied by Alomair et al. [J. Math. Cryptol. 4 (2010) 121–148], and [J.UCS 15 (2009) 2937–2956].

In interconnection network topologies, the $n$-dimensional star graph ${St}_n$ has $n!$ vertices corresponding to permutations $a_{\rho (1)},\dots ,a_{\rho (n)}$ of $n$ symbols $a_1,\dots ,a_n$ and edges which exchange the positions of the first symbol $a_{\rho (1)}$ with any one of the other symbols. The star graph compares favorably with the familiar $n$-cube on degree, diameter and a number of other parameters. A desirable property which has not been fully evaluated in star graphs is the presence of multiple edge-disjoint Hamilton cycles which are important for fault-tolerance. The only known method for producing multiple edge-disjoint Hamilton cycles in ${St}_n$ has been to label the edges in a certain way and then take images of a known base 2-labelled Hamilton cycle under different automorphisms that map labels consistently. However, optimal bounds for producing edge-disjoint Hamilton cycles in this way, and whether Hamilton decompositions can be produced, are not known for any ${St}_n$ other than for the case of ${St}_5$ which does provide a Hamilton decomposition. In this paper we show that, for all n, not more than $\phi (n)/2$, where $\phi$ is Euler’s totient function, edge-disjoint Hamilton cycles can be produced by such automorphisms. Thus, for non-prime $n$, a Hamilton decomposition cannot be produced. We show that the $\phi (n)/2$ upper bound can be achieved for all even $n$. In particular, if $n$ is a power of 2, ${St}_n$ has a Hamilton decomposable spanning subgraph comprising more than half of the edges of ${St}_n$. Our results produce a better than twofold improvement on the known bounds for any kind of edge-disjoint Hamilton cycles in $n$-dimensional star graphs for general $n$.

A $k$-workspace algorithm may use a workspace of $k$ words which can be read and written, in addition to their input, which is provided as a read-only array of $n$ items. We present a $k$-workspace algorithm for constructing the shortest path tree of a simple polygon $P$ with $n$ vertices, with respect to a given point inside the polygon in $O(n(n+{𝒯}(n,k)))$ time, where ${𝒯}(n,k)$ is the time for computing the visibility polygon of a given point inside a simple polygon with $k$ additional words of space.

We introduce an extension of the restricted shuffle operator on binary words considered by Atanasiu and Teh (2016). We then derive properties on Parikh matrix equivalence of words over a binary alphabet based on this extended shuffle operator and a weak-ratio property of words. We also examine the recently introduced concept of core Parikh matrix equivalence of binary words in the context of the restricted shuffle operator.

Representing binary truth tables is an easy task to Boolean functions. When the number of Boolean variables increases, the complexity of the Boolean functions also increases. Thus, alternative ways of representing binary truth tables are necessary. It is known that this can be accomplished by means of other approaches, such as real polynomials. In the present paper it is shown that the recently introduced iota-delta function can be used to represent every binary truth table.

Several kinds of quantum pushdown automata models have been proposed, and their computational power has been investigated intensively. However, for some quantum pushdown automaton models, it is unknown whether quantum models are at least as powerful as their classical counterparts or not. This is due to the reversibility restriction. In this paper, we introduce a new quantum pushdown automaton model that has a garbage tape. This model can overcome the reversibility restriction by exploiting the garbage tape to store popped symbols. We show that the proposed model can simulate any quantum pushdown automaton with classical stack as well as any probabilistic pushdown automaton. We also show that our model can solve a certain promise problem exactly while deterministic pushdown automata cannot. These results imply that our model is strictly more powerful than its classical counterparts in the setting of exact, one-sided error and non-deterministic computation. Showing impossibility for a promise problem is a difficult task in general. However, by analyzing the behavior of a deterministic pushdown automaton carefully, we obtained the impossibility result. This is one of the main contributions of the paper.

Link residual closeness is reported as a new graph vulnerability measure, a graph-based approach to network vulnerability analysis, and more sensitive than some other existing vulnerability measures. Residual closeness is of great theoretical and practical significance to network design and optimization. In this paper, how some of the graph types perform when they suffer a link failure is discussed. Vulnerability of graphs to the failure of individual links is computed via link residual closeness which provides a much fuller characterization of the network.