Tag: Natural Computing

Solving the generalized Subset Sum problem with a light based device

Abstract  Recently, a number of researchers have suggested light-based devices to solve combinatorially interesting problems. In this
paper, we design a light based device to solve a generalized version of the Subset Sum problem which was pr…

Abstract  

Recently, a number of researchers have suggested light-based devices to solve combinatorially interesting problems. In this
paper, we design a light based device to solve a generalized version of the Subset Sum problem which was previously handled
by Oltean and Muntean. We further design a system which is capable of providing us with the solution subset of the problem
in addition to the YES/NO answer to the question of whether there exists a solution or not.

  • Content Type Journal Article
  • Pages 541-550
  • DOI 10.1007/s11047-010-9205-1
  • Authors
    • Masud Hasan, Department of CSE, BUET, Dhaka, 1000 Bangladesh
    • Shabab Hossain, Department of CSE, BUET, Dhaka, 1000 Bangladesh
    • Md. Mahmudur Rahman, Department of CSE, BUET, Dhaka, 1000 Bangladesh
    • M. Sohel Rahman, Department of CSE, BUET, Dhaka, 1000 Bangladesh

Foreword

Foreword
Content Type Journal ArticlePages 1-2DOI 10.1007/s11047-010-9203-3Authors
Roberto Barbuti, University of Pisa, Pisa, ItalyGiuditta Franco, University of Verona, Verona, ItalyGheorghe Păun, Institute of Mathematics of the Romanian Academy, …

Foreword

  • Content Type Journal Article
  • Pages 1-2
  • DOI 10.1007/s11047-010-9203-3
  • Authors
    • Roberto Barbuti, University of Pisa, Pisa, Italy
    • Giuditta Franco, University of Verona, Verona, Italy
    • Gheorghe Păun, Institute of Mathematics of the Romanian Academy, Bucharest, Romania

Friction-based sorting

