Let L be any class of languages, L' be one of the classes of context-free, context-sensitive and recursively enumerable languages, and Σ be any alphabet. In this paper, we show that if the following statement (1) holds, then the statement (2) holds. (1) For any language L in L over Σ, there exist an alphabet Γ including Σ, a homomorphism h:Γ*Σ* defined by h(a)=a for aΣ and h(a)=λ (empty word) for aΓ-Σ, a Dyck language D over Γ, and a language L1 in L' over Γ such that L=h(DL1). (2) For any language L in L over Σ, there exist an alphabet of k pairs of matching parentheses Xk, Dyck reduction Red over Xk, and a language L2 in L' over ΣXk such that L=Red(L2)Σ*. We also give an application of this result.

An Insertion-Deletion system, first introduced in [1], is a theoretical computing model in the DNA computing framework based on insertion and deletion operations. When insertion and deletion operations work together, as expected, they are very powerful. In fact, it has been shown that even the very restricted Insertion-Deletion systems can characterize the class of recursively enumerable languages [1]-[4]. In this paper, we investigate the computational power of Insertion-Deletion systems and show that they preserve the computational universality without using contexts.

The present letter describes the estimation of the upper bounds of the correlation functions of a class of zero-correlation-zone sequences constructed from an arbitrary Hadamard matrix.

A new class of ternary sequence having a zero-correlation zone (zcz), based on Hadamard matrices, is presented. The proposed sequence construction can simultaneously generate a finite-length ternary zcz sequence set and a periodic ternary zcz sequence set. The generated finite-length ternary zcz sequence set has a zero-correlation zone for an aperiodic function. The generated periodic ternary zcz sequence set has a zero-correlation zone for even and odd correlation functions.

The present paper introduces a novel construction of ternary sequences having a zero-correlation zone. The cross-correlation function and the side-lobe of the auto-correlation function of the proposed sequence set is zero for the phase shifts within the zero-correlation zone. The proposed sequence set consists of more than one subset having the same member size. The correlation function of the sequences of a pair of different subsets, referred to as the inter-subset correlation function, has a wider zero-correlation zone than that of the correlation function of sequences of the same subset (intra-subset correlation function). The wide inter-subset zero-correlation enables performance improvement during application of the proposed sequence set. The proposed sequence set has a zero-correlation zone for periodic, aperiodic, and odd correlation functions.

In this paper, we give a direct proof of the result of Latteux and Turakainen that the full class of recursively enumerable languages can be obtained from minimal linear languages (which are generated by linear context-free grammars with only one nonterminal symbol) by Dyck reductions (which reduce pairs of parentheses to the empty word).

Watson-Crick automata were introduced as a new computer model and have been intensively investigated regarding their computational power. In this paper, aiming to establish the relations among language families defined by Watson-Crick automata and the family of context-free languages completely, we obtain the following results. (1) F1WK = FSWK = FWK, (2) FWK = AWK, (3) there exists a language which is not context-free but belongs to NWK, and (4) there exists a context-free language which does not belong to AWK.

In this paper, we give an algorithm which, given a set F of at most n-k faulty nodes, and two sets S={s1, , sk} and T = {t1,, tk}, 1kn, of non-faulty nodes in n-dimensional hypercubes Hn, finds k fault-tree node disjoint paths sitje, where (j1, , Jk) is a permutation of (1, , k), of length at most n + k in O(kn log k) time. The result of this paper implies that n disjoint paths of length at most 2n for set-to-set node disjoint path problem in Hn can be found in O(n2 log n) time.

Let L be any class of languages, L' be a class of languages which is closed under λ-free homomorphisms, and Σ be any alphabet. In this paper, we show that if the following statement (1) holds, then the statement (2) holds. (1) For any language L in L over Σ, there exist an alphabet of k pairs of matching parentheses Xk, Dyck reduction Red over Xk, and a language L1 in L' over ΣXk such that L=Red(L1)Σ*. (2) For any language L in L over Σ, there exist an alphabet Γ including Σ, a homomorphism h : Γ*Σ*, a Dyck language D over Γ, and a language L2 in L' over Γ such that L=h(DL2). We also give an application of this result.

The present paper introduces a new approach to the construction of a sequence set with a zero-correlation zone for both periodic and aperiodic correlation functions. The proposed sequences can be constructed from a pair of Hadamard matrices of orders n0 and n1. The constructed sequence set consists of n0 n1 ternary sequences, each of length n0(m+2)(n1+Δ), for a non-negative integer m and Δ ≥ 2. The zero-correlation zone of the proposed sequences is |τ| ≤ n0m+1-1, where τ is the phase shift. The proposed sequence set consists of n0 subsets, each with a member size n1. The correlation function of the sequences of a pair of different subsets, referred to as the inter-subset correlation function, has a zero-correlation zone with a width that is approximately Δ times that of the correlation function of sequences of the same subset (intra-subset correlation function). The inter-subset zero-correlation zone of the proposed sequences is |τ| ≤ Δn0m+1, where τ is the phase shift. The wide inter-subset zero-correlation enables performance improvement during application of the proposed sequence set.

The trivalent Cayley graph TCn was introduced and investigated in [1],[2]. Though "the diameter" was presented in [2], unfortunately it was not the diameter but an upper bound of it. In this paper, a lower bound of the diameter dia(TCn) of the trivalent Cayley graph TCn is investigated and the formula dia(TCn) = 2n - 2 for n 3 is established.