Fundamenta Informaticae - Volume 49, issue 1-3

Authors: Martín-Vide, Carlos | Păun, Gheorghe

Article Type: Other

Keywords:

Citation: Fundamenta Informaticae, vol. 49, no. 1-3, pp. i-ii, 2002

Authors: Martín-Vide, Carlos | Păun, Andrei | Păun, Gheorghe | Rozenberg, Grzegorz

Article Type: Research Article

Abstract: This paper continues research on membrane systems which function by communication only, meaning that there are no evolving rules for molecules. The whole computation process relies on passage of molecules through membranes -- this provides communication between regions of the membrane system. Next to transport of single molecules through membranes (uniport) we also study a coupled transport of molecules, with two molecules passing either in the same direction (symport) or in opposite directions (antiport). We study …the computational power of such membrane systems and prove that using only symport one gets Turing universality. Moreover, we prove that five membranes suffice to get Turing universality, and the number of membranes can be decreased to three if forbidding context conditions for transport are used. Show more

Keywords:

Citation: Fundamenta Informaticae, vol. 49, no. 1-3, pp. 1-15, 2002

Authors: Aguado, Joaquin | Balanescu, Tudor | Cowling, Tony | Gheorghe, Marian | Holcombe, Mike | Ipate, Florentin

Article Type: Research Article

Abstract: 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. Show more

Keywords: P Systems, Finite state machines, (Stream) X-machines, Formal specifications

Citation: Fundamenta Informaticae, vol. 49, no. 1-3, pp. 17-33, 2002

Authors: Ardelean, Ioan I.

Article Type: Research Article

Abstract: This paper presents the stucture, organization (hierarchy) and function of cell membrane in bacteria, with special emphasis on: i) the hierarchy of cell membranes in Gram-negative and Gram-positive bacteria, ii) two main criteria for the classification of transport of ions and molecules across cell membrane, iii) two important mechanisms of transport – symport and antiport, and iv) the relevance of these biological realities for working concepts in P systems such as membrane hierarchy and developmental rules. …The biological reality not only illustrates some central concepts in P systems but also could give some suggestions for the theoretical development of P systems and their possible implementation. Show more

Keywords:

Citation: Fundamenta Informaticae, vol. 49, no. 1-3, pp. 35-43, 2002

Authors: Atanasiu, Adrian | Martín-Vide, Carlos

Article Type: Research Article

Abstract: 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. Show more

Keywords:

Citation: Fundamenta Informaticae, vol. 49, no. 1-3, pp. 45-59, 2002

Authors: Ciobanu, Gabriel | Paraschiv, Dorin

Article Type: Research Article

Abstract: 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.

Citation: Fundamenta Informaticae, vol. 49, no. 1-3, pp. 61-66, 2002

Authors: Ciobanu, Gabriel | Tanasă, Bogdan

Article Type: Research Article

Abstract: This paper describes the molecular interactions and coordination of cell processes using computer operating system concepts related to synchronization and communication. We argue that in molecular biology, the genes and their chromatin context provide communication and interaction with various cell processes in a similar way to that in which computer processes synchronize and communicate with each other.

Keywords: Cell biology, operating systems, process communication, pipe, signals, modules

Citation: Fundamenta Informaticae, vol. 49, no. 1-3, pp. 67-80, 2002

Authors: Freund, Rudolf | Oswald, Marion

Article Type: Research Article

Abstract: We consider extended variants of GP systems, i.e., membrane systems with sequential applications of evolution rules. The main features we explore are applicability conditions (context conditions) on single objects as well as on the remaining contents of the underlying compartment. For a special very restricted variant only using forbidding context conditions we already obtain universal computational power.

Keywords:

Citation: Fundamenta Informaticae, vol. 49, no. 1-3, pp. 81-102, 2002

Authors: Frisco, Pierluigi | Hoogeboom, Hendrik Jan | Sant, Paul

Article Type: Research Article

Abstract: 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.

Keywords: DNA computing, P systems, Splicing, Direct universal system

Citation: Fundamenta Informaticae, vol. 49, no. 1-3, pp. 103-122, 2002

Authors: Giavitto, Jean-Louis | Michel, Olivier

Article Type: Research Article

Abstract: 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. Show more

Keywords: membrane computing, Gamma, CHAM, P system, L system, cellular automata, group based fields, rewriting, topological collection, declarative programming language

Citation: Fundamenta Informaticae, vol. 49, no. 1-3, pp. 123-145, 2002

Authors: Ji, Sungchul

Article Type: Research Article

Abstract: A molecular model of the living cell known as the Bhopalator is described with the hope of aiding mathematicians and computer scientists to develop comprehensive algebraic models of the cell. The Bhopalator is energy/information dual in the sense that it can be described using two complementary languages – the energy/matter based language of physics and chemistry and the information/sign based language of linguistics and mathematics. The availability of mathematical models of the cell may eventually …lead to developing computer models of the living cell, resulting in important applications not only in biology and medicine but also in computer science and computer industry. To stimulate discussions among mathematicians and computer scientists, the algebraic encoding of the essential characteristics of the Bhopalator may be referred to as the C system (C indicating the cell), in analogy to the well-known H and P systems. Show more

Keywords:

Citation: Fundamenta Informaticae, vol. 49, no. 1-3, pp. 147-165, 2002