Abstract  Since computer processing mainly depends on sorting and searching methods, a key problem is how to design efficient algorithms
in order to solve such problems. This paper describes a new nature-inspired mechanism (called Friction-b…

Abstract  

Since computer processing mainly depends on sorting and searching methods, a key problem is how to design efficient algorithms
in order to solve such problems. This paper describes a new nature-inspired mechanism (called Friction-based Sorting) capable
of sorting a given set of numbers. The main idea behind this mechanism is to associate a ball (whose weight is proportional
to the considered number) to each number. All the balls being allowed to fall in the presence of friction, the heaviest ball
(which corresponds to the greatest input number) will reach the ground first and the lightest ball (associated with the smallest
number) will reach the ground last. The proposed mechanism is analyzed, together with its strengths and weaknesses.

  • Content Type Journal Article
  • Pages 527-539
  • DOI 10.1007/s11047-010-9201-5
  • Authors
    • Laura Dioşan, Department of Computer Science Faculty of Mathematics and Computer Science, Babeş-Bolyai University, Cluj-Napoca, Romania
    • Mihai Oltean, Department of Computer Science Faculty of Mathematics and Computer Science, Babeş-Bolyai University, Cluj-Napoca, Romania

Data analysis pipeline from laboratory to MP models

Abstract  A workflow for data analysis is introduced to synthesize flux regulation maps of a Metabolic P system from time series of
data observed in laboratory. The procedure is successfully tested on a significant case study, the photosynth…

Abstract  

A workflow for data analysis is introduced to synthesize flux regulation maps of a Metabolic P system from time series of
data observed in laboratory. The procedure is successfully tested on a significant case study, the photosynthetic phenomenon
called NPQ, which determines plant accommodation to environmental light. A previously introduced MP model of such a photosynthetic
process has been improved, by providing an MP system with a simpler regulative network that reproduces the observed behaviors
of the natural system. Two regression techniques were employed to find out the regulation maps, and interesting experimental
results came out in the context of their residual analysis for model validation.

  • Content Type Journal Article
  • Pages 55-76
  • DOI 10.1007/s11047-010-9200-6
  • Authors
    • Alberto Castellini, Computer Science Department, Verona University, Strada Le Grazie 15, 37134 Verona, Italy
    • Giuditta Franco, Computer Science Department, Verona University, Strada Le Grazie 15, 37134 Verona, Italy
    • Roberto Pagliarini, Computer Science Department, Verona University, Strada Le Grazie 15, 37134 Verona, Italy

Algorithmic applications of XPCR

Abstract  An emerging trend in DNA computing consists of the algorithmic analysis of new molecular biology technologies, and in general
of more effective tools to tackle computational biology problems. An algorithmic understanding of the int…

Abstract  

An emerging trend in DNA computing consists of the algorithmic analysis of new molecular biology technologies, and in general
of more effective tools to tackle computational biology problems. An algorithmic understanding of the interaction between
DNA molecules becomes the focus of some research which was initially addressed to solve mathematical problems by processing
data within biomolecules. In this paper a novel mechanism of DNA recombination is discussed, that turned out to be a good
implementation key to develop new procedures for DNA manipulation (Franco et al., DNA extraction by cross pairing PCR, 2005; Franco et al., DNA recombination by XPCR, 2006; Manca and Franco, Math Biosci 211:282–298, 2008). It is called XPCR as it is a variant of the polymerase chain reaction (PCR), which was a revolution in molecular biology
as a technique for cyclic amplification of DNA segments. A few DNA algorithms are proposed, that were experimentally proven
in different contexts, such as, mutagenesis (Franco, Biomolecular computing—combinatorial algorithms and laboratory experiments,
2006), multiple concatenation, gene driven DNA extraction (Franco et al., DNA extraction by cross pairing PCR, 2005), and generation of DNA libraries (Franco et al., DNA recombination by XPCR, 2006), and some related ongoing work is outlined.

  • Content Type Journal Article
  • Pages 805-819
  • DOI 10.1007/s11047-010-9199-8
  • Authors
    • Giuditta Franco, Department of Computer Science, University of Verona, Strada Le Grazie 15, 37134 Verona, Italy
    • Vincenzo Manca, Department of Computer Science, University of Verona, Strada Le Grazie 15, 37134 Verona, Italy

Towards a neighborhood simplification of tile systems: From Moore to quasi-linear dependencies

Abstract  Self-assembly is the process by which objects aggregate independently and form complex structures. One of the theoretical
frameworks in which the process of self-assembly can be embedded and formally studied is that of tile systems…

Abstract  

Self-assembly is the process by which objects aggregate independently and form complex structures. One of the theoretical
frameworks in which the process of self-assembly can be embedded and formally studied is that of tile systems. A Wang tile
is a square unit, with glues on its edges, attaching to other tiles which have matching glues, and forming larger and larger
structures. In this paper we concentrate over two basic, but essential, self-assembling structures done by Wang tiles. The
first one, called ribbon, is a non-self-crossing wire-like structure, in which successive tiles are adjacent along an edge,
and where tiles are glued to their predecessor and successor by use of matching glues. The second one, called zipper, is a
similar contiguous structure, only that here, all touching tiles must have matching glues on their abutting edges, independently
of their position in the structure. In case of Wang tiles, it has been shown that these two structures are equivalent. Here
we generalize this result for the case when the tiles have eight glues, four on their edges and four on their corners. Thus
we show that an eight neighborhood dependency, namely the Moore neighborhood, can be simulated by a quasi-linear dependency.

  • Content Type Journal Article
  • Pages 103-117
  • DOI 10.1007/s11047-010-9193-1
  • Authors
    • Eugen Czeizler, Department of Information Technologies, Åbo Akademi University, Turku, 20520 Finland
    • Lila Kari, Department of Computer Science, University of Western Ontario, London, ON N6A 5B7, Canada

Evolutionary and population dynamics of 3 parents differential evolution (3PDE) using self-adaptive tuning methodologies

Abstract  Differential Evolution is known for its simplicity and effectiveness as an evolutionary optimizer. In recent years, many researchers
have focused on the exploration of Differential Evolution (DE). The objective of this paper is to …

Abstract  

Differential Evolution is known for its simplicity and effectiveness as an evolutionary optimizer. In recent years, many researchers
have focused on the exploration of Differential Evolution (DE). The objective of this paper is to show the evolutionary and
population dynamics for the empirical testing on 3-Parents Differential Evolution (3PDE) for unconstrained function optimization
(Teng et al. 2007). In this paper, 50 repeated evolutionary runs for each of 20 well-known benchmarks were carried out to test the proposed
algorithms against the original 4-parents DE algorithm. As a result of the observed evolutionary dynamics, 3PDE-SAF performed
the best among the preliminary proposed algorithms that included 3PDE-SACr and 3PDE-SACrF. Subsequently, 3PDE-SAF is chosen
for the self-adaptive population size for testing dynamic population sizing methods using the absolute (3PDE-SAF-Abs) and
relative (3PDE-SAF-Rel) population size encodings. The final result shows that 3PDE-SAF-Rel produced a better performance
and convergence overall compared to all the other proposed algorithms, including the original DE. In terms of population dynamics,
the population size in 3PDE-SAF-Abs exhibited disadvantageously high dynamics that caused less efficient results. On the other
hand, the population size in 3PDE-SAF-Rel was observed to be approximately constant at ten times the number of variables being
optimized, hence giving a better and more stable performance.

  • Content Type Journal Article
  • Pages 507-526
  • DOI 10.1007/s11047-010-9194-0
  • Authors
    • Teng Nga Sing, Evolutionary Computing Laboratory, School of Engineering and IT, Unversiti Malaysia Sabah, Kota Kinabalu, Sabah Malaysia
    • Jason Teo, Evolutionary Computing Laboratory, School of Engineering and IT, Unversiti Malaysia Sabah, Kota Kinabalu, Sabah Malaysia

Quantum security in wireless sensor networks

Abstract  Security in sensor networks, though an important issue for widely available wireless networks, has been studied less extensively
than other properties of these networks, such as, for example, their reliability. The few security sch…

Abstract  

Security in sensor networks, though an important issue for widely available wireless networks, has been studied less extensively
than other properties of these networks, such as, for example, their reliability. The few security schemes proposed so far
are based on classical cryptography. In contrast, the present paper develops a new security solution, based on quantum cryptography.
The scheme developed here comes with the advantages quantum cryptography has over classical cryptography, namely, effectively
unbreakable keys and therefore effectively unconditionally secure messages. Our security system ensures privacy of the measured
data field in the presence of an intruder who listens to messages broadcast in the field.

  • Content Type Journal Article
  • DOI 10.1007/s11047-010-9190-4
  • Authors
    • Naya Nagy, School of Computing, Queen’s University, Kingston, ON K7L 3N6, Canada
    • Marius Nagy, School of Computing, Queen’s University, Kingston, ON K7L 3N6, Canada
    • Selim G. Akl, School of Computing, Queen’s University, Kingston, ON K7L 3N6, Canada

On discrete models and immunological algorithms for protein structure prediction

Abstract  Discrete models for protein structure prediction embed the protein amino acid sequence into a discrete spatial structure,
usually a lattice, where an optimal tertiary structure is predicted on the basis of simple assumptions relati…

Abstract  

Discrete models for protein structure prediction embed the protein amino acid sequence into a discrete spatial structure,
usually a lattice, where an optimal tertiary structure is predicted on the basis of simple assumptions relating to the hydrophobic–hydrophilic
character of amino acids in the sequence and to relevant interactions for free energy minimization. While the prediction problem
is known to be NP complete even in the simple setting of Dill’s model with a 2D-lattice, a variety of bio-inspired algorithms
for this problem have been proposed in the literature. Immunological algorithms are inspired by the kind of optimization that
immune systems perform when identifying and promoting the replication of the most effective antibodies against given antigens.
A quick, state-of-the-art survey of discrete models and immunological algorithms for protein structure prediction is presented
in this paper, and the main design and performance features of an immunological algorithm for this problem are illustrated
in a tutorial fashion.

  • Content Type Journal Article
  • Pages 91-102
  • DOI 10.1007/s11047-010-9196-y
  • Authors
    • Vincenzo Cutello, Department of Mathematics and Computer Science, University of Catania, Catania, Italy
    • Giuseppe Morelli, Department of Mathematics and Computer Science, University of Catania, Catania, Italy
    • Giuseppe Nicosia, Department of Mathematics and Computer Science, University of Catania, Catania, Italy
    • Mario Pavone, Department of Mathematics and Computer Science, University of Catania, Catania, Italy
    • Giuseppe Scollo, Department of Mathematics and Computer Science, University of Catania, Catania, Italy

Output concepts for accelerated Turing machines

Abstract  The accelerated Turing machine (ATM) is the work-horse of hypercomputation. In certain cases, a machine having run through
a countably infinite number of steps is supposed to have decided some interesting question such as the Twin …

Abstract  

The accelerated Turing machine (ATM) is the work-horse of hypercomputation. In certain cases, a machine having run through
a countably infinite number of steps is supposed to have decided some interesting question such as the Twin Prime conjecture.
One is, however, careful to avoid unnecessary discussion of either the possible actual use by such a machine of an infinite
amount of space, or the difficulty (even if only a finite amount of space is used) of defining an outcome for machines acting
like Thomson’s lamp. It is the authors’ impression that insufficient attention has been paid to introducing a clearly defined
counterpart for ATMs of the halting/non-halting dichotomy for classical Turing computation. This paper tackles the problem
of defining the output, or final message, of a machine which has run for a countably infinite number of steps. Non-standard
integers appear quite useful in this regard and we describe several models of computation using filters.

  • Content Type Journal Article
  • DOI 10.1007/s11047-010-9197-x
  • Authors
    • Petrus H. Potgieter, Department of Decision Sciences, University of South Africa (Unisa), P.O. Box 392, Pretoria, 0003 South Africa
    • Elemér E. Rosinger, Department of Mathematics and Applied Mathematics, University of Pretoria, Pretoria, 0002 South Africa