Gheorghe Păun

TCS Journal 2018 Journal Article

A dozen of research topics in membrane computing

• Gheorghe Păun

This note considers three basic research directions in membrane computing – characterizations of the computing power of Turing machines, computing more than Turing machines, efficiency (solving computationally hard problems in a feasible time) – by basic classes of P systems (cell and tissue multiset rewriting systems, symport/antiport systems, spiking neural P systems, numerical P systems). (Types of) Results reported in the literature are briefly mentioned, several unsolved cases are pointed out, and directions of further research are proposed.

TCS Journal 2017 Journal Article

From finite state grammars to natural computing – In memory of Solomon Marcus

• Gheorghe Păun
• Ion Petre
• Grzegorz Rozenberg
• Arto Salomaa

TCS Journal 2017 Journal Article

On trace languages generated by (small) spiking neural P systems

• Haiming Chen
• Mihai Ionescu
• Andrei Păun
• Gheorghe Păun

We extend to spiking neural P systems a notion investigated in the “standard” membrane systems: the language of the traces of a distinguished object. In our case, we distinguish a spike by “marking” it and we follow its path through the neurons of the system, thus obtaining a language. Several examples are discussed and some preliminary results about this way of associating a language with a spiking neural P system are given, together with a series of topics for further research. For instance, we show that each regular language is the morphic image of a trace language intersected with a very particular regular language, while each recursively enumerable language over the one-letter alphabet is the projection of a trace language. In all proofs we try to keep the size of used systems (number of neurons, of rules in each neuron, of spikes consumed or removed by rules) as small as possible.

TCS Journal 2016 Journal Article

Cell-like spiking neural P systems

• Tingfang Wu
• Zhiqiang Zhang
• Gheorghe Păun
• Linqiang Pan

With mathematical motivation, we consider a combination of basic features of multiset-rewriting P systems and of spiking neural P systems, that is, we consider cell-like P systems with spiking rules in their membranes (hence dealing with only one kind of objects, the spikes). The universality of these systems as number generating devices is proved for the two usual ways to define the output (internally or externally) and for various restrictions on the spiking rules. Several research topics are also pointed out.

TCS Journal 2016 Journal Article

Flat maximal parallelism in P systems with promoters

• Linqiang Pan
• Gheorghe Păun
• Bosheng Song

In spite of the fact that many ways of using the evolution rules in a P system were already investigated, there is still a case, which we call the flat maximal parallelism, which appeared in several papers, but which deserves a more careful attention: in each step, in each membrane, a maximal set of applicable rules is chosen and each rule in the set is applied exactly once. In this work, flat maximal parallelism is studied for non-cooperating P systems with promoters. Specifically, we prove that non-cooperating P systems with at most one promoter associated with any rule, working in the flat maximally parallel way, are Turing universal (the Turing universality of such P systems is open if they work in the maximally parallel way). Moreover, a uniform solution to the SAT problem is provided by using non-cooperating P systems with promoters and membrane division, working in the flat maximal parallel way.

TCS Journal 2014 Journal Article

Spiking neural P systems with rules on synapses

• Tao Song
• Linqiang Pan
• Gheorghe Păun

Spiking neural P systems (SN P systems, for short) are a class of membrane systems inspired from the way the neurons process information and communicate by means of spikes. In this paper, we introduce and investigate a new class of SN P systems, with spiking rules placed on synapses. The computational completeness is first proved, then two small universal SN P systems with rules on synapses for computing functions are constructed. Specifically, when using standard spiking rules, we obtain a universal system with 39 neurons, while when using extended spiking rules on synapses, a universal SN P system with 30 neurons is constructed.

TCS Journal 2012 Journal Article

An infinite hierarchy of languages defined by dP systems

• Gheorghe Păun
• Mario J. Pérez-Jiménez

