Wyniki wyszukiwania - Biblioteka Nauki

1

P System Software Simulator

100%

Ciobanu G. , Paraschiv D.

Fundamenta Informaticae

|

2002

|

tom Vol. 49, nr 1-3

61-66

EN

We present a software application that is intended to be a tool for people working with P systems. This software tool is called the Membrane Simulator and it provides a graphical simulation for two variants of P systems: the initial version of the catalytic hierarchical cell system and the active membrane system.

2

Grammar Systems versus Membrane Computing: The Case of CD Grammar Systems

63%

Csuhaj-Varjú E. , Paun G. , Vaszil G.

Fundamenta Informaticae

|

2007

|

tom Vol. 76, nr 3

271-292

EN

In this paper we discuss some relationships between grammar systems and P systems (membrane systems), two areas of computer science dealing with distributed computing models, but with different motivations and different types of basic ingredients. We extend one of the most important communication protocols of cooperating distributed (CD) grammar systems, the so-called t-derivation mode, to P systems with string-objects: if no rule can be applied to a string in a region of a P system, then the string is moved to a neighbouring region, depending on the communication mode either in exactly one direction (in or out) or in both directions. We describe the computational power of the obtained classes of P systems in comparison with families of languages generated by grammars in the Chomsky hierarchy or with CD grammar systems and formulate several problems for future research.

3

Recursive Calculus with Membranes

63%

Atanasiu A. , Martin-Vide C.

Fundamenta Informaticae

|

2002

|

tom Vol. 49, nr 1-3

45-59

EN

P systems are computing models where certain objects evolve in parallel in a hierarchical membrane structure. Recent results show that this model is a promising framework for solving NP-complete problems in polynomial time. A variant of P systems with active membranes is proposed in this paper. It uses a new operation called ``subordonation", based on the process of ``endocytosis" of membranes: a membrane can be entirely absorbed by another membrane, preserving its content. This class of P systems with active membranes can compute all Turing computable mappings. Arithmetical operations defined in [1] can be obtained as particular cases of primitive recursive functions, but with a higher complexity degree.

4

Tree operations in P systems and [lambda]-calculus

63%

Jonoska N. , Margenstern M.

Fundamenta Informaticae

|

2004

|

tom Vol. 59, nr 1

67-90

EN

In this paper we introduce a membrane system (named lP systems) in which the computation is performed through certain operations on the tree structure of the membranes. The objects within the membranes play the role of catalysts for the operations. The result of the computation is the final configuration of the system. We show that lP systems can simulate pure l-calculus and so they have universal computational power. We also show that NP-complete problems can be solved in polynomial time in this way by showing that 3SAT is solvable in linear time with linear input.

5

Timed P Automata

63%

Barbuti R. , Maggiolo-Schettini A. , Milazzo P. , Tesei L.

Fundamenta Informaticae

|

2009

|

tom Vol. 94, nr 1

1-19

EN

To study systems whose dynamics changes with time, an extension of timed P systems is introduced in which evolution rules may vary with time. The proposed model is a timed automaton with a discrete time domain and in which each state is a timed P system. A result on expressive power and on features of the formalism sufficient for full expressiveness is proved and, as an application example, the model of an ecological system is given.

6

On synchronization in P systems

51%

Paun G. , Yu S.

Fundamenta Informaticae

|

1999

|

tom Vol. 38, Nr 4

397-410

EN

The P systems were recently introduced as distributed parallel computing models of a biochemical type. Multisets of objects are placed in a hierarchical structure of membranes and they evolve according to given rules, which are applied in a synchronous manner: at each step, all objects which can evolve, from all membranes, must evolve. We consider here the case when this restriction is removed. As expected, unsynchronized systems (even using catalysts) are weaker than the synchronized ones, providing that no priority relation among rules is considered. The power of P systems is not diminished when a priority is used and, moreover, the catalysts can change their states, among two possible states for each catalyst.

7

A Quantum-Inspired Evolutionary Algorithm Based on P systems for Knapsack Problem

51%

Zhang G.-X. , Gheorghe M. , Wu C.-Z.

Fundamenta Informaticae

|

2008

|

tom Vol. 87, nr 1

93-116

EN

This paper introduces an evolutionary algorithm which uses the concepts and principles of the quantum-inspired evolutionary approach and the hierarchical arrangement of the compartments of a P system. The P system framework is also used to formally specify this evolutionary algorithm. Extensive experiments are conducted on a well-known combinatorial optimization problem, the knapsack problem, to test the effectiveness of the approach. These experimental results show that this evolutionary algorithm performs better than quantum-inspired evolutionary algorithms, for certain arrangements of the compartments of the P system structure utilized.

8

(Tissue) P Systems with Unit Rules and Energy Assigned to Membranes

51%

Alhazov A. , Freund R. , Leporati A. , Oswald M. , Zandron C.

Fundamenta Informaticae

|

2006

|

tom Vol. 74, nr 4

391-408

EN

