Tag: Natural Computing

Spatial search using the discrete time quantum walk

Abstract  We study the quantum walk search algorithm of Shenvi et al. (Phys Rev A 67:052307, 2003) on data structures of one to two spatial dimensions, on which the algorithm is thought to be less efficient than in three
or more spatial dime…

Abstract  

We study the quantum walk search algorithm of Shenvi et al. (Phys Rev A 67:052307, 2003) on data structures of one to two spatial dimensions, on which the algorithm is thought to be less efficient than in three
or more spatial dimensions. Our aim is to understand why the quantum algorithm is dimension dependent whereas the best classical
algorithm is not, and to show in more detail how the efficiency of the quantum algorithm varies with spatial dimension or
accessibility of the data. Our numerical results agree with the expected scaling in 2D of

O( Ö

 
N logN
 
 )

, and show how the prefactors display significant dependence on both the degree and symmetry of the graph. Specifically, we
see, as expected, the prefactor of the time complexity dropping as the degree (connectivity) of the structure is increased.

  • Content Type Journal Article
  • Pages 1-13
  • DOI 10.1007/s11047-011-9279-4
  • Authors
    • Neil B. Lovett, School of Physics and Astronomy, University of Leeds, Leeds, LS2 9JT UK
    • Matthew Everitt, School of Physics and Astronomy, University of Leeds, Leeds, LS2 9JT UK
    • Matthew Trevers, School of Physics and Astronomy, University of Leeds, Leeds, LS2 9JT UK
    • Daniel Mosby, School of Physics and Astronomy, University of Leeds, Leeds, LS2 9JT UK
    • Dan Stockton, School of Physics and Astronomy, University of Leeds, Leeds, LS2 9JT UK
    • Viv Kendon, School of Physics and Astronomy, University of Leeds, Leeds, LS2 9JT UK

Sequential and maximally parallel multiset rewriting: reversibility and determinism

Abstract  We study reversibility and determinism aspects and the strong versions of these properties of sequential multiset processing
systems and of maximally parallel systems, from the computability point of view. In the sequential case, s…

Abstract  

We study reversibility and determinism aspects and the strong versions of these properties of sequential multiset processing
systems and of maximally parallel systems, from the computability point of view. In the sequential case, syntactic criteria
are established for both strong determinism and strong reversibility. In the parallel case, a criterion is established for
strong determinism, whereas strong reversibility is shown to be decidable. In the sequential case, without control all four
classes—deterministic, strongly deterministic, reversible, strongly reversible—are not universal, whereas in the parallel
case deterministic systems are universal. When allowing inhibitors, the first and the third class become universal in both
models, whereas with priorities all of them are universal. In the maximally parallel case, strongly deterministic systems
with both promoters and inhibitors are universal. We also present a few more specific results and conjectures.

  • Content Type Journal Article
  • Pages 1-12
  • DOI 10.1007/s11047-011-9267-8
  • Authors
    • Artiom Alhazov, FCS, Department of Information Engineering, Graduate School of Engineering, Hiroshima University, Higashi-Hiroshima, 739-8527 Japan
    • Rudolf Freund, Faculty of Informatics, Vienna University of Technology, Favoritenstr. 9, 1040 Vienna, Austria
    • Kenichi Morita, FCS, Department of Information Engineering, Graduate School of Engineering, Hiroshima University, Higashi-Hiroshima, 739-8527 Japan

Designing a new software tool for Digital Imagery based on P systems

Abstract  In this paper we present a new software tool for dealing with the problem of segmentation in Digital Imagery. The implementation
is inspired in the design of a tissue-like P system which solves the problem in constant time due the …

Abstract  

In this paper we present a new software tool for dealing with the problem of segmentation in Digital Imagery. The implementation
is inspired in the design of a tissue-like P system which solves the problem in constant time due the intrinsic parallelism
of Membrane Computing devices.

  • Content Type Journal Article
  • Pages 1-6
  • DOI 10.1007/s11047-011-9287-4
  • Authors
    • Daniel Díaz-Pernil, Research Group on Computational Topology and Applied Mathematics, University of Seville, Seville, Spain
    • Miguel A. Gutiérrez-Naranjo, Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, University of Seville, Seville, Spain
    • Helena Molina-Abril, Research Group on Computational Topology and Applied Mathematics, University of Seville, Seville, Spain
    • Pedro Real, Research Group on Computational Topology and Applied Mathematics, University of Seville, Seville, Spain

