International Journal of Foundations of Computer Science

In this paper, we study the bounded space variation, especially one-space bounded, of two-dimensional bin packing. A sequence of rectangular items arrive over time, and the following item arrives after the packing of the previous one. The height and width of each item are no more than 1, we need to pack these items into unit square bins of size 1 × 1 where rotation of 90° is allowed and our objective is to minimize the number of used bins. Once an item is packed into a square bin, the position of this item is fixed and it cannot be shifted within this bin. At any time, there is at most one active bin; the current unpacked item can be only packed into the active bin and the inactive bins (closed at some previous time) cannot be used for any future items. We first propose an online algorithm with a constant competitive ratio 12, then improve the competitive ratio to 8.84 by the some complicated analysis. Our results significantly improve the previous best known O((log log m)²)-competitive algorithm [10], where m is the width of the square bin and the size of each item is a × b, where a, b are integers no more than m. Furthermore, the lower bound for the competitive ratio is also improved to 2.5.

Let P be a set of n points in the Euclidean plane and let O be the origin point in the plane. In the k-tour cover problem (called frequently the capacitated vehicle routing problem), the goal is to minimize the total length of tours that cover all points in P, such that each tour starts and ends in O and covers at most k points from P.

The k-tour cover problem is known to be -hard. It is also known to admit constant factor approximation algorithms for all values of k and even a polynomial-time approximation scheme (PTAS) for small values of k, k = Ø(log n/log log n).

In this paper, we significantly enlarge the set of values of k for which a PTAS is provable. We present a new PTAS for all values of k ≤ 2^{logδ n}, where δ = δ(ε). The main technical result proved in the paper is a novel reduction of the k-tour cover problem with a set of n points to a small set of instances of the problem, each with Ø((k/ε)^Ø(1)) points.

In this paper we consider the computational complexity of deciding the existence of a perfect matching in certain classes of dense k-uniform hypergraphs. It has been known that the perfect matching problem for the classes of hypergraphs H with minimum ((k - 1)–wise) vertex degreeδ(H) at least c|V(H)| is NP-complete for and trivial for c ≥ ½, leaving the status of the problem with c in the interval widely open. In this paper we show, somehow surprisingly, that ½ is not the threshold for tractability of the perfect matching problem, and prove the existence of an ε > 0 such that the perfect matching problem for the class of hypergraphs H with δ(H) ≥ (½ - ε)|V(H)| is solvable in polynomial time. This seems to be the first polynomial time algorithm for the perfect matching problem on hypergraphs for which the existence problem is nontrivial. In addition, we consider parallel complexity of the problem, which could be also of independent interest.

We study the problem of finding all maximal approximate gapped palindromes in a string. More specifically, given a string S of length n, a parameter q ≥ 0 and a threshold k > 0, the problem is to identify all substrings in S of the form uvw such that (1) the Levenshtein distance between u^r and w is at most k, where u^r is the reverse of u and (2) v is a string of length q. The best previous work requires O(k²n) time. In this paper, we propose an O(kn)-time algorithm for this problem by utilizing an incremental string comparison technique. It turns out that the core technique actually solves a more general incremental string comparison problem that allows the insertion, deletion, and substitution of multiple symbols.

We discuss the power and limitation of various "advice," when it is given particularly to weak computational models of one-tape linear-time Turing machines and one-way finite (state) automata. Of various advice types, we consider deterministically-chosen advice (not necessarily algorithmically determined) and randomly-chosen advice (according to certain probability distributions). In particular, we show that certain weak machines can be significantly enhanced in computational power when randomized advice is provided in place of deterministic advice.

In this paper we study several closely related fundamental problems for words and matrices. First, we introduce the Identity Correspondence Problem (ICP): whether a finite set of pairs of words (over a group alphabet) can generate an identity pair by a sequence of concatenations. We prove that ICP is undecidable by a reduction of Post's Correspondence Problem via several new encoding techniques. In the second part of the paper we use ICP to answer a long standing open problem concerning matrix semigroups: "Is it decidable for a finitely generated semigroup S of integral square matrices whether or not the identity matrix belongs to S?". We show that the problem is undecidable starting from dimension four even when the number of matrices in the generator is 48. From this fact, we can immediately derive that the fundamental problem of whether a finite set of matrices generates a group is also undecidable. We also answer several questions for matrices over different number fields. Apart from the application to matrix problems, we believe that the Identity Correspondence Problem will also be useful in identifying new areas of undecidable problems in abstract algebra, computational questions in logic and combinatorics on words.

It is a crucial that password security be effective and constantly improved. The three-party encrypted key exchange (3PEKE) protocol has been used to protect passwords transmitted between users. Recently, Chang and Chang proposed a novel 3PEKE (ECC-3PEKE) protocol using a super-poly-to-one trapdoor function which demonstrates high efficiency. However, Chen et al. and Yoon et al., respectively, showed that the ECC-3PEKE protocol can not prevent undetectable on-line password guessing attacks and proposed improved protocols. Unfortunately, their improved protocols suffer from off-line password guessing attacks without perfect forward secrecy. Hence, the authors propose an improved protocol to strengthen their security.

