Tag: Natural Computing

The effect of malformed tiles on tile assemblies within the kinetic tile assembly model

Abstract  Many different constructions of proofreading tile sets have been proposed in the literature to reduce the effect of deviations
from ideal behaviour of the dynamics of the molecular tile self-assembly process. In this paper, we cons…

Abstract  

Many different constructions of proofreading tile sets have been proposed in the literature to reduce the effect of deviations
from ideal behaviour of the dynamics of the molecular tile self-assembly process. In this paper, we consider the effect on
the tile assembly process of a different kind of non-ideality, namely, imperfections in the tiles themselves. We assume a
scenario in which some small proportion of the tiles in a tile set are “malformed”. We study, through simulations, the effect
of such malformed tiles on the self-assembly process within the kinetic Tile Assembly Model (kTAM). Our simulation results
show that some tile set constructions show greater error-resilience in the presence of malformed tiles than others. For example,
the 2- and 3-way overlay compact proofreading tile sets of Reif et al. (DNA Computing 10, Lecture Notes in Computer Science,
vol 3384. Springer, 2005) are able to handle malformed tiles quite well. On the other hand, the snaked proofreading tile set of Chen and Goel (DNA
Computing 10, Lecture Notes in Computer Science, vol 3384. Springer, 2005) fails to form even moderately sized tile assemblies when malformed tiles are present. We show how the Chen–Goel construction
may be modified to yield new snaked proofreading tile sets that are resilient not only to errors intrinsic to the assembly
process, but also to errors caused by malformed tiles.

  • Content Type Journal Article
  • Pages 357-373
  • DOI 10.1007/s11047-010-9234-9
  • Authors
    • Ya Meng, Department of Mathematics and Statistics, Queen’s University, Kingston, ON K7L 3N6, Canada
    • Navin Kashyap, Department of Mathematics and Statistics, Queen’s University, Kingston, ON K7L 3N6, Canada

Unwinding performance and power on Colossus, an unconventional computer

Abstract  In 1944 the computing machine known as Colossus became operational in support of British cryptanalysis and decryption of German
High Command wireless traffic. This first electronic digital and very unconventional computer was not a…

Abstract  

In 1944 the computing machine known as Colossus became operational in support of British cryptanalysis and decryption of German
High Command wireless traffic. This first electronic digital and very unconventional computer was not a stored-program general
purpose computer in today’s terms, despite printed claims to the contrary. At least one of these asserts Colossus was a Turing
machine. While an appropriate Turing machine can simulate the operation of Colossus, that is not an argument for generality
of computation. Nor does the behavior of Colossus resemble that of a Turing machine, much less a universal Turing machine
(UTM). Nonetheless, we shall see that a UTM could have been implemented on a clustering of the ten Colossus machines installed
at Bletchley Park, England, by the end of WWII in 1945. Improvements require even fewer machines. Several advances in input,
output, speed, processing, and applications—within the hardware capability of the time and respectful of the specification
of Colossus—are also offered.

  • Content Type Journal Article
  • Pages 1-23
  • DOI 10.1007/s11047-010-9225-x
  • Authors
    • Benjamin Wells, Departments of Computer Science and Mathematics, University of San Francisco, 2130 Fulton Street, San Francisco, CA 94117, USA

Computability in planar dynamical systems