We introduce a new variant of membrane systems where the rules are directly assigned to membranes and, moreover, every membrane carries an energy value that can be changed during a computation by objects passing through the membrane. The result of a successful computation is considered to be the distribution of energy values carried by the membranes. We show that for systems working in the sequential mode with a kind of priority relation on the rules we already obtain universal computational power. When omitting the priority relation, we obtain a characterization of the family of Parikh sets of languages generated by context-free matrix grammars. On the other hand, when using the maximally parallel mode, we do not need a priority relation to obtain computational completeness. Finally, we introduce the corresponding model of tissue P systems with energy assigned to the membrane of each cell and objects moving from one cell to another one in the environment as well as being able to change the energy of a cell when entering or leaving the cell. In each derivation step, only one object may pass through the membrane of each cell. When using priorities on the rules in the sequential mode (where in each derivation step only one cell is affected) as well as without priorities in the maximally parallel mode (where in each derivation step all cells possible are affected) we again obtain computational completeness, whereas without priorities on the rules in the sequential mode we only get a characterization of the family of Parikh sets of languages generated by context-free matrix grammars.

9

Uniform Solution to Common Algorithmic Problem by P Systems Working in the Minimally Parallel Mode

51%

Niu Y. , Venkat I. , Khader A. T. , Subramanian K. G.

Fundamenta Informaticae

|

2015

|

tom Vol. 136, nr 3

285--296

EN

It is known that the Common Algorithmic Problem (CAP) has the nice property that several other NP-complete problems can be reduced to it in linear time. The decision version of this problemis known to be efficiently solved by a family of recognizer P systems with activemembranes with three electrical charges working in the maximally parallel way. We here work with a variant of P systems with active membranes without polarizations and present a uniform solution to CAP in the minimally parallel mode.

10

A Formalization of Transition P Systems

51%

Jiménez M. J. , Sancho-Caparrini F.

Fundamenta Informaticae

|

2002

|

tom Vol. 49, nr 1-3

261-272

EN

In this paper we give a complete formalization of a new computability model of a distributed parallel type which is inspired by some basic features of living cells: transition P systems as they were given in [3], addressed with completely different techniques than in [1] and [2]. For this, we present a formal syntax and semantic of the transition P systems capturing the synchronized work of P systems, and the nondeterministic and maximally parallel manner in which the rules of these systems can be applied.

11

A Direct Construction of a Universal P System

51%

Frisco P. , Hoogeboom H. J. , Sant P.

Fundamenta Informaticae

|

2002

|

tom Vol. 49, nr 1-3

103-122

EN

We present a direct universal P system based on splicing. Our approach differs from those shown in previous papers as the P system we construct takes as input an encoding of another P system. Previous results were based on the simulation of universal type-0 grammars or Turing machines. We think that the approach we use can be applied to other variants of P systems.

12

A C Library for Simulating P Systems

51%

Nicolau Jr D. V. , Solana G. , Fulga F. , Nicolau D. V.

Fundamenta Informaticae

|

2002

|

tom Vol. 49, nr 1-3

241-248

EN

The present paper describes an ANSI C library which has been developed to facilitate the implementation and simulation of P systems on a computer. Simple data structures are proposed which permit the representation of membranes and their associated objects, and facilities are provided for implementing both ``active" and ``non-active" membrane systems, including actions for dissolving a membrane, dividing an existing membrane and creating a new membrane

13

On the Power of P Systems with DNA-Worm-Objects

51%

Maté J. L. , Rodriguez-Patón A. , Silva A.

Fundamenta Informaticae

|

2002

|

tom Vol. 49, nr 1-3

229-239

EN

We introduce a variant of P systems with string-objects - called worm-objects - inspired in the DNA computing area. These systems work with multisets of string-objects processed by splitting, mutation, replication and recombination. This model is simpler (we eliminate the replication operation) and more realistic (the recombination operation is changed by the simpler one of suffix-prefix or head-tail concatenation developed in the DNA computing framework) than the previous one. The result of a computation is the set of strings sent out of the system. We work with multisets of strings but we generate languages instead of sets of numbers. We prove that, without priority among rules or other control mechanisms, (1) these P systems with at most three membranes can generate all recursively enumerable languages, (2) with non-decreasing length mutation and splitting rules, three membranes are enough to generate the family of context-sensitive languages, and (3) with these restricted types of splitting and mutation rules, four membranes can generate the family of recursively enumerable languages.

14

Simulations of Photosynthesis by a K-Subset Transforming System with Membrane

51%

Nishida T. Y.

Fundamenta Informaticae

|

2002

|

tom Vol. 49, nr 1-3

249-259

EN

By considering the inner regions of living cells' membranes, P systems with inner regions are introduced. Then, a new type of membrane computing systems are considered, called K-subset transforming systems with membranes, which can treat nonintegral multiplicities of objects. As an application, a K-subset transforming system is proposed in order to model the light reactions of the photosynthesis. The behaviour of such systems is simulated on a computer.

15

P Systems with Replicated Rewriting and Stream X-Machines (Eilenberg Machines)

51%