Here, we continue the study of the recently introduced dP automata. They are symport/antiport P systems consisting of a number of components, each one accepting a string, and working together in recognizing the concatenation of these separate strings; the overall string is distributed to the dP automaton components in a balanced way, i. e. , in equal parts up to one symbol, like in the communication complexity area. The question whether or not the number of components induces an infinite hierarchy of the recognized languages was formulated as an open problem in the literature. We solve here affirmatively this question (by connecting P automata with right linear simple matrix grammars), then we also briefly discuss the relation between the balanced and the non-balanced way of splitting the input string among components; settling this latter problem remains as a research topic. Some other open problems are also formulated.

TCS Journal 2012 Journal Article

P automata revisited

• Gheorghe Păun
• Mario J. Pérez-Jiménez

We continue here the investigation of P automata, in their non-extended case, a class of devices which characterize non-universal family of languages. First, a recent conjecture is confirmed: any recursively enumerable language is obtained from a language recognized by a P automaton, to which an initial (arbitrarily large) string is added. Then, we discuss possibilities of extending P automata, following suggestions from string finite automata. For instance, automata with a memory (corresponding to push-down automata) are considered and their power is briefly investigated, as well as some closure properties of the family of languages recognized by P automata. In the context, a brief survey of results about P and dP automata (a distributed version of P automata) is provided, and several further research topics are formulated.

TCS Journal 2012 Journal Article

Towards bridging two cell-inspired models: P systems and R systems

• Gheorghe Păun
• Mario J. Pérez-Jiménez

We examine, from the point of view of membrane computing, the two basic assumptions of reaction systems, the “threshold” and “no permanence” ones. In certain circumstances (e. g. , defining the successful computations by local halting), the second assumption can be incorporated in a transition P system or in a symport/antiport P system without losing the universality. The case of the first postulate remains open: the reaction systems deal, deterministically, with finite sets of symbols, which is not of much interest for computing; three ways to introduce nondeterminism are suggested and left as research topics.

TCS Journal 2010 Journal Article

Spiking neural P systems: An improved normal form

• Linqiang Pan
• Gheorghe Păun

Spiking neural P systems (in short, SN P systems) are computing devices based on the way the neurons communicate through electrical impulses (spikes). These systems involve various ingredients; among them, we mention forgetting rules and the delay in firing rules. However, it is known that the universality can be obtained without using these two features. In this paper we improve this result in two respects: (i) each neuron contains at most two rules (which is optimal for systems used in the generative mode), and (ii) the rules in the neurons using two rules have the same regular expression which controls their firing. This result answers a problem left open in the literature, and, in this context, an incompleteness in some previous proofs related to the elimination of forgetting rules is removed. Moreover, this result shows a somewhat surprising uniformity of the neurons in the SN P systems able to simulate Turing machines, which is both of a theoretical interest and it seems to correspond to a biological reality. When a bound is imposed on the number of spikes present in a neuron at any step of a computation (such SN P systems are called finite), two surprising results are obtained. First, a characterization of finite sets of numbers is obtained in the generative case (this contrasts the case of other classes of SN P systems, where characterizations of semilinear sets of numbers are obtained for finite SN P systems). Second, the accepting case is strictly more powerful than the generative one: all finite sets and also certain arithmetical progressions can be accepted. A precise characterization of the power of accepting finite SN P systems without forgetting rules and delay remains to be found.

TCS Journal 2009 Journal Article

Asynchronous spiking neural P systems

• Matteo Cavaliere
• Oscar H. Ibarra
• Gheorghe Păun
• Omer Egecioglu
• Mihai Ionescu
• Sara Woodworth

