New morphic characterizations in the form of a noted Chomsky-Schutzenberger 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 lambda-free regular language R can be expressed as R = h(T-k boolean AND F-R) for some 2-star language F-R, an extended 2-star language T-k and a weak coding h.
(ii) Each lambda-free context-free language L can be expressed as L = h (D-n boolean AND F-L) for some 2-local language F-L and a projection h.
(iii) A language L is accepted by a chemical reaction automaton iff there exist a 2-local language F-L and a weak coding h such that L = h (B-n boolean AND F-L), where D-n and B-n 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.

We propose a new computing model called chemical reaction automata (CRAs) as a simplified variant of reaction automata (RAs) studied in recent literature (Okubo in RAIRO Theor Inform Appl 48:23-38 2014; Okubo et al. in Theor Comput Sci 429:247-257 2012a, Theor Comput Sci 454:206-221 2012b). We show that CRAs in maximally parallel manner are computationally equivalent to Turing machines, while the computational power of CRAs in sequential manner coincides with that of the class of Petri nets, which is in marked contrast to the result that RAs (in both maximally parallel and sequential manners) have the computing power of Turing universality (Okubo 2014; Okubo et al. 2012a). Intuitively, CRAs are defined as RAs without inhibitor functioning in each reaction, providing an offline model of computing by chemical reaction networks (CRNs). Thus, the main results in this paper not only strengthen the previous result on Turing computability of RAs but also clarify the computing powers of inhibitors in RA computation.

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-boundedFAMMs 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.

© Springer International Publishing Switzerland 2014. We propose a new computing model called chemical reaction automata (CRAs) as a simplified variant of reaction automata (RAs) studied in recent literature ([7–9]).We show that CRAs in maximally parallel manner are computationally equivalent to Turing machines, while the computational power of CRAs in sequential manner coincides with that of the class of Petri nets, which is in marked contrast to the result that RAs (in both maximally parallel and sequential manners) have the computing power of Turing universality ([7, 8]). Intuitively, CRAs are defined as RAs without inhibitor functioning in each reaction, providing an offline model of computing by chemical reaction networks (CRNs).Thus, the main results in this paper not only strengthen the previous result on Turing computability of RAs but also clarify the computing powers of inhibitors in RA computation.

This chapter presents both the theoretical results of molecular computing models mainly from the viewpoint of computing theory and the biochemical implementations of thosemodels inwet lab experiments. Selected topics include a variety of molecular computing models with computabilities ranging from finite automata to Turingmachines, and the associated issues of molecular implementation, as well as some applications to logical controls for circuits and medicines.

Reaction systems are a formal model that has been introduced to investigate the interactive behaviors of biochemical reactions. Based on the formal framework of reaction systems, we propose new computing models called reaction automata that feature (string) language acceptors with multiset manipulation as a computing mechanism, and show that reaction automata are computationally Turing universal. Further, some subclasses of reaction automata with space complexity are investigated and their language classes are compared to the ones in the Chomsky hierarchy. © 2012 Elsevier B.V. All rights reserved.

Insertion systems have a unique feature in that only string insertion are allowed, which is in marked contrast to a variety of the conventional computing devices based on string rewriting. This paper will mainly focus on those systems whose insertion operations are performed in a context-free fashion, called context-free insertion systems, and obtain several characterizations of language families with the help of other primitive languages (like star languages) as well as simple operations (like projections, weak-codings). For each k >= 1, a language L is a k-star language if L = F(+) for some finite set F with the length of each string in F is no more than k. The results of this kind have already been presented in [10] by Paun et al., while the purpose of this paper is to prove enhanced versions of them.
Specifically, we show that each context-free language L can be represented in the form L = h(L(gamma)boolean AND F(+)), where gamma is an insertion system of weight (3, 0) (at most three symbols are inserted in a context-free manner), h is a projection, and F(+) is a 2-star language. A similar characterization can be obtained for recursively enumerable languages, where insertion systems of weight (3, 3) and 2-star languages are involved.

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.

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.

We consider several problems regarding the iterated or non-iterated hairpin completion of some subclasses of regular languages. Thus we obtain a characterization of the class of regular languages as the weak-code images of the k-hairpin completion of center disjoint k-locally testable languages in the strict sense. This result completes two results from [3] and [11]. Then we investigate some decision problems and closure properties of the family of the iterated hairpin completion of singleton languages. Finally, we discuss some algorithms regarding the possibility of computing the values of k such that the non-iterated or iterated k-hairpin completion of a given regular language does not produce new words.

