Skip to main content
main-content

Über dieses Buch

This book constitutes the thoroughly refereed post-conference proceedings of the 11th International Conference on Unconventional Computation, UC 2012, held in Orléans, France, during September 3-7, 2012. The 28 revised full papers presented were carefully selected from numerous submissions. Conference papers are organized in 4 technical sessions, covering topics of hypercomputation, chaos and dynamical systems based computing, granular, fuzzy and rough computing, mechanical computing, cellular, evolutionary, molecular, neural, and quantum computing, membrane computing, amorphous computing, swarm intelligence; artificial immune systems, physics of computation, chemical computation, evolving hardware, the computational nature of self-assembly, developmental processes, bacterial communication, and brain processes

Inhaltsverzeichnis

Frontmatter

Session 1: Invited Talks

The Holy Grail: Finding the Genetic Bases of Phenotypic Characters

A main goal in human genomics is to compare the genetic sequences of different individuals to identify chromosomal regions where genetic variants are shared. Using this information, researchers will be able to discover how genetic differences impact on the expression of different phenotypic characters such as disease susceptibility or drug resistance. One of the main sources of genetic variation is represented by Single Nucleotide Polymorphisms (SNPs) possessed by individuals in a population and compiled into

haplotypes

. Haplotypes allow to highlight the combined effect of multiple SNPs on the phenotypic character and greatly increase the significance of the predicted associations. Since each person possesses two haplotypes for most regions of the genome but they cannot be directly extracted by common wet-lab experiments, the inference of haplotype pairs from “raw” genetic data (

genotypes

) is a key computational problem in this area.

Paola Bonizzoni

Inductive Complexity of P versus NP Problem

Extended Abstract

Using the complexity measure developed in [7,3,4] and the extensions obtained by using inductive register machines of various orders in [1,2], we determine an upper bound on the inductive complexity of second order of the P versus NP problem. From this point of view, the P versus NP problem is more complex than the Riemann hypothesis.

Cristian S. Calude, Elena Calude, Melissa S. Queen

Advances in Embryomorphic Engineering

Generally, phenomena of spontaneous pattern formation are random and repetitive, whereas elaborate devices are the deterministic product of human design. Yet, biological organisms and collective insect constructions are exceptional examples of complex systems that are both self-organized

and

architectured. Can we understand their precise self-formation capabilities and integrate them with technological planning? Can physical systems be endowed with information, or informational systems be embedded in physics, to create autonomous morphologies and functions? A new field of research,

Morphogenetic

Engineering

, was established [1] to explore the modeling and implementation of “self-architecturing” systems. Particular emphasis is set on the

programmability

and computational abilities of self-organization, properties that are often underappreciated in complex systems science—while, conversely, the benefits of self-organization are often underappreciated in engineering methodologies.

René Doursat

Reasoning As Though

It is sometimes useful to know that we can safely reason as though something were true, even when it almost certainly is not. This talk will survey instances of this phenomenon in computer science and molecular programming.

Jack H. Lutz

Universality and the Halting Problem for Cellular Automata in Hyperbolic Spaces: The Side of the Halting Problem

In this paper, we remind results on universality for cellular automata in hyperbolic spaces, mainly results about weak universality, and we deal with the halting problem in the same settings. This latter problem is very close to that of strong universality. The paper focuses on the halting problem and it can be seen as a preliminary approach to strong universality about cellular automata in hyperbolic spaces.

Maurice Margenstern

Session 2: Tutorials

An Introduction to Tile-Based Self-assembly

In this tutorial, we give a brief introduction to the field of tile-based algorithmic self-assembly. We begin with a description of Winfree’s abstract Tile Assembly Model (aTAM) and a few basic exercises in designing tile assembly systems. We then survey a series of results in the aTAM. Next, we introduce the more experimentally realistic kinetic Tile Assembly Model (kTAM) and provide an exercise in error correction within the kTAM, then an overview of kTAM results. We next introduce the 2-Handed Assembly Model (2HAM), which allows entire assemblies to combine with each other in pairs, along with an exercise in developing a 2HAM system, and then give overviews of a series of 2HAM results. Finally, we briefly introduce a wide array of more recently developed models and discuss their various tradeoffs in comparison to the aTAM and each other.

Matthew J. Patitz

Spatial Computing in MGS

This short paper motivates and introduces the tutorial on MGS and spatial computing presented at UCNC 2012.

Antoine Spicher, Olivier Michel, Jean-Louis Giavitto

Session 3: Regular Papers

P Systems Controlled by General Topologies

In this paper we investigate the use of general topological spaces as control mechanisms for basic classes of membrane systems employing only rewrite and communication rules.