We consider here spiking neural P systems with a non-synchronized (i. e. , asynchronous) use of rules: in any step, a neuron can apply or not apply its rules which are enabled by the number of spikes it contains (further spikes can come, thus changing the rules enabled in the next step). Because the time between two firings of the output neuron is now irrelevant, the result of a computation is the number of spikes sent out by the system, not the distance between certain spikes leaving the system. The additional non-determinism introduced in the functioning of the system by the non-synchronization is proved not to decrease the computing power in the case of using extended rules (several spikes can be produced by a rule). That is, we obtain again the equivalence with Turing machines (interpreted as generators of sets of (vectors of) numbers). However, this problem remains open for the case of standard spiking neural P systems, whose rules can only produce one spike. On the other hand we prove that asynchronous systems, with extended rules, and where each neuron is either bounded or unbounded, are not computationally complete. For these systems, the configuration reachability, membership (in terms of generated vectors), emptiness, infiniteness, and disjointness problems are shown to be decidable. However, containment and equivalence are undecidable.

TCS Journal 2008 Journal Article

Membrane computing and brane calculi. Old, new, and future bridges

• Gheorghe Păun

After a short discussion about similarities and dissimilarities of membrane computing and brane calculi, insisting mainly on some recent ideas of bridging the two areas of research, one recalls some details concerning certain classes of P systems based on brane calculi operations. Several open problems are formulated in this context.

TCS Journal 2007 Journal Article

Fourth Brainstorming Week on Membrane Computing

• Gheorghe Păun
• Mario J. Pérez-Jiménez

TCS Journal 2007 Journal Article

Normal forms for spiking neural P systems

• Oscar H. Ibarra
• Andrei Păun
• Gheorghe Păun
• Alfonso Rodríguez-Patón
• Petr Sosík
• Sara Woodworth

The spiking neural P systems are a class of computing devices recently introduced as a bridge between spiking neural nets and membrane computing. In this paper we prove a series of normal forms for spiking neural P systems, concerning the regular expressions used in the firing rules, the delay between firing and spiking, the forgetting rules used, and the outdegree of the graph of synapses. In all cases, surprising simplifications are found, without losing the computational completeness — sometimes at the price of (slightly) increasing other parameters which describe the complexity of these systems.

TCS Journal 2007 Journal Article

P systems with minimal parallelism

• Gabriel Ciobanu
• Linqiang Pan
• Gheorghe Păun
• Mario J. Pérez-Jiménez

A current research topic in membrane computing is to find more realistic P systems from a biological point of view, and one target in this respect is to relax the condition of using the rules in a maximally parallel way. We contribute in this paper to this issue by considering the minimal parallelism of using the rules: if at least a rule from a set of rules associated with a membrane or a region can be used, then at least one rule from that membrane or region must be used, without any other restriction (e. g. , more rules can be used, but we do not care how many). Weak as it might look, this minimal parallelism still leads to universality. We first prove this for the case of symport/antiport rules. The result is obtained both for generating and accepting P systems, in the latter case also for systems working deterministically. Then, we consider P systems with active membranes, and again the usual results are obtained: universality and the possibility to solve NP-complete problems in polynomial time (by trading space for time).

TCS Journal 2006 Journal Article

Characterizations of context-sensitive languages and other language classes in terms of symport/antiport P systems

• Oscar H. Ibarra
• Gheorghe Păun

We give “syntactic’’ characterizations of context-sensitive languages (CSLs) in terms of some restricted models of symport/antiport P systems. These are the first such characterizations of CSLs in terms of P systems. In particular, we show the following for any language L over a binary alphabet: (1) Let m be any integer ≥ 1. Then L is a CSL if and only if it can be accepted by a restricted symport/antiport P system with m membranes and multiple number of symbols (objects). Moreover, holding the number of membranes at m, there is an infinite hierarchy in computational power (within the class of binary CSLs) with respect to the number of symbols. (2) Let s be any integer ≥ 14. Then L is a CSL if and only if it can be accepted by a restricted symport/antiport P system with s symbols and multiple number of membranes. Moreover, holding the number of symbols at s, there is an infinite hierarchy in computational power with respect to the number of membranes. (Similar results hold for languages over an alphabet of k ≥ 2 symbols.) Thus (1) and (2) say that in order for the restricted symport/antiport P systems to accept all binary CSLs, at least one parameter (either the number of symbols or the number of membranes) must grow. These are the first results of their kind in the P systems area. They contrast a known result that (unrestricted) symport/antiport P systems with s ≥ 2 symbols and m ≥ 1 membranes accept (or generate) exactly the recursively enumerable sets of numbers even for s + m = 6. We also note that previous characterizations of formal languages in the membrane computing literature are mostly for the Parikh images of languages. Variations of our model yield characterizations of regular languages, languages accepted by one-way log n space-bounded Turing machines, and recursively enumerable languages.