Aguado J. , Balanescu T. , Cowling T. , Gheorghe M. , Holcombe M. , Ipate F.

Fundamenta Informaticae

|

2002

|

tom Vol. 49, nr 1-3

17-33

EN

The aim of this paper is to show how the P systems with replicated rewriting can be modeled by X-machines (also called Eilenberg machines). In the first approach, the parallel behaviour of the regions of a P system is simulated by a sequential process involving a single X-machine. This allows the application of the X-machine testing procedures in order to prove the correctness of P systems. In the second approach, a P system is simulated by a communicating system of X-machines. Each component of such a system is an X-machine associated with a region of the given P system. The components act in parallel, as their counterparts do in a P system, and use some specific mechanism for communication and synchronisation.

16

A Notion of Biological Diagnosability Inspired by the Notion of Opacity in Systems Security

51%

Barbuti R. , Maggiolo-Schettini A. , Milazzo P. , Gruska D. P.

Fundamenta Informaticae

|

2010

|

tom Vol. 102, nr 1

19-34

EN

A formal model for diagnostics of biological systems modelled as P systems is presented. We assume the presence of some biologically motivated changes (frequently pathological) in the systems behavior and investigate when these changes could be diagnosed by an external observer by exploiting some techniques originally developed for reasoning on system security.

17

Array P Systems and t-Communication

51%

Subramanian K. G. , Ali R. M. , Nagar A. K. , Margenstern M.

Fundamenta Informaticae

|

2009

|

tom Vol. 91, nr 1

145-159

EN

The two areas of grammar systems and P systems, which have provided interesting computational models in the study of formal string language theory have been in the recent past effectively linked in [4] by incorporating into P systems, a communication mode called t-mode of cooperating distributed grammar systems. On the other hand cooperating array grammar systems [5] and array P systems [1] have been developed in the context of two-dimensional picture description. In this paper, motivated by the study of [4], these two systems are studied by linking them through the t-communication mode, thus bringing out the picture description power of these systems.

18

P Systems Simulating Bacterial Conjugation : Universality and Properties

51%

Păun A. , Rodríguez-Patón A.

Fundamenta Informaticae

|

2017

|

tom Vol. 153, nr 1/2

87--103

EN

We refine the modeling in the P systems area of the way bacteria transmit genetic information in bacterial colonies, specifically the conjugation process. We study this new model from the computational power perspective using methods and ideas in the area; we are able to prove the universality of these systems. We show that systems working in a homogeneous manner and using only 75 species of objects in the regions and 13 species of "on-membrane" objects are enough for reaching universality. The system starts in a initial state with only few (nine) bacteria needed and the "bacteria" from this system are homogeneous, all have the same rules.

19

Solving a PSPACE-Complete Problem by Recognizing P Systems with Restricted Active Membranes

51%

Alhazov A. , Martin-Vide C. , Pan L.

Fundamenta Informaticae

|

2003

|

tom Vol. 58, nr 2

67--77

EN

P systems are parallel molecular computing models based on processing multisets of objects in cell-like membrane structures. Recently, Petr Sosík has shown that a semi-uniform family of P systems with active membranes and 2-division is able to solve the PSPACE-complete problem QBF-SAT in linear time; he has also conjectured that the membrane dissolving rules of the (d) type may be omitted, but probably not the (f) type rules for non-elementary membrane division. In this paper, we partially confirm the conjecture proving that dissolving rules are not necessary. Moreover, the construction is now uniform. It still remains open whether or not non-elementary membrane division is needed.

20

The Hamiltonian Cycle and Travelling Salesman Problems in cP Systems

44%

Cooper J. , Nicolescu R.

Fundamenta Informaticae

|

2019

|

tom Vol. 164, nr 2-3

157--180

EN

The Hamiltonian Cycle Problem (HCP) and Travelling Salesman Problem (TSP) are long-standing and well-known NP-hard problems. The HCP is concerned with finding paths through a given graph such that those paths visit each node exactly once after the start, and end where they began (i.e., Hamiltonian cycles). The TSP builds on the HCP and is concerned with computing the lowest cost Hamiltonian cycle on a weighted (di)graph. Many solutions to these problems exist, including some from the perspective of P systems. For the TSP however, almost all these papers have combined membrane computing with other approaches for approximate solution algorithms, which is surprising given the plethora of P systems solutions to the HCP. A recent paper presented a brute-force style P systems solution to the TSP with a time complexity of O(n2), exploiting the ability of P systems to reduce time complexity in exchange for space complexity, but the resultant system had a fairly high number of rules, around 50. Inspired by this paper, and seeking a more concise representation of an exact brute-force TSP algorithm, we have devised a P systems algorithm based on cP systems (P systems with Complex Objects) which requires five rules and takes n + 3 steps. We first provide some background on cP systems and demonstrate a fast new cP systems method to find the minimum of a multiset, then describe our solution to the HCP, and build on that for our TSP algorithm. This paper describes said algorithms, and provides an example application of our TSP algorithm to a given graph and a digraph variant.