This work deals with several aspects concerning the formal verification of SN P systems and the computing power of some variants. A methodology based on the information given by the transition diagram associated with an SN P system is presented. The analysis of the diagram cycles codifies invariants formulae which enable us to establish the soundness and completeness of the system with respect to the problem it tries to resolve. We also study the universality of asynchronous and sequential SN P systems and the capability these models have to generate certain classes of languages. Further, by making a slight modification to the standard SN P systems, we introduce a new variant of SN P systems with a special I/O mode, called SN P modules, and study their computing power. It is demonstrated that, as string language acceptors and transducers, SN P modules can simulate several types of computing devices such as finite automata, a-finite transducers, and systolic trellis automata.

We consider two complementary operations: Hairpin completion introduced in [D. Cheptea, C. Martin-Vide, V. Mitrana, A new operation on words suggested by DNA biochemistry: Hairpin completion, in: Proc. Transgressive Computing, 2006, pp. 216-228] with motivations coming from DNA biochemistry and hairpin reduction as the inverse operation of the hairpin completion. Both operations are viewed here as formal operations on words and languages. We settle the closure properties of the classes of regular and linear context-free languages under hairpin completion in comparison with hairpin reduction. While the class of linear context-free languages is exactly the weak-code image of the class of the hairpin completion of regular languages, rather surprisingly, the weak-code image of the class of the hairpin completion of linear context-free languages is a class of mildly context-sensitive languages. The closure properties with respect to the hairpin reduction of some time and space complexity classes are also Studied. We show that the factors found in the general cases are not necessary for regular and context-free languages. This part of the paper completes the results given in the earlier paper, where a similar investigation was made for hairpin completion. Finally, we briefly discuss the iterated variants of these operations. (C) 2008 Elsevier B.V. All rights reserved.

In this paper, we introduce the notion of a membrane computing schema for string objects. We propose a computing schema for a membrane network (i.e., tissue-like membrane system) where each membrane performs unique type of operations at a time and sends the result to others connected through the channel. The distinguished features of the computing models obtained from the schema are:1. only context-free insertion operations are used for string generation,2. some membranes assume filtering functions for structured objects (molecules),3. generating model and accepting model are obtained in the same schema, and both are computationally universal,4. several known rewriting systems with universal computability can be reformulated by the membrane computing schema in a uniform manner.The first feature provides the model with a simple uniform Structure which facilitates it biological implementation of the model, while the second feature suggests further feasibility of the model in terms of DNA complementarity.Through the third and fourth features, one may have a unified view of a variety of existing rewriting systems with Turing computability in the framework of membrane computing paradigm.

Insertion-deletion operations are much investigated in linguistics and in DNA computing and several characterizations of Turing computability and characterizations or representations of languages in Chomsky hierarchy were obtained in this framework.
In this note we contribute to this research direction with a new characterization of this type, as well as with representations of regular and context-free languages, mainly starting from context-free insertion systems of as small as possible complexity. For instance, each recursively enumerable language L can be represented in a way similar to the celebrated Chomsky-Schutzenberger representation of context-free languages, i.e., in the form L = h(L(gamma)boolean AND D), where 7 is an insertion system of weight (3, 0) (at most three symbols are inserted in a context of length zero), h is a projection, and D is a Dyck language. A similar representation can be obtained for regular languages, involving insertion systems of weight (2,0) and star languages, as well as for context-free languages - this time using insertion systems of weight (3, 0) and star languages.

Two specific mappings called doubler f d and linearizer f e are introduced to bridge between two kinds of languages. Specifically, f d maps string languages into (double-stranded) molecular languages, while f e performs the opposite mapping. Using these mappings, we obtain new characterizations for the families of sticker languages and of Watson-Crick languages, which lead to not only a unified view of the two families of languages but also provide a helpful view on the computational capability of DNA complementarity. Furthermore, we introduce a special type of a projection f pr which is composed of f d and a projection in the usual sense. We show that any recursively enumerable language L can be expressed as f pr(L m) for a minimal linear language L m. This result can be strengthened to L = f p(L s), for a specific form of minimal linear language L s, which provides a simple morphic characterization for the family of recursively enumerable languages. © Springer Science+Business Media B.V. 2007.