TCS Journal 2005 Journal Article

Context-free insertion–deletion systems

• Maurice Margenstern
• Gheorghe Păun
• Yurii Rogozhin
• Sergey Verlan

We consider a class of insertion–deletion systems which have not been investigated so far, those without any context controlling the insertion–deletion operations. Rather unexpectedly, we found that context-free insertion–deletion systems characterize the recursively enumerable languages. Moreover, this assertion is valid for systems with only one axiom, and also using inserted and deleted strings of a small length. As direct consequences of the main result we found that set-conditional insertion–deletion systems with two axioms generate any recursively enumerable language (this solves an open problem), as well as that membrane systems with one membrane having context-free insertion–deletion rules without conditional use of them generate all recursively enumerable languages (this improves an earlier result). Some open problems are also formulated.

TCS Journal 2005 Journal Article

Tissue P systems with channel states

• Rudolf Freund
• Gheorghe Păun
• Mario J. Pérez-Jiménez

We consider tissue-like P systems with states associated with the links (we call them synapses) between cells, controlling the passage of objects across the links. We investigate the computing power of such devices for the case of using—in a sequential manner—antiport rules of small weights. Systems with two cells are proved to be universal when having arbitrarily many states and minimal antiport rules, or one state and antiport rules of weight two. Also the systems with arbitrarily many cells, three states, and minimal antiport rules are universal. In contrast, the systems with one cell and any number of states and rules of any weight only compute Parikh sets of matrix languages (generated by matrix grammars without appearance checking); characterizations of Parikh images of matrix languages are obtained for such one-cell systems with antiport rules of a reduced weight.

TCS Journal 2004 Journal Article

From regulated rewriting to computing with membranes: collapsing hierarchies

• Rudolf Freund
• Carlos Martı́n-Vide
• Gheorghe Păun

In addressing certain problems about membrane computing, a recent and active branch of natural computing, it first was necessary to address certain problems from the area of regulated rewriting. Thus, the present paper is a contribution to both these domains. A central problem in membrane computing is that of the hierarchy with respect to the number of membranes: Are systems with n+1 membranes more powerful than systems with n membranes? Does the number of membranes induce an infinite hierarchy of the computed functions? Usually, when proving the universality of membrane systems (also called P systems), one starts from a matrix grammar and the number of membranes depends on the number of non-terminal symbols used by this grammar in the so-called appearance checking mode. We first prove that recursively enumerable languages can be generated by matrix grammars with only two non-terminal symbols being used in the appearance checking mode. The proofs of this fact and of several related results are based on a simulation of register machines by means of graph-controlled grammars. Then, we consider three classes of membrane systems, and in all the three cases the hierarchies with respect to the number of membranes are shown to collapse at level four: systems with four membranes are computationally universal (but we do not know whether or not this result is optimal).

TCS Journal 2004 Journal Article

On the power of membrane division in P systems

• Gheorghe Păun
• Yasuhiro Suzuki
• Hiroshi Tanaka
• Takashi Yokomori

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.

TCS Journal 2003 Journal Article

On three variants of rewriting P systems

• Claudio Ferretti
• Giancarlo Mauri
• Gheorghe Păun
• Claudio Zandron

We continue here the study of P systems with string objects processed by rewriting rules, by investigating some questions which are classic in formal language theory: leftmost derivation, conditional use of rules (permitting and forbidding conditions), relationships with language families in Chomsky and Lindenmayer hierarchies.

