588 results on '"P systems"'
Search Results
552. Further results on contextual and rewriting P systems
- Author
-
Krishna, S.N., Rama, R., Ramesh, H.
- Subjects
Systems analysis ,Contextual grammars ,Leftmost rewriting ,P systems ,Recursively enumerable languages ,Replicated rewriting ,Rewriting P systems ,Text processing - Abstract
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.
- Published
- 2005
553. Tissue P systems with channel states
- Author
-
Mario J. Pérez-Jiménez, Gheorghe Paun, Rudolf Freund, Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial, and Universidad de Sevilla. TIC193: Computación Natural
- Subjects
Discrete mathematics ,Matrix grammar ,States ,General Computer Science ,P systems ,Turing computability ,State (functional analysis) ,Membrane Computing ,Theoretical Computer Science ,Matrix (mathematics) ,Matrix grammars ,Rule-based machine translation ,Channel (programming) ,Membrane computing ,P system ,Mathematics ,Computer Science(all) - Abstract
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 arbitrarilymanystates 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 anyweight onlycompute Parikh sets of matrix languages (generated bymatrix 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.
- Published
- 2005
554. On P Systems with Promoters/Inhibitors
- Author
-
Ionescu, Mihai and Sburlan, Dragos
- Subjects
inhibitors ,promoters ,universality ,P Systems - Abstract
This article shows how the computational universality can be reached using P systems with object rewriting non-cooperative rules, promoters/inhibitors at the level of rules, and only one catalyst. Both generative and accepting cases are studied. The theoretical issues presented are illustrated by several examples.
- Published
- 2004
555. Finding the Maximum Element Using P Systems
- Author
-
Fontana, F. and Giuditta FRANCO
- Subjects
maximum value ,P systems ,natural computing ,DNA computing ,formal rewriting systems ,maximum-length sequence ,Natural computing ,Membrane computing ,Maximum value - Abstract
A nondeterministic, maximally parallel methodology for finding the maximum element in a set of numerical values is presented, suitable for being implemented on P systems. Several algorithms of maximum search are then developed for different types of such systems, namely using priorities, nested membranes and linked transport, and their performances are evaluated accordingly. The proposed solutions are expected to find application inside membrane models devoted to compute algorithmic procedures in which the greatest element in a data set must be found. Dynamic algorithms for DNA sequence alignment are an example of such procedures.
- Published
- 2004
556. Parallel Rewriting P systems without Target Conflicts
- Author
-
Daniela Besozzi, Claudio Zandron, Giancarlo Mauri, Paun, G, Rozenberg, G, Salomaa, A, Zandron, C, Besozzi, D, and Mauri, G
- Subjects
Theoretical computer science ,Computer science ,String (computer science) ,P systems ,Parallelism (grammar) ,INF/01 - INFORMATICA ,Rewriting ,Membrane computing ,P system ,Register machine - Abstract
We consider rewriting P systems with parallel application of evolution rules, where no conflicts on the communication of objects can arise. Different parallelism methods are used and only rules which have the same target indication can be simultaneously applied to a common string. The computational power is analyzed, with respect to Lindenmayer systems, and some relations among different parallel rewriting P systems are studied. Some open problems are also formulated.
- Published
- 2003
557. Membrane division, restricted membrane creation and object complexity in P systems
- Abstract
We improve, by using register machines, some existing universality results for specific models of P systems. P systems with membrane creation are known to generate all recursively enumerable sets of vectors of non-negative integers, even when no region (except the environment) contains more than one object of the same kind.We showhere that they generate all recursively enumerable languages, and that two membrane labels are sufficient (the same result holds for accepting all recursively enumerable vectors of non-negative integers). Moreover, at most two objects are present inside the system at any time in the generative case.We then prove that 10 + msymbols are sufficient to generate any recursively enumerable language over m symbols. P systems with active membranes without polarizations are known to generate all recursively enumerable sets of vectors of non-negative integers. We show that they generate all recursively enumerable languages; four starting membranes with three labels or seven starting membranes with two labels are sufficient. P systems with active membranes and two polarizations are known to generate/accept all recursively enumerable sets of vectors of non-negative integers, using only rules of rewriting and sending objects out.We show that accepting can be done by deterministic systems. Finally, we show that P systems with restricted membrane creation (the newly created membrane can only be of the same kind as the parent one) generate at least matrix languages, even when having at most one object in the configuration (except the environment). We conclude by presenting a summary of the main results obtained in this paper and a list of open questions.
- Published
- 2006
558. Membrane division, restricted membrane creation and object complexity in P systems
- Abstract
We improve, by using register machines, some existing universality results for specific models of P systems. P systems with membrane creation are known to generate all recursively enumerable sets of vectors of non-negative integers, even when no region (except the environment) contains more than one object of the same kind.We showhere that they generate all recursively enumerable languages, and that two membrane labels are sufficient (the same result holds for accepting all recursively enumerable vectors of non-negative integers). Moreover, at most two objects are present inside the system at any time in the generative case.We then prove that 10 + msymbols are sufficient to generate any recursively enumerable language over m symbols. P systems with active membranes without polarizations are known to generate all recursively enumerable sets of vectors of non-negative integers. We show that they generate all recursively enumerable languages; four starting membranes with three labels or seven starting membranes with two labels are sufficient. P systems with active membranes and two polarizations are known to generate/accept all recursively enumerable sets of vectors of non-negative integers, using only rules of rewriting and sending objects out.We show that accepting can be done by deterministic systems. Finally, we show that P systems with restricted membrane creation (the newly created membrane can only be of the same kind as the parent one) generate at least matrix languages, even when having at most one object in the configuration (except the environment). We conclude by presenting a summary of the main results obtained in this paper and a list of open questions.
- Published
- 2006
559. Membrane division, restricted membrane creation and object complexity in P systems
- Abstract
We improve, by using register machines, some existing universality results for specific models of P systems. P systems with membrane creation are known to generate all recursively enumerable sets of vectors of non-negative integers, even when no region (except the environment) contains more than one object of the same kind.We showhere that they generate all recursively enumerable languages, and that two membrane labels are sufficient (the same result holds for accepting all recursively enumerable vectors of non-negative integers). Moreover, at most two objects are present inside the system at any time in the generative case.We then prove that 10 + msymbols are sufficient to generate any recursively enumerable language over m symbols. P systems with active membranes without polarizations are known to generate all recursively enumerable sets of vectors of non-negative integers. We show that they generate all recursively enumerable languages; four starting membranes with three labels or seven starting membranes with two labels are sufficient. P systems with active membranes and two polarizations are known to generate/accept all recursively enumerable sets of vectors of non-negative integers, using only rules of rewriting and sending objects out.We show that accepting can be done by deterministic systems. Finally, we show that P systems with restricted membrane creation (the newly created membrane can only be of the same kind as the parent one) generate at least matrix languages, even when having at most one object in the configuration (except the environment). We conclude by presenting a summary of the main results obtained in this paper and a list of open questions.
- Published
- 2006
560. Membrane division, restricted membrane creation and object complexity in P systems
- Abstract
We improve, by using register machines, some existing universality results for specific models of P systems. P systems with membrane creation are known to generate all recursively enumerable sets of vectors of non-negative integers, even when no region (except the environment) contains more than one object of the same kind.We showhere that they generate all recursively enumerable languages, and that two membrane labels are sufficient (the same result holds for accepting all recursively enumerable vectors of non-negative integers). Moreover, at most two objects are present inside the system at any time in the generative case.We then prove that 10 + msymbols are sufficient to generate any recursively enumerable language over m symbols. P systems with active membranes without polarizations are known to generate all recursively enumerable sets of vectors of non-negative integers. We show that they generate all recursively enumerable languages; four starting membranes with three labels or seven starting membranes with two labels are sufficient. P systems with active membranes and two polarizations are known to generate/accept all recursively enumerable sets of vectors of non-negative integers, using only rules of rewriting and sending objects out.We show that accepting can be done by deterministic systems. Finally, we show that P systems with restricted membrane creation (the newly created membrane can only be of the same kind as the parent one) generate at least matrix languages, even when having at most one object in the configuration (except the environment). We conclude by presenting a summary of the main results obtained in this paper and a list of open questions.
- Published
- 2006
561. Tau leaping stochastic simulation method in P Systems
- Abstract
Stochastic simulations based on the tau leaping method are applicable to well stirred chemical systems reacting within a single fixed volume. In this paper we propose a novel method, based on the tau leaping procedure, for the simulation of complex systems composed by several communicating regions. The new method is here applied to dynamical probabilistic P systems, which are characterized by several features suitable to the purpose of performing stochastic simulations distributed in many regions. Conclusive remarks and ideas for future research are finally presented
- Published
- 2006
562. Quantum Sequential P Systems with Unit Rules and Energy Assigned to Membranes
- Abstract
We propose a quantum version of P systems with unit rules and energy assigned to membranes. Differently from the classical version, the new quantum P systems do not need to use priorities over rules to be computationally complete. We also propose a quantum version of register machines as a tool to study the computational power of quantum models of computation
- Published
- 2006
563. Stochastic Approaches in P systems for Simulating Biological Systems
- Abstract
Different stochastic strategies for modelling biological systems with P systems are reviewed in this paper, such as the multi-compartmental approach and dynamical probabilistic P systems. The respective results obtained from the simulations of a test case study (the quorum sensing phenomena in Vibrio Fischeri colonies) are shown, compared and discussed.
- Published
- 2006
564. (Tissue) P systems with unit rules and energy assigned to membranes
- Abstract
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.
- Published
- 2006
565. Membrane division, restricted membrane creation and object complexity in P systems
- Abstract
We improve, by using register machines, some existing universality results for specific models of P systems. P systems with membrane creation are known to generate all recursively enumerable sets of vectors of non-negative integers, even when no region (except the environment) contains more than one object of the same kind.We showhere that they generate all recursively enumerable languages, and that two membrane labels are sufficient (the same result holds for accepting all recursively enumerable vectors of non-negative integers). Moreover, at most two objects are present inside the system at any time in the generative case.We then prove that 10 + msymbols are sufficient to generate any recursively enumerable language over m symbols. P systems with active membranes without polarizations are known to generate all recursively enumerable sets of vectors of non-negative integers. We show that they generate all recursively enumerable languages; four starting membranes with three labels or seven starting membranes with two labels are sufficient. P systems with active membranes and two polarizations are known to generate/accept all recursively enumerable sets of vectors of non-negative integers, using only rules of rewriting and sending objects out.We show that accepting can be done by deterministic systems. Finally, we show that P systems with restricted membrane creation (the newly created membrane can only be of the same kind as the parent one) generate at least matrix languages, even when having at most one object in the configuration (except the environment). We conclude by presenting a summary of the main results obtained in this paper and a list of open questions.
- Published
- 2006
566. Membrane division, restricted membrane creation and object complexity in P systems
- Abstract
We improve, by using register machines, some existing universality results for specific models of P systems. P systems with membrane creation are known to generate all recursively enumerable sets of vectors of non-negative integers, even when no region (except the environment) contains more than one object of the same kind.We showhere that they generate all recursively enumerable languages, and that two membrane labels are sufficient (the same result holds for accepting all recursively enumerable vectors of non-negative integers). Moreover, at most two objects are present inside the system at any time in the generative case.We then prove that 10 + msymbols are sufficient to generate any recursively enumerable language over m symbols. P systems with active membranes without polarizations are known to generate all recursively enumerable sets of vectors of non-negative integers. We show that they generate all recursively enumerable languages; four starting membranes with three labels or seven starting membranes with two labels are sufficient. P systems with active membranes and two polarizations are known to generate/accept all recursively enumerable sets of vectors of non-negative integers, using only rules of rewriting and sending objects out.We show that accepting can be done by deterministic systems. Finally, we show that P systems with restricted membrane creation (the newly created membrane can only be of the same kind as the parent one) generate at least matrix languages, even when having at most one object in the configuration (except the environment). We conclude by presenting a summary of the main results obtained in this paper and a list of open questions.
- Published
- 2006
567. Tissue P systems with channel states
- Abstract
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 arbitrarilymanystates 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 anyweight onlycompute Parikh sets of matrix languages (generated bymatrix 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.
- Published
- 2005
568. Tissue P systems with channel states
- Abstract
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 arbitrarilymanystates 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 anyweight onlycompute Parikh sets of matrix languages (generated bymatrix 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.
- Published
- 2005
569. Tissue P systems with channel states
- Abstract
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 arbitrarilymanystates 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 anyweight onlycompute Parikh sets of matrix languages (generated bymatrix 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.
- Published
- 2005
570. Tissue P systems with channel states
- Abstract
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 arbitrarilymanystates 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 anyweight onlycompute Parikh sets of matrix languages (generated bymatrix 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.
- Published
- 2005
571. Tissue P systems with channel states
- Abstract
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 arbitrarilymanystates 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 anyweight onlycompute Parikh sets of matrix languages (generated bymatrix 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.
- Published
- 2005
572. A Note on Complexity Measures for Probabilistic P Systems
- Abstract
In this paper we present a first approach to the definition of different entropy measures for probabilistic P systems in order to obtain some quantitative parameters showing how complex the evolution of a P system is. To this end, we define two possible measures, the first one to reflect the entropy of the P system considered as the state space of possible computations, and the second one to reflect the change of the P system as it evolves.
- Published
- 2004
573. A Note on Complexity Measures for Probabilistic P Systems
- Abstract
In this paper we present a first approach to the definition of different entropy measures for probabilistic P systems in order to obtain some quantitative parameters showing how complex the evolution of a P system is. To this end, we define two possible measures, the first one to reflect the entropy of the P system considered as the state space of possible computations, and the second one to reflect the change of the P system as it evolves.
- Published
- 2004
574. A Note on Complexity Measures for Probabilistic P Systems
- Abstract
In this paper we present a first approach to the definition of different entropy measures for probabilistic P systems in order to obtain some quantitative parameters showing how complex the evolution of a P system is. To this end, we define two possible measures, the first one to reflect the entropy of the P system considered as the state space of possible computations, and the second one to reflect the change of the P system as it evolves.
- Published
- 2004
575. A Note on Complexity Measures for Probabilistic P Systems
- Abstract
In this paper we present a first approach to the definition of different entropy measures for probabilistic P systems in order to obtain some quantitative parameters showing how complex the evolution of a P system is. To this end, we define two possible measures, the first one to reflect the entropy of the P system considered as the state space of possible computations, and the second one to reflect the change of the P system as it evolves.
- Published
- 2004
576. A Note on Complexity Measures for Probabilistic P Systems
- Abstract
In this paper we present a first approach to the definition of different entropy measures for probabilistic P systems in order to obtain some quantitative parameters showing how complex the evolution of a P system is. To this end, we define two possible measures, the first one to reflect the entropy of the P system considered as the state space of possible computations, and the second one to reflect the change of the P system as it evolves.
- Published
- 2004
577. A Note on Complexity Measures for Probabilistic P Systems
- Abstract
In this paper we present a first approach to the definition of different entropy measures for probabilistic P systems in order to obtain some quantitative parameters showing how complex the evolution of a P system is. To this end, we define two possible measures, the first one to reflect the entropy of the P system considered as the state space of possible computations, and the second one to reflect the change of the P system as it evolves.
- Published
- 2004
578. Universality results for some variants of P systems
- Author
-
Mutyam, M. and Krithivasan, K.
- Subjects
Artificial intelligence ,P systems ,Distributed computing models - Abstract
P systems, introduced by Gh. P�aun, form a new class of distributed computing models. Many variants of P systems were shown to be computationally universal. In this paper, we consider several classes of P systems with symbol-objects where we allow the catalysts to move in and out of a membrane. We prove universality results for these variants of P systems with a very small number of membranes. ? 2001 Springer-Verlag Berlin Heidelberg.
- Published
- 2001
579. Evolving cell models for systems and synthetic biology.
- Author
-
Cao H, Romero-Campero FJ, Heeb S, Cámara M, and Krasnogor N
- Abstract
This paper proposes a new methodology for the automated design of cell models for systems and synthetic biology. Our modelling framework is based on P systems, a discrete, stochastic and modular formal modelling language. The automated design of biological models comprising the optimization of the model structure and its stochastic kinetic constants is performed using an evolutionary algorithm. The evolutionary algorithm evolves model structures by combining different modules taken from a predefined module library and then it fine-tunes the associated stochastic kinetic constants. We investigate four alternative objective functions for the fitness calculation within the evolutionary algorithm: (1) equally weighted sum method, (2) normalization method, (3) randomly weighted sum method, and (4) equally weighted product method. The effectiveness of the methodology is tested on four case studies of increasing complexity including negative and positive autoregulation as well as two gene networks implementing a pulse generator and a bandwidth detector. We provide a systematic analysis of the evolutionary algorithm's results as well as of the resulting evolved cell models.
- Published
- 2010
- Full Text
- View/download PDF
580. On the degree of parallelism in membrane systems
- Author
-
Miguel A. Gutiérrez-Naranjo, Mario J. Pérez-Jiménez, and Agustín Riscos-Núñez
- Subjects
Theoretical computer science ,General Computer Science ,Computation ,P systems ,Degree of parallelism ,Single step ,Membrane Computing ,Dependency graph ,Task (project management) ,Theoretical Computer Science ,Membrane computing ,Algorithm ,P system ,Mathematics ,Computer Science(all) - Abstract
In the literature, several designs of P systems might be found for performing the same task. The use of different techniques or even different P system models makes it very difficult to compare these designs. In this paper, we introduce a new criterion for such a comparison: the degree of parallelism of a P system. With this aim, we define the labelled dependency graph associated with a P system, and we use this new concept for proving some results concerning the maximum number of applications of rules in a single step through the computation of a P system.
- Full Text
- View/download PDF
581. P systems with control nuclei: The concept
- Author
-
Gheorghe Stefanescu, Camelia Chira, and Traian Florin Şerbănuţă
- Subjects
Theoretical computer science ,K rewrite-based framework ,Logic ,Process (engineering) ,P systems ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Theoretical Computer Science ,Set (abstract data type) ,Membrane region ,0202 electrical engineering, electronic engineering, information engineering ,medicine ,Control (linguistics) ,Representation (mathematics) ,Modeling cell growth ,Mathematics ,Extension (predicate logic) ,Division (mathematics) ,medicine.anatomical_structure ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,020201 artificial intelligence & image processing ,Nucleus ,Software ,Control nuclei - Abstract
We describe an extension of P systems where each membrane has an associated control nucleus responsible with the generation of the rules to be applied in that membrane. The nucleus exports a set of rules which are applied in the membrane region (only for one step, but in the usual maximal-parallel way), then the rules are removed and a new iteration of this process takes place. This way, powerful control mechanisms may be included in P systems themselves, as opposed to using the level of “strategies” previously exploited for simulating P systems. The nuclei may contain general programs for generating rules, ranging from those using information on the full system, to more restricted programs where only local information in the nuclei themselves and the associated membranes is used. The latter approach, mixed with a particular mechanism for the representation of the control programs, the rules, and the export procedure is powerful enough for modeling complex biological applications, e.g., to develop a detailed model for cell growth and division in normal and abnormal (tumoral) evolution of biological systems.
- Full Text
- View/download PDF
582. Test generation from P systems using model checking
- Author
-
Raluca Lefticaru, Florentin Ipate, and Marian Gheorghe
- Subjects
Model checking ,Theoretical computer science ,Logic ,Test generation ,Kripke structure ,P systems ,Kripke structures ,Rule-based system ,Theoretical Computer Science ,Set (abstract data type) ,Test case ,TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES ,Linear temporal logic ,Computational Theory and Mathematics ,Simple (abstract algebra) ,TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS ,Algorithm ,Software ,Mathematics ,Counterexample - Abstract
This paper presents some testing approaches based on model checking and using different testing criteria. First, test sets are built from different Kripke structure representations. Second, various rule coverage criteria for transitional, non-deterministic, cell-like P systems, are considered in order to generate adequate test sets. Rule based coverage criteria (simple rule coverage, context-dependent rule coverage and variants) are defined and, for each criterion, a set of LTL (Linear Temporal Logic) formulas is provided. A codification of a P system as a Kripke structure and the sets of LTL properties are used in test generation: for each criterion, test cases are obtained from the counterexamples of the associated LTL formulas, which are automatically generated from the Kripke structure codification of the P system. The method is illustrated with an implementation using a specific model checker, NuSMV. (C) 2010 Elsevier Inc. All rights reserved.
- Full Text
- View/download PDF
583. (Mem)brane automata
- Author
-
Erzsébet Csuhaj-Varjú and György Vaszil
- Subjects
Discrete mathematics ,P automata ,Multiset ,General Computer Science ,Modulo ,Continuous automaton ,P systems ,Computational completeness ,Automaton ,Mobile automaton ,Theoretical Computer Science ,Combinatorics ,Brane calculi ,Recursively enumerable language ,Természettudományok ,Simple (abstract algebra) ,Brane ,Matematika- és számítástudományok ,Mathematics ,Computer Science(all) - Abstract
We introduce the notion of a P automaton with marked membranes, a Ppp automaton for short, which is an accepting variant of P systems. The concept is motivated by the theory of P systems, brane calculi, and the traditional concept of automata. In P systems with marked membranes, bio-molecules (proteins) are allowed to move through the membranes and to attach onto or to de-attach from the membranes. The membrane system evolves according to rules which are defined over multisets of proteins and describe the above actions. In addition to these features, the P automaton with marked membranes is able to consume inputs from its environment, i.e. multisets of proteins, which might influence the behaviour of the system. The result of the computation is the set of multiset sequences consumed by the skin membrane, supposing that the Ppp automaton started functioning in the initial configuration and entered a final configuration at halting. We show that any recursively enumerable language can be obtained as the language accepted by a Ppp automaton modulo a simple computable mapping.
- Full Text
- View/download PDF
584. Discrete solutions to differential equations by metabolic P systems
- Author
-
Federico Fontana and Vincenzo Manca
- Subjects
education.field_of_study ,General Computer Science ,Differential equation ,Population ,Mathematical analysis ,P systems ,Ode ,Metabolic network ,Metabolic networks ,Membrane computing ,Computational biology ,Metabolic algorithm ,Theoretical Computer Science ,Amphibian embryos ,Ordinary differential equation ,Attractor ,Applied mathematics ,education ,MP systems ,MP graphs ,P system ,Ordinary differential equations ,Computer Science(all) ,Mathematics - Abstract
The relationships existing between metabolic P systems and ODE systems are investigated. Formal results show that every MP system determines a structure, called an MP graph, which results in an ODE system whose solution equals, in the limit, the evolution of any non-cooperative MP system that can be derived from the initial one by means of a systematic procedure. Examples based on the model of a mitotic oscillator in early amphibian embryos, the Lotka–Volterra predator–prey population dynamics, and the Lorenz strange attractor are provided, showing the applicability of the proposed computational approach.
- Full Text
- View/download PDF
585. Hierarchical clustering with membrane computing
- Author
-
Cardona, M., Colomer, M. A., Zaragoza, A., and Mario J. Pérez Jiménez
- Subjects
P systems ,hierarchical clustering - Abstract
In this paper we approach the problem of hierarchical clustering through membrane computing. A specific P system with external output is designed for each Boolean matrix associated with a finite set of individuals. The computation of the system allows us to obtain one of the possible classifications in a non-deterministic way. The amount of resources required in the construction is polynomial in the number of individuals and of characteristics analyzed.
586. P Systems Computing the Period of Irreducible Markov Chains
- Author
-
Agustín Riscos Núñez, M. Angeles Colomer Cugat, Mónica Cardona Roca, Miquel Rius Font, Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada IV, Universitat Politècnica de Catalunya. COMBGRAPH - Combinatòria, Teoria de Grafs i Aplicacions, Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial, Universidad de Sevilla. TIC193: Computación Natural, Ministerio de Educación y Ciencia (MEC). España, and Junta de Andalucía
- Subjects
Discrete mathematics ,Markov chain mixing time ,Markov chain ,Parallel processing (Electronic computers) ,Computer Networks and Communications ,Markov processes ,P systems ,Discrete phase-type distribution ,Membrane Computing ,Computer Science Applications ,Molecular computers ,Coupling from the past ,Computational Theory and Mathematics ,Absorbing Markov chain ,Markov, Processos de ,Markov renewal process ,Ordinadors moleculars ,ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION ,Balance equation ,Markov property ,Mathematics - Abstract
It is well known that any irreducible and aperiodic Markov chain has exactly one stationary distribution, and for any arbitrary initial distribution, the se- quence of distributions at time n converges to the stationary distribution, that is, the Markov chain is approaching equilibrium as n→∞. In this paper, a characterization of the aperiodicity in existential terms of some state is given. At the same time, a P system with external output is associated with any irre- ducible Markov chain. The designed system provides the aperiodicity of that Markov chain and spends a polynomial amount of resources with respect to the size of the in- put. A comparative analysis with respect to another known solution is described. Ministerio de Educación y Ciencia TIN2006–13425 Junta de Andalucía P08-TIC-04200
587. A note on complexity measures for probabilistic P systems
- Author
-
Cordon-Franco, A., Fernando Sancho Caparrini, and Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial
- Subjects
Natural computing ,Entropy ,P systems ,Natural Computing - Abstract
In this paper we present a first approach to the definition of different entropy measures for probabilistic P systems in order to obtain some quantitative parameters showing how complex the evolution of a P system is. To this end, we define two possible measures, the first one to reflect the entropy of the P system considered as the state space of possible computations, and the second one to reflect the change of the P system as it evolves. Ministerio de Ciencia y Tecnología TIC2002-04220-C03-01
588. Tau leaping stochastic simulation method in P systems
- Author
-
Daniela Besozzi, Dario Pescini, Giancarlo Mauri, Paolo Cazzaniga, Cazzaniga, P, Pescini, D, Besozzi, D, and Mauri, G
- Subjects
Mathematical optimization ,Settore INF/01 - Informatica ,Computer science ,P systems ,Probabilistic logic ,Complex system ,Volume (computing) ,INF/01 - INFORMATICA ,Stochastic simulation ,Poisson distribution ,symbols.namesake ,symbols ,Applied mathematics ,Tau-leaping - Abstract
Stochastic simulations based on the tau leaping method are applicable to well stirred chemical systems reacting within a single fixed volume. In this paper we propose a novel method, based on the tau leaping procedure, for the simulation of complex systems composed by several communicating regions. The new method is here applied to dynamical probabilistic P systems, which are characterized by several features suitable to the purpose of performing stochastic simulations distributed in many regions. Conclusive remarks and ideas for future research are finally presented
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.