A survey of recursive analysis and Moore’s notion of real computation

Abstract  The theory of analog computation aims at modeling computational systems that evolve in a continuous space. Unlike the situation
with the discrete setting there is no unified theory of analog computation. There are several proposed …

Abstract  

The theory of analog computation aims at modeling computational systems that evolve in a continuous space. Unlike the situation
with the discrete setting there is no unified theory of analog computation. There are several proposed theories, some of them
seem quite orthogonal. Some theories can be considered as generalizations of the Turing machine theory and classical recursion
theory. Among such are recursive analysis and Moore’s class of recursive real functions. Recursive analysis was introduced
by Turing (Proc Lond Math Soc 2(42):230–265, 1936), Grzegorczyk (Fundam Math 42:168–202, 1955), and Lacombe (Compt Rend l’Acad Sci Paris 241:151–153, 1955). Real computation in this context is viewed as effective (in the sense of Turing machine theory) convergence of sequences
of rational numbers. In 1996 Moore introduced a function algebra that captures his notion of real computation; it consists
of some basic functions and their closure under composition, integration and zero-finding. Though this class is inherently
unphysical, much work have been directed at stratifying, restricting, and comparing it with other theories of real computation
such as recursive analysis and the GPAC. In this article we give a detailed exposition of recursive analysis and Moore’s class and the relationships between them.

  • Content Type Journal Article
  • Pages 1-13
  • DOI 10.1007/s11047-011-9278-5
  • Authors
    • Walid Gomaa, Department of Computer Science and Engineering, Egypt-Japan University of Science and Technology, Alexandria, Egypt

Preface

Preface
Content Type Journal ArticlePages 1-1DOI 10.1007/s11047-011-9283-8Authors
Olivier Bournez, École polytechnique, Paris, FranceGilles Dowek, INRIA, Paris, France

Journal Natural ComputingOnline ISSN 1572-9796Print ISSN 1567-7818

Preface

  • Content Type Journal Article
  • Pages 1-1
  • DOI 10.1007/s11047-011-9283-8
  • Authors
    • Olivier Bournez, École polytechnique, Paris, France
    • Gilles Dowek, INRIA, Paris, France

Editorial for special issue on unconventional computation

Editorial for special issue on unconventional computation
Content Type Journal ArticlePages 1-2DOI 10.1007/s11047-011-9273-xAuthors
Jon Timmis, Department of Computer Science, University of York, York, UKKenichi Morita, Department of Information Eng…

Editorial for special issue on unconventional computation

  • Content Type Journal Article
  • Pages 1-2
  • DOI 10.1007/s11047-011-9273-x
  • Authors
    • Jon Timmis, Department of Computer Science, University of York, York, UK
    • Kenichi Morita, Department of Information Engineering, Graduate School of Engineering, Hiroshima University, Higashi-Hiroshima, Japan

Partitioned quantum cellular automata are intrinsically universal

Abstract  There have been several non-axiomatic approaches taken to define quantum cellular automata (QCA). Partitioned QCA (PQCA) are
the most canonical of these non-axiomatic definitions. In this work we show that any QCA can be put into t…

Abstract  

There have been several non-axiomatic approaches taken to define quantum cellular automata (QCA). Partitioned QCA (PQCA) are
the most canonical of these non-axiomatic definitions. In this work we show that any QCA can be put into the form of a PQCA.
Our construction reconciles all the non-axiomatic definitions of QCA, showing that they can all simulate one another, and
hence that they are all equivalent to the axiomatic definition. This is achieved by defining generalised n-dimensional intrinsic simulation, which brings the computer science based concepts of simulation and universality closer
to theoretical physics. The result is not only an important simplification of the QCA model, it also plays a key role in the
identification of a minimal n-dimensional intrinsically universal QCA.

  • Content Type Journal Article
  • Pages 1-10
  • DOI 10.1007/s11047-011-9277-6
  • Authors
    • Pablo Arrighi, Laboratoire LIG, Bâtiment IMAG C, University of Grenoble, 220 Rue de la Chimie, 38400 Saint-Martin-d’Hères, France
    • Jonathan Grattage, Laboratoire LIG, Bâtiment IMAG C, University of Grenoble, 220 Rue de la Chimie, 38400 Saint-Martin-d’Hères, France