TCS Journal 2003 Journal Article

PC grammar systems with five context-free components generate all recursively enumerable languages

• Erzsébet Csuhaj-Varjú
• Gheorghe Păun
• György Vaszil

Parallel communicating grammar systems (PC grammar systems, in short) are language generating devices consisting of several context-free grammars which work synchronously on their own sentential forms and communicate the generated strings to each other by request. These systems with eleven components are known to have the power of the Turing machines. We considerably improve this result, proving that five components suffice in order to generate any recursively enumerable language.

TCS Journal 2003 Journal Article

Tissue P systems

• Carlos Martín-Vide
• Gheorghe Păun
• Juan Pazos
• Alfonso Rodríguez-Patón

Starting from the way the inter-cellular communication takes place by means of protein channels (and also from the standard knowledge about neuron functioning), we propose a computing model called a tissue P system, which processes symbols in a multiset rewriting sense, in a net of cells. Each cell has a finite state memory, processes multisets of symbol-impulses, and can send impulses (“excitations”) to the neighboring cells. Such cell nets are shown to be rather powerful: they can simulate a Turing machine even when using a small number of cells, each of them having a small number of states. Moreover, in the case when each cell works in the maximal manner and it can excite all the cells to which it can send impulses, then one can easily solve the Hamiltonian Path Problem in linear time. A new characterization of the Parikh images of ET0L languages is also obtained in this framework. Besides such basic results, the paper provides a series of suggestions for further research.

TCS Journal 2002 Journal Article

A guide to membrane computing

• Gheorghe Păun
• Grzegorz Rozenberg

Membrane systems are models of computation which are inspired by some basic features of biological membranes. In a membrane system multisets of objects are placed in the compartments defined by the membrane structure, and the objects evolve by means of “reaction rules” also associated with the compartments, and applied in a maximally parallel, nondeterministic manner. The objects can pass through membranes, the membranes can change their permeability, they can dissolve, and they can divide. These features are used in defining transitions between configurations of the system, and sequences of transitions are used to define computations. In the case of symbol-objects, we compute a set of numbers, and in the case of string-objects we compute a set of strings, hence a language. Many different classes of such computing devices (now called P systems) have already been investigated. Most of them are computationally universal, i. e. , equal in power to Turing machines. Systems with an enhanced parallelism are able to trade space for time and solve in this way (at least in principle), by making use of an exponential space, intractable problems in a feasible time. The present paper presents the basic ideas of computing with membranes and some fundamental properties (mostly concerning the computational power and efficiency) of P systems of various types 1 1 The current bibliography of membrane computing can be found at the web address http: //bioinformatics. bio. disco. unimib. it/psystems.

TCS Journal 2002 Journal Article

Membrane systems with carriers

• Carlos Martı́n-Vide
• Gheorghe Păun
• Grzegorz Rozenberg

A membrane system is a model of computation which is inspired by some basic features of biological membranes. In this paper we consider another biologically inspired notion, viz. , the notion of a carrier (or vehicle), as, e. g. , used in gene cloning. We investigate the power of membrane systems where the rules for the evolving of objects are replaced by the rules that carry objects (by vehicles) through membranes. It turns out that these systems (even with a small number of membranes, a small number of carriers, and a small number of passengers taken by carriers) are computationally universal.

TCS Journal 2002 Journal Article

Topics in the theory of DNA computing

• Martyn Amos
• Gheorghe Păun
• Grzegorz Rozenberg
• Arto Salomaa

DNA computing, or, more generally, molecular computing, is an exciting fast developing interdisciplinary area. Research in this area concerns theory, experiments, and applications of DNA computing. In this paper, we demonstrate the theoretical developments by discussing a number of selected topics. We also give an introduction to the basic structure of DNA and the basic DNA processing tools.

TCS Journal 2001 Journal Article

Formal properties of PA-matching

• Satoshi Kobayashi
• Victor Mitrana
• Gheorghe Păun
• Grzegorz Rozenberg

