Wyniki wyszukiwania - BazTech

1

The Hamiltonian Cycle and Travelling Salesman Problems in cP Systems

Cooper James, Nicolescu Radu

Fundamenta Informaticae

|

2019

|

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.

2

P Systems Simulating Bacterial Conjugation : Universality and Properties

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

Fundamenta Informaticae

|

2017

|

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.

3

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

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

Fundamenta Informaticae

|

2015

|

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.

4

Simulating P Systems on GPU Device : A Survey

Martínez-del-Amor M. A., García-Quismondo M., Macías-Ramos L. F., Valencia-Cabrera L., Riscos-Núñez A., Pérez-Jiménez M. J.

Fundamenta Informaticae

|

2015

|

Vol. 136, nr 3

269--284

EN

P systems have been proven to be useful as modeling tools in many fields, such as Systems Biology and Ecological Modeling. For such applications, the acceleration of P system simulation is often desired, given the computational needs derived from these kinds of models. One promising solution is to implement the inherent parallelism of P systems on platforms with parallel architectures. In this respect, GPU computing proved to be an alternative to more classic approaches in Parallel Computing. It provides a low cost, and a manycore platform with a high level of parallelism. The GPU has been already employed to speedup the simulation of P systems. In this paper, we look over the available parallel P systems simulators on the GPU, with special emphasis on those included in the PMCGPU project, and analyze some useful guidelines for future implementations and developments.

5

Sevilla Carpets Revisited : Enriching the Membrane Computing Toolbox

Orellana-Martín D., Graciani C., Macías-Ramos L.-F., Martínez-del-Amor M. A., Riscos-Núñez A., Romero-Jiménez A., Valencia-Cabrera L.

Fundamenta Informaticae

|

2014

|

Vol. 134, nr 1/2

153--166

EN

Sevilla carpets have already been used to compare different solutions of the Subset Sum problem: either designed in the framework of P systems with active membranes (both in the case of membrane division and membrane creation), and in the framework of tissue-like P systems with cell division. Recently, the degree of parallelism and other descriptive complexity details have been found to be relevant when designing parallel simulators running on GPUs. We present here a new way to use the information provided by Sevilla carpets in this context, and a script that allows to generate them automatically from P-Lingua files.

6

Regularising Ill-posed Discrete Optimisation: Quests with P Systems

Nicolescu R., Gimel’farb G., Morris J., Delmas P., Gong R.

Fundamenta Informaticae

|

2014

|

Vol. 131, nr 3-4

465--483

EN

We propose a novel approach to justify and guide regularisation of an ill-posed one-dimensional global optimisation with multiple solutions using a massively parallel (P system) model of the solution space. Classical optimisation assumes a well-posed problem with a stable unique solution. Most of important practical problems are ill posed due to an unstable or non-unique global optimum and are regularised to get a unique best-suited solution. Whilst regularisation theory exists largely for unstable unique solutions, its recommendations are often routinely applied to inverse optical problems with essentially non-unique solutions, e.g. computer stereo vision or image segmentation, typically formulated in terms of global energy minimisation. In these cases the recommended regularisation becomes purely heuristic and does not guarantee a unique solution. As a result, classical optimisation algorithms: dynamic programming (DP) and belief propagation (BP) – meet with difficulties. Our recent concurrent propagation (CP), leaning upon the P systems paradigm, extends DP and BP to always detect whether the problem is ill posed or not and store in the ill-posed case an entire space of solutions that yield the same global optimum. This suggests a radically new path to proper regularisation: select the best-suited unique solution by exploring statistical and structural features of this space. We propose a P systems based implementation of CP and set out as a case study an application of CP to the image matching problem in stereo vision.

7

On Controlled P Systems

Krithivasan K., Păun G., Ramanujan A.

Fundamenta Informaticae

|

2014

|

Vol. 131, nr 3-4

451--464

EN

We introduce and briefly investigate P systems with controlled computations. First, P systems with label restricted transitions are considered (in each step, all rules used have either the same label, or, possibly, the empty label, λ), then P systems with the computations controlled by languages (as in context-free controlled grammars). The relationships between the families of sets of numbers computed by the various classes of controlled P systems are investigated, also comparing them with length sets of languages in Chomsky and Lindenmayer hierarchies (characterizations of the length sets of ET0L and of recursively enumerable languages are obtained in this framework). A series of open problems and research topics are formulated.