Erzsébet Csuhaj-Varjú, Marian Gheorghe, Mike Stannett

P Systems with Minimal Left and Right Insertion and Deletion

In this article we investigate the operations of insertion and deletion performed at the ends of a string. We show that using these operations in a P systems framework (which corresponds to using specific variants of graph control), computational completeness can even be achieved with the operations of left and right insertion and deletion of only one symbol.

Rudolf Freund, Yurii Rogozhin, Sergey Verlan

Lower Bounds on the Complexity of the Wavelength-Based Machine

The optical wavelength-based machine, or simply w-machine, is a computational model designed based on physical properties of light. The machine deals with sets of binary numbers, and performs computation using four defined basic operations. The sets are implemented as light rays and wavelengths are considered as binary numbers. Basic operations are then implemented using simple optical devices.

In this paper, we have provided a polynomial lower bound on the complexity of any

w

-machine computing all satisfiable SAT formulas. We have shown that the provided lower bound is tight by providing such a

w

-machine. Although the size complexity of the SAT problem on w-machine is polynomial, but, according to the provided optical implementation, it requires exponential amount of energy to be computed.

We have also provided an exponential lower bound on the complexity of most of

w

-machine languages, by showing that when

n

tends to infinity, the ratio of

n

-bit languages requiring exponential size

w

-machine to be computed, to the number of all

n

-bit languages, converges to 1.

Sama Goliaei, Mohammad-Hadi Foroughmand-Araabi

String Matching with Involutions

We propose a novel algorithm for locating in a text

T

every occurrence of a string that can be obtained from a given pattern

P

by successively applying antimorphic involutions on some of its factors. When the factors on which these involutions are applied overlap, a linear time algorithm is obtained. When we apply the involutions to non-overlapping factors we obtain an algorithm running in

${\mathcal{O}}(|T||P|)$

time and

${\mathcal{O}}(|P|)$

space, in the worst case. We also improve the latter algorithm to achieve linear average running time, when the alphabet of the pattern is large enough.

Cristian Grozea, Florin Manea, Mike Müller, Dirk Nowotka

Distributed Execution of Automata Networks on a Computing Medium: Introducing IfAny Machines

A computing medium is a set of Processing Elements (PE) homogeneously distributed in space, with connections local in space. PEs are fine grain, and are therefore modeled as Finite State Machine (FSM). In this elementary framework, the interaction between PEs can be defined by a set of instructions, which return a value depending on the neighbor’s state. That value is then used as an input to the FSM. This paper studies an instruction set reduced to a single instruction called “IfAny

q

” that tests IfAny of the neighbors has a given state

q

. This instruction puts a minimal requirement on hardware: there is no need for addressing channels, communication can be done by local radio broadcasting. An IfAny machine

A

running on a network tailored for a specific computational task can be executed in parallel on an IfAny medium whose network is fixed and reflects the locality in space. The execution involves an embedding of

A

’s network, and a transformation of

A

’s FSM, adding a 3 states register. We analyse the example of

A

realizing the addition of

n

binary numbers. With a carefully chosen network embedding, the resulting parallel execution is optimal in time and space with respect to VLSI complexity.

This work demonstrates that IfAny machines can be seen as a rudimentary programming method for computing media. It represents a first step of our long term project which is to realize general purpose parallel computation on a computing medium.

Frederic Gruau, Luidnel Maignan

Symbol Representations in Evolving Droplet Computers

We investigate evolutionary computation approaches as a mechanism to program networks of excitable chemical droplets. For this kind of systems, we assigned a specific task and concentrated on the characteristics of signals representing symbols. Given a Boolean function like Identity, OR, AND, NAND, XOR, XNOR or the half-adder as the target functionality, 2D networks composed of 10×10 droplets were considered in our simulations. Three different setups were tested: Evolving network structures with fixed on/off rate coding signals, coevolution of networks and signals, and network evolution with fixed but pre-evolved signals. Evolutionary computation served in this work not only for designing droplet networks and input signals but also to estimate the quality of a symbol representation: We assume that a signal leading to faster evolution of a successful network for a given task is better suited for the droplet computing infrastructure. Results show that complicated functions like XOR can evolve using only rate coding and simple droplet types, while other functions involving negations like the NAND or the XNOR function evolved slower using rate coding. Furthermore we discovered symbol representations that performed better than the straight forward on/off rate coding signals for the XNOR and AND Boolean functions. We conclude that our approach is suitable for the exploration of signal encoding in networks of excitable droplets.

Gerd Gruenert, Gabi Escuela, Peter Dittrich

Inductive Complexity of Goodstein’s Theorem

We use the recently introduced [1, 2] inductive complexity measure to evaluate the inductive complexity of Goodstein’s Theorem, a statement that is independent from Peano Arithmetic.