Authors: Krishna, S.N. | Lakshmanan, K. | Rama, R.

Article Type: Research Article

Abstract: We consider P Systems with string objects which evolve by means of one-sided contextual rules and erasing contextual rules. The generative power of these systems with three or less than three membranes is investigated. We show that systems with three membranes characterize the family of recursively enumerable languages. When the string replication is used in one-sided contextual rules, these systems are able of solving NP-complete problems in linear time: this is exemplified with SAT and HPP.

Keywords: P Systems, One-sided contextual rules, Erasing contextual rules, Recursively enumerable, NP-completeness

Citation: Fundamenta Informaticae, vol. 49, no. 1-3, pp. 167-178, 2002

Authors: Krithivasan, Kamala | Madhu, Mutyam

Article Type: Research Article

Abstract: Generally, in P systems with string-objects one uses the Chomsky way of rewriting for processing the objects. In this paper we consider the contextual way of handling string-objects in P systems. We introduce some variants of contextual grammars and prove that contextual P systems with rules corresponding to these variants are more powerful than ordinary contextual grammars and their variants. We also show that one-sided contextual P systems with right-sided erased contexts and insertion contextual P …systems with right-sided erased contexts are computationally complete. Show more

Keywords: P systems, contextual grammars, insertion grammars, contextual P systems, recursively enumerable languages, Kuroda normal form, Pentonnen normal form, computational completeness

Citation: Fundamenta Informaticae, vol. 49, no. 1-3, pp. 179-189, 2002

Authors: Kudlek, Manfred | Mitrana, Victor

Article Type: Research Article

Abstract: Multiset languages are languages defined by multiset grammars in the sense of [4]. We extend to multiset languages the usual operations defined for string languages and define new operations specific for multiset languages. The closure properties of the main classes of multiset languages are investigated. Along these lines we introduce two notions of abstract family of multiset languages.

Keywords: Multisets, Closure Properties

Citation: Fundamenta Informaticae, vol. 49, no. 1-3, pp. 191-203, 2002

Authors: Manca, Vincenzo

Article Type: Research Article

Abstract: Some DNA algorithms proposed in the literature for propositional satisfiability (SAT) are analyzed. In the class of 'extract model' the two sub-classes of 'literal string' and 'clause string' algorithms are compared and a new formulation of these algorithms is given in terms of membrane systems. Then, the duality between literal string and clause string formulation of SAT is expressed by means of 'singleton matrices' that introduce another membrane algorithm for SAT. The analysis developed suggests …the perspective of membrane systems as problem-solving agents based on molecule localization, transformation, and propagation. Show more

Keywords: Satisfiability, DNA Computing, Membrane Systems, Molecular Computing, Unconventional Computing Models

Citation: Fundamenta Informaticae, vol. 49, no. 1-3, pp. 205-221, 2002

Authors: Marcus, Salomon

Article Type: Research Article

Abstract: Based on some recent arguments brought into attention by some important authors, we point out the insufficiency of DNA in explaining life and the importance of membranes in bridging this gap. We also discuss the delicate, still open problem concerning the mathematical status of membrane.

Keywords:

Citation: Fundamenta Informaticae, vol. 49, no. 1-3, pp. 223-227, 2002

Authors: Maté, José L. | Rodríguez-Patón, A. | Silva, Andrés

Article Type: Research Article

Abstract: 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. Show more

Keywords: Membrane computing, P systems, Recursively enumerable languages

Citation: Fundamenta Informaticae, vol. 49, no. 1-3, pp. 229-239, 2002

Authors: Nicolau Jr, Dan V | Solana, Gerardin | Fulga, Florin | Nicolau, Dan V

Article Type: Research Article

Abstract: 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.

Keywords: P systems, Software, Membranes, Simulation

Citation: Fundamenta Informaticae, vol. 49, no. 1-3, pp. 241-248, 2002

Authors: Nishida, Taishin Yasunobu

Article Type: Research Article

Abstract: 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.

Keywords: P system, nonintegral multiplicity, K-subset, photosynthesis

Citation: Fundamenta Informaticae, vol. 49, no. 1-3, pp. 249-259, 2002

Authors: Pérez-Jiménez, Mario J. | Sancho-Caparrini, Fernando

Article Type: Research Article

Abstract: 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. Show more

Keywords: Natural computing, P system, Formal verification

Citation: Fundamenta Informaticae, vol. 49, no. 1-3, pp. 261-271, 2002

Authors: Romero-Jiménez, Álvaro | Pérez-Jiménez, Mario J.

Article Type: Research Article

Abstract: In [3] a variant of the computation model introduced by Gh. Păun in [1] is considered: membrane systems with external output, which were proven to be universal, in the sense that they are able to generate all Parikh images of recursively enumerable languages. Here we give another proof of the universality of this model. The proof is carried out associating to each deterministic Turing machine a P system with external output that simulates its running. Thus, …although we work with symbol-objects, we get strings as a result of computations, and in this way we generate directly all recursively enumerable languages, instead of their images through Parikh mapping, as it is done in [3]. Show more

Keywords: Natural computing, Membrane computing, Turing machines

Citation: Fundamenta Informaticae, vol. 49, no. 1-3, pp. 273-287, 2002