Tag: Natural Computing

A software tool for generating graphics by means of P systems

Abstract  The hand-made graphical representation of the configuration of a P system becomes a hard task when the number of membranes
and objects increases. In this paper we present a new software tool, called JPLANT, for computing and repres…

Abstract  

The hand-made graphical representation of the configuration of a P system becomes a hard task when the number of membranes
and objects increases. In this paper we present a new software tool, called JPLANT, for computing and representing the evolution
of a P system model with membrane creation. We also present some experiments performed with JPLANT and point out new lines
for the research in computer graphics with membrane systems.

  • Content Type Journal Article
  • Pages 879-890
  • DOI 10.1007/s11047-010-9198-9
  • Authors
    • Elena Rivero-Gil, Departamento de Ciencias de la Computación e Inteligencia Artificial, Escuela Técnica Superior de Ingeniería Informática, Universidad de Sevilla, Avda. Reina Mercedes, s/n., 41012 Sevilla, Spain
    • Miguel Á. Gutiérrez-Naranjo, Departamento de Ciencias de la Computación e Inteligencia Artificial, Escuela Técnica Superior de Ingeniería Informática, Universidad de Sevilla, Avda. Reina Mercedes, s/n., 41012 Sevilla, Spain
    • Álvaro Romero-Jiménez, Departamento de Ciencias de la Computación e Inteligencia Artificial, Escuela Técnica Superior de Ingeniería Informática, Universidad de Sevilla, Avda. Reina Mercedes, s/n., 41012 Sevilla, Spain
    • Agustín Riscos-Núñez, Departamento de Ciencias de la Computación e Inteligencia Artificial, Escuela Técnica Superior de Ingeniería Informática, Universidad de Sevilla, Avda. Reina Mercedes, s/n., 41012 Sevilla, Spain

A review of the nondeterministic waiting time algorithm