Joachim Hertel

Towards a Biomolecular Learning Machine

Learning and generalisation are fundamental behavioural traits of intelligent life. We present a synthetic biochemical circuit which can exhibit non-trivial learning and generalisation behaviours, which is a first step towards demonstrating that these behaviours may be realised at the molecular level. The aim of our system is to learn positive real-valued weights for a real-valued linear function of positive inputs. Mathematically, this can be viewed as solving a non-negative least-squares regression problem. Our design is based on deoxyribozymes, which are catalytic DNA strands. We present simulation results which demonstrate that the system can converge towards a desired set of weights after a number of training instances are provided.

Matthew R. Lakin, Amanda Minnich, Terran Lane, Darko Stefanovic

Tractional Motion Machines: Tangent-Managing Planar Mechanisms as Analog Computers and Educational Artifacts

Concrete and virtual machines play a central role in the both Unconventional Computing (machines as computers) and in Math Education (influence of artifacts on reaching/producing abstract thought). Here we will examine some fallouts in these fields for the Tractional Motion Machines, planar mechanisms based on some devices used to plot the solutions of differential equations by the management of the tangent since the late 17th century.

Pietro Milici

Computing with Sand: On the Complexity of Recognizing Two-dimensional Sandpile Critical Configurations

In this work we study the complexity of recognizing the critical configurations of The Two-dimensional Abelian Sandpile Model, we review some known facts and we prove that there does not exist a polylog-depth uniform polynomial size family of monotone boolean circuits solving this problem, this result suggests that the recognition of critical configurations cannot be accomplished in polylog time employing a polynomial number of processors.

J. Andres Montoya

Genome Parameters as Information to Forecast Emergent Developmental Behaviors

In this paper we measure genomic properties in EvoDevo systems, to predict emergent phenotypic characteristic of artificial organisms. We describe and compare three parameters calculated out of the composition of the genome, to forecast the emergent behavior and structural properties of the developed organisms. The parameters are each calculated by including different genomic information. The genotypic information explored are: purely regulatory output, regulatory input and relative output considered independently and an overall parameter calculated out of genetic dependency properties. The goal of this work is to gain more knowledge on the relation between genotypes and the behavior of emergent phenotypes. Such knowledge will give information on genetic composition in relation to artificial developmental organisms, providing guidelines for construction of EvoDevo systems. A minimalistic developmental system based on Cellular Automata is chosen in the experimental work.

Stefano Nichele, Gunnar Tufte

Heterotic Computing Examples with Optics, Bacteria, and Chemicals

Unconventional computers can perform embodied computation that can directly exploit the natural dynamics of the substrate. But such

in materio

devices are often limited, special purpose machines. To be practically useful, unconventional devices are usually be combined with classical computers or control systems. However, there is currently no established way to do this, or to combine different unconventional devices.

In this position paper we describe

heterotic unconventional computation

, an approach that focusses on

combinations

of unconventional devices. This will need a sound semantic framework defining how diverse unconventional computational devices can be combined in a way that respects the intrinsic computational power of each, whilst yielding a hybrid device that is capable of more than the sum of its parts. We also describe a suite of diverse physical implementations of heterotic unconventional computers, comprising computation performed by bacteria hosted in chemically built material, sensed and controlled optically and chemically.

Susan Stepney, Samson Abramsky, Matthias Bechmann, Jerzy Gorecki, Viv Kendon, Thomas J. Naughton, Mario J. Perez-Jimenez, Francisco J. Romero-Campero, Angelika Sebald

Reliable Node Placement in Wireless Sensor Networks Using Cellular Automata

Wireless sensor networks are often used to provide critical measurements in unattended harsh environments. They should be designed to adequately monitor their surroundings while being resilient to environmental changes. Appropriate sensor node placement greatly influences their capability to perform this task. Cellular automata have properties very similar to those of wireless sensor networks. In this paper, we present a sensor node placement algorithm that runs on a cellular automaton and achieves adequate coverage, connectivity and sparsity while being resilient to changing environmental conditions.

Sami Torbey, Selim G. Akl

Robust Evaluation of Expressions by Distributed Virtual Machines

We show how expressions written in a functional programming language can be robustly evaluated on a modular asynchronous spatial computer by compiling them into a distributed virtual machine comprised of reified bytecodes undergoing diffusion and communicating via messages containing encapsulated virtual machine states. Because the semantics of the source language are purely functional, multiple instances of each reified bytecode and multiple execution threads can coexist without inconsistency in the same distributed heap.

Lance R. Williams

Session 4: Posters

Numerical Evaluation of the Average Number of Successive Guesses