Restricting the Parikh Matrix mapping to a language rather than to an alphabet rises a set of problems that seem interesting to us. Moreover, amiability (or M-equivalence as it is named by other authors) is exploited in order to characterise certain types of languages. The paper also proposes a series of results establishing relations between classes of languages defined by Parikh matrix mappings and the Chomsky hierarchy. Finally, a result related to word composition concludes the paper, showing that for every two arbitrary words there exist two other words such that their composition (two by two) is amiable.

Verification of program termination is an important problem in program correctness analysis. Automatically proving termination or finding nonterminating inputs as counter-examples for many programs will be a big breakthrough in theoretical computer science. A remarkable result, provided by Tiwari(2004), showed that the termination of linear loops is decidable and an eventually nonterminating input can be found for the given nonterminating loop. But some essential lemmas were missing in that proof and his algorithm could not generate a nonterminating input, which might be more widely utilized in software testing. In this paper, we discuss these details carefully and present an algorithm for producing a nonterminating input automatically. We reduce the problem of finding a nonterminating input to that of computing real root bound of a multi-exponential polynomial. This algorithm has been implemented in a Maple package based on symbolic computation. Thereby a stronger and complete decidable result in termination problem is established.

Using the fact that the Parikh matrix mapping is not an injective mapping, the paper investigates some properties of the set of words having the same Parikh matrix; these words are called "amiable" or "M - equivalent". The presented paper uses the results obtained in [3] for the binary case. The aim is to distinguish the amiable words by using a morphism that provides additional information about them. The morphism proposed here is the Istrail morphism.

The problem of extracting a basis of irredundant motifs from a sequence is considered. In previous work such bases were built incrementally for all suffixes of the input string s in O(n³), where n is the length of s. Faster, non-incremental algorithms have been based on the landmark approach to string searching due to Fischer and Paterson, and exhibit respective time bounds of O(n²log n log|Σ|) and O(|Σ|n²log² n log log n), with Σ denoting the alphabet. The algorithm by Fischer and Paterson makes crucial use of the FFT, which is impractical with long sequences.

The present paper describes an off-line algorithm for binary strings that takes O(n²) time. The algorithm does not need to resort to the FFT and yet its performance is optimal for finite Σ.

In a proxy re-encryption scheme, a semi-trusted proxy converts a ciphertext for Alice into a ciphertext for Bob without seeing the underlying plaintext. A number of solutions have been proposed in public key settings. Hierarchical identity-based cryptography is a generalization of identity-based encryption that mirrors an organizational hierarchy, which allows a root private key generator to distribute the workload by delegating private key generation and identity authentication to lower-level private key generators. In this paper, we propose a hierarchical identity-based proxy re-encryption (HIBPRE) scheme which achieves IND-PrID-CCA2 security without random oracles. This is the first HIBPRE scheme up to now, and our scheme satisfies unidirectionality, non-interactivity and permits multiple re-encryptions.

In this paper we give a new proof and a small improvement for the three-squares lemma for partial words with one hole. This recent result by Blanchet-Sadri et al. gives a lower bound for the length of the longest square in the situation where three squares begin at the same position of a one-hole word and the shortest square satisfies a primitivity condition.

This paper explores the phase transitions of the EXPSPACE-complete problems, which mainly focus on the conformant planning problems. The research presents two conformant planning algorithms—CONFORMANT PLAN-NONEXISTENCE algorithm and CONFORMANT PLAN-EXISTENCE algorithm. By analyzing the features of the two algorithms, the phase transition area of the conformant planning problems is obtained. If the number of the operators isn't greater than θ_ub, the CONFORMANT PLAN-NONEXISTENCE algorithm can prove that nearly all the conformant planning instances have no solution. If the number of the operators isn't lower than θ_lb, the CONFORMANT PLAN-EXISTENCE algorithm can prove that nearly all the conformant planning instances have solutions. The results of the experiments show that there exist phase transitions from a region where almost all the conformant planning instances have no solution to a region where almost all the conformant planning instances have solutions.

DNA microarray technology has proven to be an invaluable tool for molecular biologists. Microarrays are used extensively in SNP detection, genomic hybridization, alternative splicing and gene expression profiling. However the manufacturers of the microarrays are often stuck with the problem of minimizing the effects of unwanted illumination (border length minimization (BLM)) which is a hard combinatorial problem. In this paper we prove that the BLM problem on a rectangular grid is NP-hard – this however does not mean the BLM problem on a square grid is NP-hard.

We also give the first integer linear programming (ILP) formulation to solve BLM problem optimally. Experimental results indicate that our ILP method produces superior results (both in runtime and cost) compared to the current state of the art algorithms to solve the BLM problem optimally.