We consider the PA-matching operation, used in DNA computing, as a formal operation on strings and languages. We investigate the closure of various families of languages under this operation, representations of recursively enumerable languages and decision problems. We also consider the dual operation of overlapping strings. All closure properties of families in the Chomksy hierarchy under both non-iterated and iterated PA-matching and overlapping operations are settled.

TCS Journal 2000 Journal Article

DNA computing based on splicing: universality results

• Gheorghe Păun

First, we recall some characterizations of recursively enumerable languages by means of finite H systems with certain regulations on the splicing operation. Then, we consider a variant of the splicing operation where the splicing proceeds always in couples of steps: the two strings obtained after a splicing enter immediately a second splicing (the rules used in the two steps are not prescribed). Somewhat surprising if we take into account the loose control on the performed operations, extended H systems with finite sets of axioms and of splicing rules, using this double splicing operation, can again characterize the recursively enumerable languages. Finally, we consider two types of distributed H systems: communicating distributed H systems and time-varying distributed H systems. For the first type of devices, we give a new proof of the recent result of [25] that (in the extended case) such systems with three components characterize the recursively enumerable languages. In what concerns the second mentioned distributed model, we prove that time-varying H systems with seven components can characterize the recursively enumerable languages. The optimality of these two last-mentioned results is open.

TCS Journal 1998 Journal Article

Characterizations of recursively enumerable languages by means of insertion grammars

• Carlos Martin-Vide
• Gheorghe Păun
• Arto Salomaa

An insertion grammar is based on pure rules of the form uv → uxv (the string x is inserted in the context (u, v)). A strict subfamily of the context-sensitive family is obtained, incomparable with the family of linear languages. We prove here that each recursively enumerable language can be written as the weak coding of the image by an inverse morphism of a language generated by an insertion grammar (with the maximal length of strings u, v as above equal to seven). This result is rather surprising in view of some closure properties established earlier in the literature. Some consequences of this result are also stated. When also erasing rules of the form uxv → uv are present (the string x is erased from the context (u, v)), then a much easier representation of recursively enumerable languages is obtained, as the intersection with V∗ of a language generated by an insertion grammar with erased strings (having the maximal length of strings u, v as above equal to two).

TCS Journal 1998 Journal Article

Sticker systems

• Gheorghe Păun
• Grzegorz Rozenberg

Sticker systems is a computational model which is an abstraction of the way that the Watson-Crick complementarity is used in DNA computing. We consider such systems of a general form, with blocks of arbitrary shapes to be annealed to the currently built sequences. We investigate the generative power of several variants of sticker systems. Characterizations of regular, linear, and recursively enumerable languages are obtained in this framework.

TCS Journal 1996 Journal Article

Computing by splicing

• Gheorghe Păun
• Grzegorz Rozenberg
• Arto Salomaa

Computing by splicing is a new powerful tool stemming originally from molecular genetics. This new model of computing, splicing systems, is investigated here. Several variants, resulting from the use of the rules in different ways, are considered. The power of such systems with very weak structure imposed on rules turns out to be very large. Characterizations of recursively enumerable languages are obtained for many variants. In this way our study is analogous to the early studies concerning variations of Turing machines. Other classes of such splicing systems generate only regular or context-free languages (giving, in fact, characterizations of these families). With a few exceptions, we are able to obtain precise characterizations for all resulting families.

TCS Journal 1996 Journal Article

Pattern systems

• Victor Mitrana
• Gheorghe Păun
• Grzegorz Rozenberg
• Arto Salomaa

We introduce a model that covers the recent studies on pattern languages (with or without erasing), multi-pattern languages, iterated pattern languages and languages of pattern grammars. The model, referred to as a pattern system, provides a uniform framework for all such studies. Moreover, it gives a new method of investigating certain basic families of developmental languages. This paper investigates the basics of the main types (general, synchronized, deterministic) of pattern systems. Open problems and topics for further research will be pointed out.