Fundamenta Informaticae - Volume 49, issue 1-3

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