8

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

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

Fundamenta Informaticae

|

2010

|

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.

9

Timed P Automata

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

Fundamenta Informaticae

|

2009

|

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.

10

Partial Halting and Minimal Parallelism Based on Arbitrary Rule Partitions

Alhazov A., Oswald M., Freund R., Verlan S.

Fundamenta Informaticae

|

2009

|

Vol. 91, nr 1

17-34

EN

We consider a new variant of the halting condition in P systems, i.e., a computation in a P system is already called halting if not for all membranes a rule is applicable anymore at the same time, whereas usually a computation is called halting if no rule is applicable anymore in the whole system. This new variant of partial halting is especially investigated for several variants of P systems using membrane rules with permitting contexts and working in different transition modes, especially for minimal parallelism. Both partial halting and minimal parallelism are based on an arbitrary set of subsets from the set of rules assigned to the membranes.

11

Array P Systems and t-Communication

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

Fundamenta Informaticae

|

2009

|

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.

12

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

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

Fundamenta Informaticae

|

2008

|

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.

13

A P Systems Flat Form Preserving Step-by-step Behaviour

Barbuti R., Maggiolo-Schettini A., Milazzo P., Tini S.

Fundamenta Informaticae

|

2008

|

Vol. 87, nr 1

1-34

EN

Starting from a compositional operational semantics of transition P Systems we have previously defined, we face the problem of developing an axiomatization that is sound and complete with respect to some behavioural equivalence. To achieve this goal, we propose to transform the systems into a normal form with an equivalent semantics. As a first step, we introduce axioms which allow the transformation of membrane structures into flat membranes. We leave as future work the further step that leads to the wanted normal form.

14

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

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

Fundamenta Informaticae

|

2007

|

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.

15

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

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

Fundamenta Informaticae

|

2006

|

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.

16

On P Systems and Almost Periodicity

Bernardini F., Gheorghe M., Manca V.

Fundamenta Informaticae

|

2005

|

Vol. 64, nr 1-4

29-42

EN

The study of P systems as a mathematical model for biological systems is an important research topic in the area of membrane computing. In this respect, the detection of periodicity and almost periodicity as aspects of the system dynamics seems to be of particular relevance for understanding many biological processes and their related phenomena. This paper introduces specific notions of periodicity and almost periodicity for (infinite) sequences of multisets, which are used to describe the dynamics of P systems. Specifically, a variant of P systems, called P systems with resources, is considered where the rules always consume a certain amount of resources, which are provided in the form of a periodic input sequence of multisets. It is then shown that P systems with resources are computationally complete (when halting computations are considered) and that, in general, they can generate sequences of multisets that are not even almost periodic (once the constraint of having halting computation is released). However, if P systems with resources are restricted to be deterministic, it is shown that a characterization of the behaviour of a particular class of P systems with resources can be obtained in terms of almost periodicty.

17

Further Results on Contextual and Rewriting P Systems

Krishna S. N., Rama R., Ramesh H.

Fundamenta Informaticae

|

2005

|

Vol. 64, nr 1-4

241-253

EN

In this paper, we continue the study of contextual and rewriting P systems. In contextual P systems, we improve a universality result avoiding the extended feature and by using rules of small weight. In rewriting P systems, we have two (rather surprising) universality results, both of them using three membranes, for non-extended systems with replicated rewriting and with leftmost rewriting, respectively.

18

Tree operations in P systems and [lambda]-calculus

Jonoska N., Margenstern M.

Fundamenta Informaticae

|

2004

|

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.

19

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

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

Fundamenta Informaticae

|

2003

|

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 Topological Structures of Membrane Computing

Giavitto J-L., Michel O.

Fundamenta Informaticae

|

2002

|

Vol. 49, nr 1-3

123-145

EN

In its initial presentation, the P system formalism describes the topology of the membranes as a set of nested regions. In this paper, we present an algebraic structure developped in combinatorial topology that can be used to describe finer adjacency relationships between membranes. Using an appropriate abstract setting, this technical device enables us to reformulate also the computation within a membrane and proposes a unified view on several computational mechanisms initially inspired by biological processes. These theoretical tools are instantiated in MGS, an experimental programming language handling various types of membrane structures in a homogeneous and uniform syntax.