New morphic characterizations in the form of a noted Chomsky-Schützenberger theorem are established for the classes of regular languages, of context-free languages and of languages accepted by chemical reaction automata. Our results include the following: (i) Each λ-free regular language R can be e xpressed as R = h(Tk ∩ FR) for some 2-star language FR, an extended 2-star language Tk and a weak coding h. (ii) Each λ-free context-free language L can be expressed as L = h(Dn ∩ FL) for some 2-local language FL and a projection h. (iii) A language L is accepted by a chemical reaction automaton iff there exist a 2-local language FL and a weak coding h such that L = h(Bn ∩ FL), where Dn and Bn are a Dyck set and a partially balanced language defined over the n-letter alphabet, respectively. These characterizations improve or shed new light on the previous results.

This paper concerns new characterizations of language classes in the Chomsky hierarchy in terms of a new type of computing device called FAMM (Finite Automaton with Multiset Memory) in which a multiset of symbol objects is available for the storage of working space. Unlike the stack or the tape for a storage, the multiset might seem to be less powerful in computing task, due to the lack of positional (structural) information of stored data. We introduce the class of FAMMs of degree d (for non-negative integer d) in general form, and investigate the computing powers of some subclasses of those FAMMs. We show that the classes of languages accepted by FAMMs of degree 0, by FAMMs of degree 1, by exponentially-bounded FAMMs of degree 2, and by FAMMs of degree 2 are exactly the four classes of languages REG, CF, CS and RE in the Chomsky hierarchy, respectively. Thus, this unified view from multiset-based computing provides new insight into the computational aspects of the Chomsky hierarchy.

We bring together two topics recently introduced in membrane computing, the much investigated spiking neural P systems (in short, SN P systems), inspired from the way the neurons communicate through spikes, and the dP systems (distributed P systems, with components which “read” strings from the environment and then cooperate in accepting their concatenation). The goal is to introduce SN dP systems, and to this aim we first introduce SN P systems with the possibility to input, at their request, spikes from the environment; this is done by so-called request rules. A preliminary investigation of the obtained SN dP systems (they can also be called automata) is carried out. As expected, request rules are useful, while the distribution in terms of dP systems can handle languages which cannot be generated by usual SN P systems. We always work with extended SN P systems; the non-extended case, as well as several other natural questions remain open.

Hairpin completion and its variant called bounded hairpin completion are operations on formal languages, inspired by a hairpin formation in molecular biology. Another variant called hairpin lengthening has been recently introduced, and the related closure properties and algorithmic problems concerning several families of languages have been studied. In this paper, we introduce a new operation of this kind, called hairpin incompletion which is not only an extension of bounded hairpin completion, but also a restricted (bounded) variant of hairpin lengthening. Further, the hairpin incompletion operation provides a formal language theoretic framework that models a bio-molecular technique nowadays known as Whiplash PCR. We study the closure properties of language families under both the operation and its iterated version. We show that a family of languages closed under intersection with regular sets, concatenation with regular sets, and finite union is closed under one-sided iterated hairpin incompletion, and that a family of languages containing all linear languages and closed under circular permutation, left derivative and substitution is also closed under iterated hairpin incompletion.

. Molecular Computing is a novel computing paradigm recently emerged from and stimulated by a groundbreaking wet lab experimental work by Adleman in 1994. Since then, a great number of computation models have been proposed in the context of both biomolecular experiments and theoretical computer science (e.g., [2, 3, 7, 9, 10, 11, 13, 17, 19, 20]), trying to break through the so-called NP-completeness barrier or to establish new computation paradigms with universal capability. This paper proposes new computing paradigms based on self-assembly and conformational change. These two principles have already appeared in an extensive variety of literature in natural science, while relatively a few studies have discussed these two together in the context of computing. In order to demonstrate a new computing schema : computation = selfassembly + conformational change, we first discuss a framework of computing model CCC (Computing by Conformational Change) by showing examples of solving several N...

This paper presents an efficient algorithm for learning in the limit a special type of regular languages, called strictly locally testable languages from positive data, and its application to identifying the protein /spl alpha/-chain region in amino acid sequences. First, we present a linear time algorithm that, given a strictly locally testable language, learns its deterministic finite state automaton in the limit from only positive data. This provides one with a practical and efficient method for learning a specific concept domain of sequence analysis. We then describe several experimental results using the learning algorithm developed above. Following a theoretical observation which strongly suggests that a certain type of amino acid sequences can be expressed by a locally testable language, we apply the learning algorithm to identifying the protein /spl alpha/-chain region in amino acid sequences for hemoglobin. Experimental scores show an overall success rate of 95% correct identification for positive data, and 96% for negative data.

We investigate the learning problem of two-tape deterministic finite automata( 2-tape DFAs) from queries and counterexamples.Instead of accepting a subset of X*, a 2-tape DFA over an alphabet X accepts a subset of V* ~Z* and therefore, it can specifY a binary relation 'on Z*.In [3] Angluin showed that the class of deterministic finite automata(DFAs) is learnable in polynomial time from membership queries and equivalence queries, namely, from minimally adequate teacher( MAT).In this article we show that the class of 2-tape DFAs is learnable in polynomial time from MAT in the following sense that there effectively exists an algorithm that, given any language L accepted by an unknown 2-tape DFA ~, learns from MAT a two-tape nondeterrninistic finite automaton(2-tape NFA) M' accepting L in time polynomial in n and 4, where n is the size of &f for L and t is the maximum length of any counterexample provided during the learning process.This gives a generalization of the corresponding Angluin's result for DFAs.