Abstract  We provide the description for the nondeterministic waiting time (NWT) algorithm, a biochemical modeling approach based on
the membrane systems paradigm of computation. The technique provides a unique (different to Gillespie’s al…

Abstract  

We provide the description for the nondeterministic waiting time (NWT) algorithm, a biochemical modeling approach based on
the membrane systems paradigm of computation. The technique provides a unique (different to Gillespie’s algorithm or ODE modeling)
perspective on the biochemical evolution of the cell. That is, depending on the reactions and molecular multiplicities of
a given model, our simulator is capable of producing results comparable to the alternative techniques—continuous and deterministic
or discrete and stochastic. Some results for sample models are given, illustrating the differences between the NWT algorithm,
the Gillespie algorithm, and the solutions to systems of ordinary differential equations. We have previously used this simulation
technique to address issues surrounding Fas-induced apoptosis in cancerous cells and so-called latent HIV-infected cells.

  • Content Type Journal Article
  • Pages 1-11
  • DOI 10.1007/s11047-010-9195-z
  • Authors
    • John Jack, IfM Louisiana Tech University Department of Computer Science P.O. Box 10348 Ruston LA 71272 USA
    • Andrei Păun, IfM Louisiana Tech University Department of Computer Science P.O. Box 10348 Ruston LA 71272 USA
    • Alfonso Rodríguez-Patón, Universidad Politécnica de Madrid Facultad de Informática, Departamento de Inteligencia Artificial Campus de Montegancedo S/N 28660 Boadilla del Monte, Madrid Spain

Computing transparently: the independent sets in a graph

Abstract  A procedure is given for finding the independent sets in an undirected graph by xeroxing onto transparent plastic sheets.
Let an undirected graph having n vertices and m edges be given. A list of all the independent subsets of the …

Abstract  

A procedure is given for finding the independent sets in an undirected graph by xeroxing onto transparent plastic sheets.
Let an undirected graph having n vertices and m edges be given. A list of all the independent subsets of the set of vertices of the graph is constructed by using a xerox machine in a manner that requires
the formation of only n + m + 1 successive transparencies. An accompanying list of the counts of the elements in each independent set is then constructed
using only O(n
2) additional transparencies. The list with counts provides a list of all maximum independent sets. This gives an O(n
2) step solution for the classical problem of finding the cardinality of a maximal independent set in a graph. The applicability
of these procedures is limited, of course, by the increase in the information density on the transparencies when n is large. Our ultimate purpose here is to give hand tested ‘ultra parallel’ algorithmic procedures that may prove suitable for realization
using future optical technologies.

  • Content Type Journal Article
  • Pages 1-10
  • DOI 10.1007/s11047-010-9186-0
  • Authors
    • Tom Head, Binghamton University Mathematical Sciences Binghamton NY 13902-6000 USA

A relation by palindromic subwords

Abstract  We define a new relation on words by a finite series of insertions and/or deletions of palindromic subwords. In particular
we concentrate on insertion or deletion of Watson–Crick palindromes. We show that the new relation ∼θ i…

Abstract  

We define a new relation on words by a finite series of insertions and/or deletions of palindromic subwords. In particular
we concentrate on insertion or deletion of Watson–Crick palindromes. We show that the new relation ∼θ is, in fact, an equivalence relation where θ is any arbitrary antimorphic involution that is not the identity on the letters
of the alphabet. We also show that the set of all θ-palindromic free words defined in (Daley et al. in preparation) is ∼θ-independent. Using the relation we define a new subclass of primitive words which we call as ∼θ-primitive words and show that the class of all ∼θ-primitive words is closed under circular permutations. We also define ∼θ-conjugates and ∼θ-commutativity and study the properties of such words and show that they are similar to that of conjugate words and words
that commute.

  • Content Type Journal Article
  • DOI 10.1007/s11047-010-9179-z
  • Authors
    • Mark Daley, Department of Computer Science and Department of Biology, University of Western Ontario, London, ON N6A 5B7, Canada
    • Kalpana Mahalingam, Department of Mathematics, Indian Institute of Technology, Chennai, TN 600 042, India

An empirical evaluation of P system testing techniques

Abstract  This paper presents the existing techniques for P system testing and performs an empirical evaluation of their fault-detection
efficiency. The comparison is performed using mutation testing and, based on the results obtained, some …

Abstract  

This paper presents the existing techniques for P system testing and performs an empirical evaluation of their fault-detection
efficiency. The comparison is performed using mutation testing and, based on the results obtained, some improved testing methodologies
are proposed.

  • Content Type Journal Article
  • Pages 1-15
  • DOI 10.1007/s11047-010-9188-y
  • Authors
    • Raluca Lefticaru, University of Pitesti Department of Computer Science Str Targu din Vale 1 110040 Pitesti Romania
    • Marian Gheorghe, University of Pitesti Department of Computer Science Str Targu din Vale 1 110040 Pitesti Romania
    • Florentin Ipate, University of Pitesti Department of Computer Science Str Targu din Vale 1 110040 Pitesti Romania

A computational modeling for real ecosystems based on P systems

Abstract  In this paper, a P systems based general framework for modeling ecosystems dynamics is presented. Particularly, ecosystems
are specified by means of multienvironment P systems composed of a finite number of environments, each of th…

Abstract  

In this paper, a P systems based general framework for modeling ecosystems dynamics is presented. Particularly, ecosystems
are specified by means of multienvironment P systems composed of a finite number of environments, each of them having an extended
P system with active membranes. The semantics is of a probabilistic type and it is implemented by assigning each rule of the
system a probabilistic constant which depends on the environment and the run time. As a case study, two real ecosystems are
described: scavenger birds in the Catalan Pyrenees and the zebra mussel (Dreissena Polymorpha) in Ribarroja reservoir (Spain).

  • Content Type Journal Article
  • Pages 1-15
  • DOI 10.1007/s11047-010-9191-3
  • Authors
    • Mónica Cardona, University of Lleida Department of Mathematics Av. Alcalde Rovira Roure, 191 25198 Lleida Spain
    • M. Angels Colomer, University of Lleida Department of Mathematics Av. Alcalde Rovira Roure, 191 25198 Lleida Spain
    • Antoni Margalida, Bearded Vulture Study & Protection Group Adpo. 43 25520 El Pont de Suert (Lleida) Spain
    • Antoni Palau, Dirección de Medio Ambiente y Desarrollo Sostenible Endesa Spain
    • Ignacio Pérez-Hurtado, University of Sevilla Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence Avda. Reina Mercedes s/n 41012 Sevilla Spain
    • Mario J. Pérez-Jiménez, University of Sevilla Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence Avda. Reina Mercedes s/n 41012 Sevilla Spain
    • Delfí Sanuy, University of Lleida Department of Animal Production Av. Alcalde Rovira Roure, 191 25198 Lleida Spain

P systems with active membranes: trading time for space

Abstract  We consider recognizer P systems having three polarizations associated to the membranes, and we show that they are able to
solve the PSPACE-complete problem Quantified 3SAT when working in polynomial space and exponential time. The…

Abstract  

We consider recognizer P systems having three polarizations associated to the membranes, and we show that they are able to
solve the PSPACE-complete problem Quantified 3SAT when working in polynomial space and exponential time. The solution is uniform (all the instances of a fixed size are solved
by the same P system) and uses only communication rules: evolution rules, as well as membrane division and dissolution rules,
are not used. Our result shows that, as it happens with Turing machines, this model of P systems can solve in exponential
time and polynomial space problems that cannot be solved in polynomial time, unless P = SPACE.

  • Content Type Journal Article
  • Pages 1-16
  • DOI 10.1007/s11047-010-9189-x
  • Authors
    • Antonio E. Porreca, Università degli Studi di Milano-Bicocca Dipartimento di Informatica, Sistemistica e Comunicazione Viale Sarca 336/14 20126 Milan Italy
    • Alberto Leporati, Università degli Studi di Milano-Bicocca Dipartimento di Informatica, Sistemistica e Comunicazione Viale Sarca 336/14 20126 Milan Italy
    • Giancarlo Mauri, Università degli Studi di Milano-Bicocca Dipartimento di Informatica, Sistemistica e Comunicazione Viale Sarca 336/14 20126 Milan Italy
    • Claudio Zandron, Università degli Studi di Milano-Bicocca Dipartimento di Informatica, Sistemistica e Comunicazione Viale Sarca 336/14 20126 Milan Italy

Spatial P systems

Abstract  We present Spatial P systems, a variant of P systems which embodies the concept of space and position inside a membrane. Objects
in membranes are associated with positions. Rules specify, in the usual way, the objects which are con…

Abstract  

We present Spatial P systems, a variant of P systems which embodies the concept of space and position inside a membrane. Objects
in membranes are associated with positions. Rules specify, in the usual way, the objects which are consumed and the ones which
are produced; in addition, they can specify the positions of the produced objects. Objects belong to two different sets: the
set of ordinary objects and the set of mutually exclusive objects. Every position inside a membrane can accommodate an arbitrary number of ordinary objects, but at most one mutually
exclusive object. We prove that Spatial P systems are universal even if only non-cooperating rules are allowed. We also show
how Spatial P systems can be used to model the evolution of populations in presence of geographical separations.

  • Content Type Journal Article
  • Pages 1-14
  • DOI 10.1007/s11047-010-9187-z
  • Authors
    • Roberto Barbuti, Università di Pisa Dipartimento di Informatica Largo Pontecorvo 3 56127 Pisa Italy
    • Andrea Maggiolo-Schettini, Università di Pisa Dipartimento di Informatica Largo Pontecorvo 3 56127 Pisa Italy
    • Paolo Milazzo, Università di Pisa Dipartimento di Informatica Largo Pontecorvo 3 56127 Pisa Italy
    • Giovanni Pardini, Università di Pisa Dipartimento di Informatica Largo Pontecorvo 3 56127 Pisa Italy
    • Luca Tesei, Università di Camerino School of Science and Technology Via Madonna delle Carceri 9 62032 Camerino MC Italy

An improved multi-agent genetic algorithm for numerical optimization

Abstract  Multi-agent genetic algorithm (MAGA) is a good algorithm for global numerical optimization. It exploited the known characteristics
of some benchmark functions to achieve outstanding results. But for some novel composition functions…

Abstract  

Multi-agent genetic algorithm (MAGA) is a good algorithm for global numerical optimization. It exploited the known characteristics
of some benchmark functions to achieve outstanding results. But for some novel composition functions, the performance of the
MAGA significantly deteriorates when the relative positions of the variables at the global optimal point are shifted with
respect to the search ranges. To this question, an improved multi-agent genetic algorithm for numerical optimization (IMAGA)
is proposed. IMAGA make use of the agent evolutionary framework, and constructs heuristic search and a hybrid crossover strategy
to complete the competition and cooperation of agents, a convex mutation operator and some local search to achieve the self-learning
characteristic. Using the theorem of Markov chain, the improved multi-agent genetic algorithm is proved to be convergent.
Experiments are conducted on some benchmark functions and composition functions. The results demonstrate good performance
of the IMAGA in solving complicated composition functions compared with some existing algorithms.

  • Content Type Journal Article
  • Pages 1-20
  • DOI 10.1007/s11047-010-9192-2
  • Authors
    • Xiaoying Pan, Xi’an University of Posts and Telecommunications School of Computer Science and Technology Xi’an 710121 China
    • Licheng Jiao, Institute of Intelligent Information Processing, Xidian University Key Laboratory of Intelligent Perception and Image Understanding of Ministry of Education of China Xi’an 710071 China
    • Fang Liu, Xidian University School of Computer Science and Engineering Xi’an 710071 China

The quantification of pollutants in drinking water by use of artificial neural networks

Abstract  Drinking water attained from aquifers (ground water) is susceptible to contamination from a wide variety of sources. The importance
of ensuring that the water is of high quality is paramount. Multivariate calibration in conjunction…

Abstract  

Drinking water attained from aquifers (ground water) is susceptible to contamination from a wide variety of sources. The importance
of ensuring that the water is of high quality is paramount. Multivariate calibration in conjunction with analytical techniques
can assist in qualifying and quantifying a wide range of pollutants. These can be divided into two types: inorganic and organic.
The former typically includes heavy metals such as cadmium and lead; the latter includes a range of compounds such as pesticides
and by-products of industrial processes such as oil refining. This article presents the application of the well known nature-inspired
paradigm of artificial neural networks (ANNs) for the quantitative determination of inorganic pollutants (namely cadmium,
lead and copper) and organic pollutants (namely anthracene, phenanthrene and naphthalene) from multivariate analytical data
acquired from the samples. The success of the determination of the pollutants via ANNs is reported in terms of the overall
root mean square error of prediction (RMSEP) which is an accepted measure of the difference between the predicted concentrations
and the actual concentrations. The work represents a good example of nature-inspired methods being used to solve a genuine
environmental problem.

  • Content Type Journal Article
  • Pages 1-14
  • DOI 10.1007/s11047-010-9185-1
  • Authors
    • Michael Cauchi, Cranfield University Cranfield Health Bedfordshire MK43 0AL UK
    • Luca Bianco, Cranfield University Cranfield Health Bedfordshire MK43 0AL UK
    • Conrad Bessant, Cranfield University Cranfield Health Bedfordshire MK43 0AL UK