We consider spiking neural P systems with a new type of rule application: whenever a rule is enabled in a neuron, it is used in an exhaustive manner, i.e., as many times as possible for the number of spikes from that neuron. Thus, also the number of spikes produced at a time in that neuron can be arbitrarily large; all produced spikes are transmitted to neighboring neurons through synapses. A result is associated with a computation as usual, in the form of the number of time units elapsed between the first two steps when the Output neuron spikes. In this framework, we prove the computational completeness of Our systems, both as number generating devices and as number accepting devices. Several research topics are also pointed out.

This paper proposes a way to incorporate the idea of spiking neurons into the area of membrane computing, and to this aim we introduce a class of neural-like P systems which we call spiking neural P systems (in short, SN P systems). In these devices, the time (when the neurons fire and/or spike) plays an essential role. For instance, the result of a computation is the time between the moments when a specified neuron spikes. Seen as number computing devices, SN P systems are shown to be computationally complete (both in the generating and accepting modes, in the latter case also when restricting to deterministic systems). If the number of spikes present in the system is bounded, then the power of SN P systems falls drastically, and we get a characterization of semilinear sets. A series of research topics and open problems are formulated.

There are several explanations of why certain primitive multicellular organisms aggregate in particular forms and why their constituent cells cooperate with one another to a particular degree. Utilizing the framework of formal language theory, we have derived one possible simple classification of the volvocine algae-one of the primitive multicells-for some forms of aggregation and some degrees of cooperation among cells. The volvocine algae range from the unicellular Chlamydonionas to the multicellular Volvox globator, which has thousands of cells. The classification we use in this paper is based on the complexity of Parikh sets of families on Chomsky hierarchy in formal language theory. We show that an alga with almost no space closed to the environment, e.g., Gonium pectorale, can be characterized by PsFIN, one with a closed space and no cooperation, e.g., Eudorina elegans, by PsCF, and one with a closed space and cooperation, e.g., Volvox globator, by Ps lambda SC. This classification should provide new insights into the necessity for specific forms and degrees of cooperation in the volvocine algae. (c) 2005 Society for Mathematical Biology. Published by Elsevier Ltd. All rights reserved.

First, we consider P systems with active membranes, hence with the possibility that the membranes can be divided, with non-cooperating evolution rules (the objects always evolve separately). These systems are known to be able to solve NP-complete problems in linear time. Here we give a normal form theorem for such systems: their computational universality is preserved even if only the elementary membranes are divided. The possibility of solving SAT in linear time is preserved only when non-elementary membranes may also be divided under the influence of objects in their region.
Second, we consider a slight generalization, namely, we allow that a membrane can produce by division both a copy of itself and a copy of a membrane with a different label; again, only elementary membranes may be divided. In this case, we prove that the hierarchy on the maximal number of membranes present in the system collapses: three membranes at a time are sufficient in order to characterize the recursively enumerable sets of vectors of natural numbers. This result is optimal, two membranes are shown not to be sufficient.
Third, we consider P systems with cooperating rules (several objects may evolve together). Making use of this powerful feature, we show that many NP-complete problems can be solved in linear time in a quite uniform way (by systems which are very similar to each other), using only elementary membranes division (and not further ingredients, such as electrical charges). The degree of cooperation is minimal: two objects at a time. (C) 2004 Elsevier B.V. All rights reserved.

The aim of this paper is to try to understand the process of children's language acquisition by using the theory of inference of formal grammars. Toward this goal, we introduce an extension of Marcus External Contextual grammars which constitutes a Mildly Context-Sensitive language family, and study their learnability in the limit from positive data. Finally, we briefly indicate our future research direction.

We are concerned with a problem of checking the structure freeness of S+ for a given set S of DNA sequences. It is still open whether or not there exists an efficient algorithm for this problem. In this paper, we will give an efficient algorithm to check the structure freeness of S+ under the constraint that every sequence may form only linear secondary structures, which partially solves the open problem.

This paper concerns a subclass of simple deterministic grammars, called very simple grammars, and studies the problem of identifying the subclass in the limit from positive data. The class of very simple languages forms a proper subclass of simple deterministic languages and is incomparable to the class of regular languages. This class of languages is also known as the class of left Szilard languages of context-free grammars.
After providing some properties of very simple languages, we show that the class of very simple grammars is polynomial-time identifiable in the limit from positive data in the following sense. That is, we show that there effectively exists an algorithm that, given a target very simple grammar G(*) over alphabet Sigma, identifies a very simple grammar G equivalent to G(*) in the limit from positive data, satisfying the property that the time for updating a conjecture is bounded by O(m), and the total number of prediction errors made by the algorithm is bounded by O(n), where n is the size of G(*), m = Max{N\Sigma\+1, \Sigma\(3)} and N is the total length of all positive data provided. (C) 2002 Elsevier Science B.V. All rights reserved.

