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.

Watson-Crick automata, recently introduced in, are new types of automata in the DNA computing framework, working on tapes which are double stranded sequences of symbols related by a complementarity relation, similar to a DNA molecule. The automata scan separately each of the two strands in a corelated mannar. Some restricted variants of them were also introduced and the relationship between the families of languages recognized by them were investigated in. In this paper, we clarify some relations between the families of languages recognized by the restricted variants of Watson-Crick finite automata and the families in the Chomsky hierarchy.

In this paper, we propose a stochastic dynamic local search (SDLS) method for Multiple-Valued Logic (MVL) learning by introducing stochastic dynamics into the traditional local search method. The proposed learning network maintains some trends of quick descent to either global minimum or a local minimum, and at the same time has some chance of escaping from local minima by permitting temporary error increases during learning. Thus the network may eventually reach the global minimum state or its best approximation with very high probability. Simulation results show that the proposed algorithm has the superior abilities to find the global minimum for the MVL network learning within reasonable number of iterations.

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.