This work has been inspired by problems addressed in the field of computer security, where the attacking of, e.g., password systems is an important issue. In [2] Lundin

et

al

. discuss measures related to the number of guesses or attempts a supposed attacker needs for revealing information. Here several numerical approaches are discussed for evaluating the average number of successive guesses required for correctly guessing the value of a string of independent and identically-distributed random variables. The guessing strategy used is guessing strings in decreasing order of probability [1].

Kerstin Andersson

Discrete Discs and Broadcasting Sequences

Neighbourhood Sequences are deemed to be important in many practical applications within digital imaging through their application in measuring digital distance.

Aggregation of neighbourhood sequences based on classical digital distance functions was proposed as an alternative method for organising swarms or robots on the non-oriented grid environment in [1]. Wave phenomena generated nodal patterns in a discrete environment via the two neighbourhood sequences providing a distributed algorithm to find the centre of a digital disc. The geometric shapes that can be formed by such sequences in 2-D are quite limited and so constraints are relaxed to allow any two points at euclidean distance

r

(

r

-neighbours) such neighbourhoods represented by the digital disc of radius

r

.

Thomas Nickson, Igor Potapov

Optical Analog Feedback in Euglena-Based Neural Network Computing

Using living microbial cells in computational processing is a fascinating challenge to incorporate their autonomous adaptation and exploration abilities into a physical computing algorithm [1]. When the stimulus to the cells is given as analog values, more flexible solutions would be expected in microbe-based neurocomputing [1] owing to the diversity of reaction threshold among the cells. We have investigated the optical analog feedback in

Euglena

-based neurocomputing, for a task to select some from 16 compartments with avoiding the first and second nearest compartments [2].

Kazunari Ozasa, Jeesoo Lee, Simon Song, Mizuo Maeda, Masahiko Hara

Gardening Cyber-Physical Systems

Today’s artefacts, from small devices to buildings and cities, are, or are becoming, cyber-physical socio-technical systems, with tightly interwoven material and computational parts. Currently, we have to laboriously build such systems, component by component, and the results are often difficult to maintain, adapt, and reconfigure. Even “soft” ware is brittle and non-trivial to adapt and change.

Susan Stepney, Ada Diaconescu, René Doursat, Jean-Louis Giavitto, Taras Kowaliw, Ottoline Leyser, Bruce MacLennan, Olivier Michel, Julian F. Miller, Igor Nikolic, Antoine Spicher, Christof Teuscher, Gunnar Tufte, Francisco J. Vico, Lidia Yamamoto

Towards a Theory of Self-constructing Automata

Self constructing automata (SCA) are automata which construct their own state set

on the fly

. Here, we do not provide a class of automata, but rather a perspective on automata: we can reconstruct any class of automata as class of SCA. An SCA is defined by 1. an

input alphabet

Σ and a

state alphabet

Ω, 2. a map

$\phi:\Sigma(\cup\epsilon)\rightarrow \wp(\Omega\times\Omega)$

; this map is homomorphically extended over strings and interprets concatenation as relation composition; and 3. an

accepting relation

F

 ⊆ 

i

×Ω

*

. For

$\mathfrak{A}$

an SCA, put

$L(\mathfrak{A})=\{w:\phi(w)\cap F\neq\emptyset\}$

.

Christian Wurm

Flower Pollination Algorithm for Global Optimization

Flower pollination is an intriguing process in the natural world. Its evolutionary characteristics can be used to design new optimization algorithms. In this paper, we propose a new algorithm, namely, flower pollination algorithm, inspired by the pollination process of flowers. We first use ten test functions to validate the new algorithm, and compare its performance with genetic algorithms and particle swarm optimization. Our simulation results show the flower algorithm is more efficient than both GA and PSO. We also use the flower algorithm to solve a nonlinear design benchmark, which shows the convergence rate is almost exponential.

Xin-She Yang

Backmatter

Weitere Informationen

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.

Whitepaper

- ANZEIGE -

INDUSTRIE 4.0

Der Hype um Industrie 4.0 hat sich gelegt – nun geht es an die Umsetzung. Das Whitepaper von Protolabs zeigt Unternehmen und Führungskräften, wie sie die 4. Industrielle Revolution erfolgreich meistern. Es liegt an den Herstellern, die besten Möglichkeiten und effizientesten Prozesse bereitzustellen, die Unternehmen für die Herstellung von Produkten nutzen können. Lesen Sie mehr zu: Verbesserten Strukturen von Herstellern und Fabriken | Konvergenz zwischen Soft- und Hardwareautomatisierung | Auswirkungen auf die Neuaufstellung von Unternehmen | verkürzten Produkteinführungszeiten
Jetzt gratis downloaden!

Bildnachweise