Gene insertion and deletion are basic phenomena found in DNA processing or RNA editing in molecular biology. The genetic mechanism and development based on these evolutionary transformations have been formulated as a formal system with two operations of insertion and deletion, called insertion-deletion systems ([1], [2]).
We investigate the generative power of insertion-deletion systems (InsDel systems), and show that the family (INS1DEL11)-D-1 is equal to the family of recursively enumerable languages. This gives a positive answer to an open problem posed in [2] where it was conjectured to be negative.

Molecules with hairpin structure(s) form a natural extension of linear non-branched molecules, and they have been already used in experimental work in DNA computing. In this paper we introduce and investigate classes of string languages (hence languages modeling the sets of linear DNA molecules), consisting of strings which can (fold on itself and) form hairpins. We classify the complexity of these classes using language-theoretic techniques. We also discuss a further use of hairpin molecules in DNA computing. © 2001 World Scientific Publishing Company.

Hairpin formation by single-stranded DNA molecules was exploited in a DNA-based computation in order to explore the feasibility of autonomous molecular computing. An instance of the satisfiability problem, a famous hard combinatorial problem, was solved by using molecular biology techniques. The satisfiability of a given Boolean formula was examined autonomously, on the basis of hairpin formation by the molecules that represent the formula. This computation algorithm can test several clauses in the given formula simultaneously, which could reduce the number of Laboratory steps required for computation.

In search for a universal splicing system, in this paper we present a Post system universal for the class of Post systems, and we discuss its translation into an extended splicing system with multiplicity. We also discuss the complexity of the resulting universal splicing system, comparing our result with recent known results about the translation of universal Turing machines into splicing systems. (C) 2000 Elsevier Science B.V. All rights reserved.

In this paper, we are concerned with identifying a subclass of tree adjoining grammars (TAGs) that is suitable for the application to modeling and predicting RNA secondary structures. The goal of this paper is twofold: For the purpose of applying to the RNA secondary structure prediction problem, we first introduce a special subclass of TAGs and develop a fast parsing algorithm for the subclass, together with some of its language theoretic characterizations. Then, based on the algorithm, we develop a prediction system and demonstrate the effectiveness of the system by presenting some experimental results obtained from biological data, where free energy evaluation selection for parse trees is incorporated into the algorithm. (C) 1999-Elsevier Science B.V. All rights reserved.

This paper concerns 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 alpha-chain region in amino acid sequences. First, we present a linear time algorithm that, given a strictly locally testable language, learns (identifies) its deterministic finite state automaton in the limit from only positive data. This provides us 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 alpha-chain region in amino acid sequences for hemoglobin. Experimental scores show an overall success rate of 95 percent correct identification for positive data, and 96 percent for negative data.

In algorithmic learning theory fundamental roles:are played by the family of languages that are locally testable in the strict sense and by the family of reversible languages. These two families are shown to be the first two members of an infinite sequence of families of regular languages the members of which are learnable in the limit from positive data only. A uniform procedure is given for deciding, for each regular language R and each of our specified families, whether R belongs to the family.: The approximation of arbitrary regular languages by languages belonging to these families is discussed. Further, we will:give a uniform scheme for learning these families from positive data. Several research problems are also suggested.

In this note, we consider the problem of learning approximately regular languages in the limit from positive data using the class of k-reversible languages. The class of k-reversible languages was introduced by Angluin (1982), and proved to be efficiently identifiable in the limit from positive data only. We show that Angluin's learning algorithm for the class of k-reversible languages can be readily adopted for the approximate identification of regular languages from positive data. Considering the negative result on the exact identifiability by Gold (1967), this approximation approach would be one of the best we could hope for learning the class of regular languages from positive data only.

From a biological motivation of interactions between linear and circular DNA sequences, we propose a new type of splicing models called circular H systems and show that they have the same computational power as Turing machines. It is also shown that there effectively exists a universal circular H system which can stimulate any circular H system with the same terminal alphabet, which strongly suggests a feasible design for a DNA computer based on circular splicing.