Comparing simulation algorithms for multienvironment probabilistic P systems over a standard virtual ecosystem

Abstract  Membrane Computing has recently proved to be a suitable framework for addressing the modelling of dynamical biological systems
in general, and ecosystems in particular. Due to the inherent randomness and uncertainty in biological s…

Abstract  

Membrane Computing has recently proved to be a suitable framework for addressing the modelling of dynamical biological systems
in general, and ecosystems in particular. Due to the inherent randomness and uncertainty in biological systems, when designing
a model the relevant tasks to be addressed are the validation and virtual experimentation processes, rather than the formal
verification. It is therefore crucial to rely on software implementations of efficient simulation algorithms. This paper presents
a simple (but realistic enough) ecosystem where a carnivore and several herbivorous species interact. The model of this ecosystem
has been used to compare experimentally the performance of two different simulation algorithms.

  • Content Type Journal Article
  • Pages 1-11
  • DOI 10.1007/s11047-011-9289-2
  • Authors
    • M. Angels Colomer, Department of Mathematics, University of Lleida, Av. Alcalde Rovira Roure, 191, 25198 Lleida, Spain
    • Ignacio Pérez-Hurtado, Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, University of Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain
    • Mario J. Pérez-Jiménez, Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, University of Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain
    • Agustín Riscos-Núñez, Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, University of Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain

Membrane system models for super-Turing paradigms

Abstract  We extend Calude and Păun’s accelerating P system model of computation, and investigate the computational power of the resulting
systems. We show that the resulting systems can solve problems at all levels of the arithmetical hi…

Abstract  

We extend Calude and Păun’s accelerating P system model of computation, and investigate the computational power of the resulting
systems. We show that the resulting systems can solve problems at all levels of the arithmetical hierarchy, and that the higher
systems have hyperarithmetical computational power.

  • Content Type Journal Article
  • Pages 1-7
  • DOI 10.1007/s11047-011-9291-8
  • Authors
    • Marian Gheorghe, Department of Computer Science, University of Sheffield Regent Court, 211 Portobello, Sheffield, S1 4DP UK
    • Mike Stannett, Department of Computer Science, University of Sheffield Regent Court, 211 Portobello, Sheffield, S1 4DP UK

Emergence of synchronicity in a self-organizing spiking neuron network: an approach via genetic algorithms

Abstract  Based on the Theory of Neuronal Group Selection (TNGS), we have investigated the emergence of synchronicity in a network composed
of spiking neurons via genetic algorithm. The TNGS establishes that a neuronal group is the most basi…

Abstract  

Based on the Theory of Neuronal Group Selection (TNGS), we have investigated the emergence of synchronicity in a network composed
of spiking neurons via genetic algorithm. The TNGS establishes that a neuronal group is the most basic unit in the cortical
area of the brain and, as a rule, it is not formed by a single neuron, but by a cluster of tightly coupled neural cells which
fire and oscillate in synchrony at a predefined frequency. Thus, this paper describes a method of tuning the parameters of
the Izhikevich spiking neuron model through genetic algorithm in order to enable the self-organization of the neural network.
Computational experiments were performed considering a network composed of neurons of the same type and another composed of
neurons of different types.

  • Content Type Journal Article
  • Pages 1-9
  • DOI 10.1007/s11047-011-9288-3
  • Authors
    • Gabriela E. Soares, Laboratório de Sistemas Inteligentes—LSI-CEFET-MG, Av. Amazonas 7675, CEP 30.510-000 Belo Horizonte, MG, Brazil
    • Henrique E. Borges, Laboratório de Sistemas Inteligentes—LSI-CEFET-MG, Av. Amazonas 7675, CEP 30.510-000 Belo Horizonte, MG, Brazil
    • Rogério M. Gomes, Laboratório de Sistemas Inteligentes—LSI-CEFET-MG, Av. Amazonas 7675, CEP 30.510-000 Belo Horizonte, MG, Brazil
    • Gustavo M. Zeferino, Laboratório de Sistemas Inteligentes—LSI-CEFET-MG, Av. Amazonas 7675, CEP 30.510-000 Belo Horizonte, MG, Brazil
    • Antônio P. Braga, Universidade Federal de Minas Gerais, Av. Antônio Carlos 6627, CEP 31270-010 Belo Horizonte, MG, Brazil