Abstract  In this paper we explore the problem of computing attractors and their respective basins of attraction for continuous-time
planar dynamical systems. We consider C
1 systems and show that stability is in general necessary (but may …

Abstract  

In this paper we explore the problem of computing attractors and their respective basins of attraction for continuous-time
planar dynamical systems. We consider C
1 systems and show that stability is in general necessary (but may not be sufficient) to attain computability. In particular,
we show that (a) the problem of determining the number of attractors in a given compact set is in general undecidable, even
for analytic systems and (b) the attractors are semi-computable for stable systems. We also show that the basins of attraction
are semi-computable if and only if the system is stable.

  • Content Type Journal Article
  • Pages 1-18
  • DOI 10.1007/s11047-010-9230-0
  • Authors
    • Daniel Graça, DM/FCT, Universidade do Algarve, C. Gambelas, 8005-139 Faro, Portugal
    • Ning Zhong, DMS, University of Cincinnati, Cincinnati, OH 45221-0025, USA

Padlock probe-mediated qRT-PCR for DNA computing answer determination

Abstract  Padlock probe-mediated quantitative real time PCR (PLP-qRT-PCR) was adapted to quantify the abundance of sequential 10mer
DNA sequences for use in DNA computing to identify optimal answers of traveling salesman problems. The protoc…

Abstract  

Padlock probe-mediated quantitative real time PCR (PLP-qRT-PCR) was adapted to quantify the abundance of sequential 10mer
DNA sequences for use in DNA computing to identify optimal answers of traveling salesman problems. The protocol involves:
(i) hybridization of a linear PLP with a target DNA sequence; (ii) PLP circularization through enzymatic ligation; and (iii)
qRT-PCR amplification of the circularized PLP after removal of non-circularized templates. The linear PLP was designed to
consist of two 10-mer sequence-detection arms at the 5′ and 3′ ends separated by a core sequence composed of universal PCR
primers, and a qRT-PCR reporter binding site. Circularization of each PLP molecule is dependent upon hybridization with target
sequence and high-fidelity ligation. Thus, the number of PLP circularized is determined by the abundance of target in solution.
The amplification efficiency of the PLP was 98.7% within a 0.2 pg–20 ng linear detection range between thermal cycle threshold
(Ct value) and target content. The Ct values derived from multiplex qRT-PCR upon three targets did not differ significantly from those obtained with singleplex
assays. The protocol provides a highly sensitive and efficient means for the simultaneous quantification of multiple short
nucleic acid sequences that has a wide range of applications in biotechnology.

  • Content Type Journal Article
  • Pages 947-959
  • DOI 10.1007/s11047-010-9227-8
  • Authors
    • Fusheng Xiong, Faculty of Biomedicine and Biotechnology, School of Life Sciences, Arizona State University, P.O. Box 874501, Tempe, AZ 85287-4501, USA
    • Wayne D. Frasch, Faculty of Biomedicine and Biotechnology, School of Life Sciences, Arizona State University, P.O. Box 874501, Tempe, AZ 85287-4501, USA

Forward

Forward
Content Type Journal ArticlePages 335-336DOI 10.1007/s11047-010-9231-zAuthors
Russell Deaton, Computer Science and Computer Engineering, University of Arkansas, Fayetteville, AR 72701, USA

Journal Natural ComputingOnline ISSN 1572-979…

Forward

  • Content Type Journal Article
  • Pages 335-336
  • DOI 10.1007/s11047-010-9231-z
  • Authors
    • Russell Deaton, Computer Science and Computer Engineering, University of Arkansas, Fayetteville, AR 72701, USA

A hybrid approach for learning concept hierarchy from Malay text using artificial immune network

Abstract  A concept hierarchy is an integral part of an ontology but it is expensive and time consuming to build. Motivated by this,
many unsupervised learning methods have been proposed to (semi-) automatically develop a concept hierarchy. …

Abstract  

A concept hierarchy is an integral part of an ontology but it is expensive and time consuming to build. Motivated by this,
many unsupervised learning methods have been proposed to (semi-) automatically develop a concept hierarchy. A significant
work is the Guided Agglomerative Hierarchical Clustering (GAHC) which relies on linguistic patterns (i.e., hypernyms) to guide
the clustering process. However, GAHC still relies on contextual features to build the concept hierarchy, thus data sparsity
still remains an issue in GAHC. Artificial Immune Systems are known for robustness, noise tolerance and adaptability. Thus,
an extension to the GAHC is proposed by hybridizing it with Artificial Immune Network (aiNet) which we call Guided Clustering
and aiNet for Learning Concept Hierarchy (GCAINY). In this paper, we have tested GCAINY using two parameter settings. The
first parameter setting is obtained from the literature as a baseline parameter setting and second is by automatic parameter
tuning using Particle Swarm Optimization (PSO). The effectiveness of the GCAINY is evaluated on three data sets. For further
validations, a comparison between GCAINY and GAHC has been conducted and with statistical tests showing that GCAINY increases
the quality of the induced concept hierarchy. The results reveal that the parameters value found by using PSO significantly
produce better concept hierarchy than the vanilla parameter. Thus it can be concluded that the proposed approach has greater
ability to be used in the field of ontology learning.

  • Content Type Journal Article
  • Pages 275-304
  • DOI 10.1007/s11047-010-9228-7
  • Authors
    • Mohd Zakree Ahmad Nazri, Data Mining and Optimization Research Group, Centre for Artificial Information Technology, Faculty of Information Science and Technology, Universiti Kebangsaan Malaysia, 43650 Bangi, Selangor Malaysia
    • Siti Mariyam Shamsuddin, Soft Computing Research Group, Faculty of Computer Science and Information System, Universiti Teknologi Malaysia, 81100 Skudai, Johor Malaysia
    • Azuraliza Abu Bakar, Data Mining and Optimization Research Group, Centre for Artificial Information Technology, Faculty of Information Science and Technology, Universiti Kebangsaan Malaysia, 43650 Bangi, Selangor Malaysia
    • Salwani Abdullah, Data Mining and Optimization Research Group, Centre for Artificial Information Technology, Faculty of Information Science and Technology, Universiti Kebangsaan Malaysia, 43650 Bangi, Selangor Malaysia

Influences on the formation and evolution of Physarum polycephalum inspired emergent transport networks

Abstract  The single-celled organism Physarum polycephalum efficiently constructs and minimises dynamical nutrient transport networks resembling proximity graphs in the Toussaint hierarchy.
We present a particle model which collectively appr…

Abstract  

The single-celled organism Physarum polycephalum efficiently constructs and minimises dynamical nutrient transport networks resembling proximity graphs in the Toussaint hierarchy.
We present a particle model which collectively approximates the behaviour of Physarum. We demonstrate spontaneous transport network formation and complex network evolution using the model and show that the model
collectively exhibits quasi-physical emergent properties, allowing it to be considered as a virtual computing material. This
material is used as an unconventional method to approximate spatially represented geometry problems by representing network
nodes as nutrient sources. We demonstrate three different methods for the construction, evolution and minimisation of Physarum-like transport networks which approximate Steiner trees, relative neighbourhood graphs, convex hulls and concave hulls. We
extend the model to adapt population size in response to nutrient availability and show how network evolution is dependent
on relative node position (specifically inter-node angle), sensor scaling and nutrient concentration. We track network evolution
using a real-time method to record transport network topology in response to global differences in nutrient concentration.
We show how Steiner nodes are utilised at low nutrient concentrations whereas direct connections to nutrients are favoured
when nutrient concentration is high. The results suggest that the foraging and minimising behaviour of Physarum-like transport networks reflect complex interplay between nutrient concentration, nutrient location, maximising foraging
area coverage and minimising transport distance. The properties and behaviour of the synthetic virtual plasmodium may be useful
in future physical instances of distributed unconventional computing devices, and may also provide clues to the generation
of emergent computation behaviour by Physarum.

  • Content Type Journal Article
  • Pages 1-25
  • DOI 10.1007/s11047-010-9223-z
  • Authors
    • Jeff Jones, Centre for Unconventional Computing, University of the West of England, Bristol, BS16 1QY UK

On the hierarchy of conservation laws in a cellular automaton

Abstract  Conservation laws in cellular automata (CA) are studied as an abstraction of the conservation laws observed in nature. In
addition to the usual real-valued conservation laws we also consider more general group-valued and semigroup-…

Abstract  

Conservation laws in cellular automata (CA) are studied as an abstraction of the conservation laws observed in nature. In
addition to the usual real-valued conservation laws we also consider more general group-valued and semigroup-valued conservation
laws. The (algebraic) conservation laws in a CA form a hierarchy, based on the range of the interactions they take into account.
The conservation laws with smaller interaction ranges are the homomorphic images of those with larger interaction ranges,
and for each specific range there is a most general law that incorporates all those with that range. For one-dimensional CA,
such a most general conservation law has—even in the semigroup-valued case—an effectively constructible finite presentation,
while for higher-dimensional CA such effective construction exists only in the group-valued case. It is even undecidable whether
a given two-dimensional CA conserves a given semigroup-valued energy assignment. Although the local properties of this hierarchy
are tractable in the one-dimensional case, its global properties turn out to be undecidable. In particular, we prove that
it is undecidable whether this hierarchy is trivial or unbounded. We point out some interconnections between the structure
of this hierarchy and the dynamical properties of the CA. In particular, we show that positively expansive CA do not have
non-trivial real-valued conservation laws.

  • Content Type Journal Article
  • Pages 1-20
  • DOI 10.1007/s11047-010-9222-0
  • Authors
    • Enrico Formenti, Laboratoire I3S, Université de Nice Sophia Antipolis, 2000 route des Lucioles, Les Algorithmes – Bât. Euclide B, BP 121, 06903 Sophia Antipolis Cedex, France
    • Jarkko Kari, Department of Mathematics, University of Turku, 20014 Turku, Finland
    • Siamak Taati, Laboratoire I3S, Université de Nice Sophia Antipolis, 2000 route des Lucioles, Les Algorithmes – Bât. Euclide B, BP 121, 06903 Sophia Antipolis Cedex, France

Unconventional complexity measures for unconventional computers

Abstract  Unconventional computers—which may, for example, exploit chemical/analogue/quantum phenomena in order to compute, rather than
electronically implementing discrete logic gates—are widely studied in both theoretical and practical…

Abstract  

Unconventional computers—which may, for example, exploit chemical/analogue/quantum phenomena in order to compute, rather than
electronically implementing discrete logic gates—are widely studied in both theoretical and practical contexts. One particular
motivation behind unconventional computation is the desire efficiently to solve classically difficult problems—we recall chemical-computer
attempts at solving
NP
-complete problems such as the Travelling Salesperson Problem—, with computational complexity theory offering the criteria
for judging this efficiency. However, care must be taken here; conventional (Turing-machine-style) complexity analysis is
not always appropriate for unconventional computers: new, non-standard computational resources, with correspondingly new complexity
measures, are often required. Accordingly, we discuss in the present paper various resources beyond merely time and space
(and, indeed, discuss various interpretations of the term ‘resource’ itself), advocating such resources’ consideration when
analysing the complexity of unconventional computers. We hope that this acts as a useful starting point for practitioners
of unconventional computing and computational complexity.

  • Content Type Journal Article
  • Pages 1-15
  • DOI 10.1007/s11047-010-9226-9
  • Authors
    • Ed Blakey, Oxford University Computing Laboratory, Wolfson Building, Parks Road, Oxford, OX1 3QD UK

Greedy versus social: resource-competing oscillator network as a model of amoeba-based neurocomputer

Abstract  A single-celled amoeboid organism, the true slime mold Physarum polycephalum, exhibits rich spatiotemporal oscillatory behavior and sophisticated computational capabilities. The authors previously created
a biocomputer that incorpo…

Abstract  

A single-celled amoeboid organism, the true slime mold Physarum polycephalum, exhibits rich spatiotemporal oscillatory behavior and sophisticated computational capabilities. The authors previously created
a biocomputer that incorporates the organism as a computing substrate to search for solutions to combinatorial optimization
problems. With the assistance of optical feedback to implement a recurrent neural network model, the organism changes its
shape by alternately growing and withdrawing its photosensitive branches so that its body area can be maximized and the risk
of being illuminated can be minimized. In this way, the organism succeeded in finding the optimal solution to the four-city
traveling salesman problem with a high probability. However, it remains unclear how the organism collects, stores, and compares
information on light stimuli using the oscillatory dynamics. To study these points, we formulate an ordinary differential
equation model of the amoeba-based neurocomputer, considering the organism as a network of oscillators that compete for a
fixed amount of intracellular resource. The model, called the “Resource-Competing Oscillator Network (RCON) model,” reproduces
well the organism’s experimentally observed behavior, as it generates a number of spatiotemporal oscillation modes by keeping
the total sum of the resource constant. Designing the feedback rule properly, the RCON model comes to face a problem of optimizing
the allocation of the resource to its nodes. In the problem-solving process, “greedy” nodes having the highest competitiveness
are supposed to take more resource out of other nodes. However, the resource allocation pattern attained by the greedy nodes
cannot always achieve a “socially optimal” state in terms of the public cost. We prepare four test problems including a tricky
one in which the greedy pattern becomes “socially unfavorable” and investigate how the RCON model copes with these problems.
Comparing problem-solving performances of the oscillation modes, we show that there exist some modes often attain socially
favorable patterns without being trapped in the greedy one.

  • Content Type Journal Article
  • Pages 1-26
  • DOI 10.1007/s11047-010-9224-y
  • Authors
    • Masashi Aono, Flucto-Order Functions Research Team, RIKEN-HYU Collaboration Research Center, RIKEN Advanced Science Institute, 2-1 Hirosawa, Wako, Saitama 351-0198, Japan
    • Yoshito Hirata, Institute of Industrial Science, The University of Tokyo, 4-6-1 Komaba, Meguro-ku, Tokyo 153-8505, Japan
    • Masahiko Hara, Flucto-Order Functions Research Team, RIKEN-HYU Collaboration Research Center, RIKEN Advanced Science Institute, 2-1 Hirosawa, Wako, Saitama 351-0198, Japan
    • Kazuyuki Aihara, Institute of Industrial Science, The University of Tokyo, 4-6-1 Komaba, Meguro-ku, Tokyo 153-8505, Japan