In this paper, we propose a method for biologically implementing simple Boolean formulae. This method enables us to compute logical consequences of a given set of simple Horn clauses in parallel and takes advantage of potentially huge number of molecular CPUs of DNA computers. Further, we show that the method is nicely applied to the parallel implementation of a grammatical recognition algorithm which is based on 'dynamic programming.'

We investigate the learning problem of two-tape deterministic finite automata (2-tape DFAs) from queries and counterexamples. Instead of accepting a subset of Sigma*, a 2-tape DFA over an alphabet Sigma accepts a subset of Sigma* x Sigma*, and therefore, it can specify a binary relation on Sigma*. 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 a minimally adequate teacher (MAT).
In this article we show that the class of 2-tape DFAs is learnable in polynomial time from MAT. More specifically, we show an algorithm that, given any language L accepted by an unknown 2-tape DFA M, learns from MAT a two-tape nondeterministic finite automaton (2-tape NFA) M' accepting L in time polynomial in n and l, where n is the size of M and l is the maximum length of any counterexample provided during the learning process.

It is of great significance to develop an efficient software system for higher-level structural prediction in RNA/protein sequences. Speaking of RNA secondary structure prediction, it is inevitably required that a prediction system must have an ability to deal with so-called "pseudoknot" structures, one of the most typical and important constructs found in vivo, while no effective system is yet reported for predicting RNA secondary structures involving in pseudoknots.<BR>We are developing prediction systems for RNA secondary structures thatcan handle pseudo-knots in an elegant manner, where the developing systems are constructed based on the following two ways.

This paper deals with the polynomial-time learnability of a language class in the limit from positive data, and discusses the learning problem of a subclass of deterministic finite automata (DFAs), called strictly deterministic antomata (SDAs), in the framework of learning in the limit from positive data. We first discuss the difficulty of Pitt's definition in the framework of learning in the limit from positive data, by showing that any class of languages with an infinite descending chain property is not polynomial-time learnable in the limit from positive data. We then propose new definitions for polynomial-lime learnability in the limit from positive data. We show in our new definitions that the class of SDAs is iteratively, consistently polynomial-time learnable in the limit from positive data. In particular, we present a learning algorithm that learns any SDA M in the limit from positive data, satisfying the properties that (i) the time for updating a conjecture is at most O(lm), (ii) the number of implicit prediction errors is at most O(ln), where l is the maximum length of all positive data provided, m is the alphabet size of M and n is the size of M, (iii) each conjecture is computed from only the previous conjecture and the current example, and (iv) at any stage the conjecture is consistent with the sample set seen so far. This is in marked contrast to the fact that the class of DFAs is neither learnable in the limit from positive data nor polynomial-time learnable in the limit.

Tree Adjunct Grammar for RNA (TAG²_RNA) is a new grammatical device to model RNA secondary structures including pseudoknots. An efficient parsing algorithm for this grammar is developed, and applied to some computational problems concerning RNA secondary structures. With this parser, we first try to predict secondary structures of RNA sequences which are known to form pseudoknots structures, and show prediction results which nicely match the known structures. Further, a (-1) frameshift grammar is constructed based on a biological observation that a (-1) frameshift might be caused from some structural features of RNA sequences. The proposed grammar is used to find candidate sequences for (-1) frameshift in Human spumaretrovirus gag and pol genes.

We propose a simple string similarity measure and apply it to the problem of DNA sequence analysis, more specifically, to the problem of analysing molecular evolution. This measure is based on a "local feature" that was motivated from a theoretical characterization on DNA splicing sequences.<BR>We demonstrate the usefulness of the proposed measure by presenting an experimental result which concerns evolutionary molecular analysis. This sheds new light on the other types of DNA sequence analysis such as protein classification, motif identification.

This paper concerns the learning of context-free grammars, and introduces a subclass which we call context-deterministic (c-deterministic) grammars. The corresponding language class properly contains the classes or regular languages and of even linear languages, and is incomparable to the classes or simple deterministic languages and of one-counter languages. We show that the class of c-deterministic grammars is learnable in polynomial time from (extended) minimally adequate teacher (MAT). which gives a generalization of the corresponding results on regular languages in Ref 3) and even-linear languages in Ref.9).

In this paper we present new methods for testing linguistic similarity using the concept of fuzzy relation. By applying a fuzzy clustering technique, we show that the problem of testing linguistic similarity can be regarded as a clustering problem under fuzzy conditions, and give some methods of measuring the similarity of natural languages.