Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Special Issue on Unconventiona...

Special Issue on Unconventional Computing

Jarkko Kari, Ion Petre (Eds.), Special Issue on Unconventional Computing. Natural Computing 11(4), 2012.

Abstract:

This special issue of the Natural Computing is dedicated to selected papers presented at the 10th International Conference on Unconventional Computation, UC 2011. The conference was organized under the auspices of EATCS and Academia Europaea, by the Department of Mathematics of the University of Turku (Turku, Finland), and the Center for Discrete Mathematics and Theoretical Computer Science (Auckland, New Zealand). The event was held in Turku, Finland, during June 6–10, 2011.

The International Conference on Unconventional Computation (UC) series is devoted to all aspects of UC theory as well as experiments and applications. Typical, but not exclusive, topics are: natural computing including quantum, cellular, molecular, membrane, neural, and evolutionary computing, as well as chaos and dynamical system-based computing, and various proposals for computational mechanisms that go beyond the Turing model. The first venue of the UC Conference (formerly called Unconventional Models of Computation) was Auckland, New Zealand in 1998. Subsequent sites of the conference were Brussels, Belgium in 2000, Kobe, Japan in 2002, Seville, Spain in 2005, York, UK in 2006, Kingston, Canada in 2007, Vienna, Austria in 2008, Ponta Delgada, Portugal in 2009, and Tokyo, Japan in 2010.

The authors of the best papers presented at UC 2011 were invited to submit extended versions of their papers to this special issue of Natural Computing. All submissions were peer-reviewed according to the usual scientific standards of the journal. The ten selected papers span a wide variety of topics that are of interest in the field of natural computing.

The paper by Olivier Bouré, Nazim Fatès and Vincent Chevrier investigates cellular automata under asynchronous information transmission schemes. After synchronously or asynchronously updating the internal state of each cell, the transmission of the new state to neighbors may fail. A number of different behaviors are reported when variants of the scheme are applied on elementary cellular automata. A main observation is that changing the details of the update scheme can have drastic influence on the global behavior of the system.

The paper by Silvio Capobianco and Tommaso Toffoli studies conserved quantities in second-order cellular automata and, in particular, in a cellular automaton realization of the Ising spin model. The authors want to find out to which extend properties of continuous time systems can be converted to the discrete setting. More precisely, the possibility of a discrete version of the Noether’s theorem in the context of second-order cellular automata is discussed.

The paper by Ac. Cem Say and Abuzer Yakaryilmaz considers some variants of computation with closed time-like curves (CTCs). It is known from results of Aaronson and Watrous (2009) that the capability of sending a polynomial number of bits through a CTC to the past, and using it as part of the input, increases the computational power of constant-depth, polynomial-size Boolean circuits to match PSPACE; moreover, the same is true when adding the same capability to polynomial-time quantum computers. The authors give full characterizations of the classes of languages decided by polynomial time probabilistic and quantum computers that can only send a single classical bit to their past. They also such narrow CTCs make a difference between the computational power of quantum finite automata and their probabilistic counterparts.

The paper by Jürgen Dassow, Florin Manea and Bianca Truthe focuses on networks of evolutionary processors (NEPs), a bio-inspired language generating computational model. It is known that NEPs are equivalent to the model of phrase-structure grammars. The authors show that several restricted variants of NEPs preserve the computational power of the general model. They prove that NEPs remain computationally complete even in the case of single-state control automata; in this case however, the underlying graph is arbitrary. They show that universality can also be obtained with NEPs where the derivation rules can be applied at arbitrary positions, the communication is controlled by a finite automaton with at most two states, and either the rule sets are singletons, or the underlying graph is complete.

The paper by Jérôme Durand-Lose concerns signal machines in the context of abstract geometrical computations. These are continuous space–time counterparts of cellular automata where discrete signals have been replaced by continuous ones. The author investigates isolated accumulation points of signals, a kind of singularities that result from unbounded accelerations. It turns out that if all signals have rational speeds, and if the signal positions in the initial configuration are rational, the isolated accumulation times (resp. spatial accumulation points) are computably enumerable reals (resp. differences of computably enumerable reals). In the present paper the author proves the converse: any computably enumerable real time (or any difference of computably enumerable real spatial point) contains the unique accumulation point of some rational signal computation.

The paper by Russell Martin, Thomas Nickson and Igor Potapov introduces a novel approach for self-organization, partitioning and pattern formation on the non-oriented grid environment based on the generation of nodal patterns in the environment via sequences of discrete waves. They investigate geometric computations and constructions by a weak, static, swarm of robots arranged in a square lattice; each robot is represented by a broadcasting automaton with finite memory. The power of this approach is demonstrated by solving two geometric problems: the problem of finding the center of a digital disk starting from any points on its border and that of electing a set of automata that form the inscribed square of the same digital disk.

The paper by Radu Nicolescu and Huiling Wu proposes four fast synchronous distributed message-based algorithms to identify the maximum cardinality sets of edge- and node-disjoint paths, between a source node and target node in a digraph. Their algorithms are inspired and guided by a P system modeling exercise, but are suitable for any distributed implementation. Two of the algorithms are based on depth-first search and two are based on breadth-first search, all running in O(nf), where n is the number of nodes and f is the number of disjoint paths in the graph. The authors also discuss empirical results on the performance of their algorithms on a large set of randomly generated digraphs.The paper by David Sears and Kai Salomaa investigates Watson–Crick E0L systems. It is known that such systems employed with the standard trigger (a context-free language) are computationally universal. The authors introduce a notion of weak derivation mode where, for sentential forms in the trigger language, one can choose nondeterministically whether to apply the Watson–Crick morphism in the derivation. They prove that Watson–Crick E0L systems employing a regular trigger and the weak derivation mode remain computationally universal, improving the previously known universality result. They also show that the corresponding uni-transitional systems generate only a subclass of the ET0L languages.The paper by William Stevens implements Boolean logic functions using arrangements of toppling dominoes on the plane. By using dual-rail logic, the author succeeds to implement any combinatorial function without timing or order constraints. The arrangements also do not require bridges to allow one domino line to cross another.

The paper by Luděk Žaloudek and Lucáš Sekanina addresses the problem of faults in cellular automata systems. The authors advocate module redundancy as a feasible solution to fault tolerance. Experimental evaluation of the proposed method is done on a number of sample CA problems, including computation of majority, Conway’s Game of Life and self-replication of Byl’s loop.

We thank all the authors for their contributions. We are also greatly indebted to the referees for their valuable help in the preparation of this special issue.

August 2012
Turku, Finland

Jarkko Kari Ion Petre

BibTeX entry:

@PERIODICAL{ejKaPe12a,
  title = {Special Issue on Unconventional Computing},
  journal = {Natural Computing},
  volume = {11},
  number = {4},
  editor = {Kari, Jarkko and Petre, Ion},
  publisher = {Springer},
  year = {2012},
  keywords = {Natural Computing, Unconventional computing},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics, Computational Biomodeling Laboratory (Combio Lab)

Publication Forum rating of this publication: level 1

Edit publication