Unconventional Computation: 4th International Conference, UC 2005, Sevilla, Spain, October 3 – 7, 2005. Proceedings

Thomas Bäck, Ron Breukelaar (auth.), Cristian S. Calude, Michael J. Dinneen, Gheorghe Păun, Mario J. Pérez-Jímenez, Grzegorz Rozenberg (eds.)3540291008, 9783540291008

The Fourth International Conference on Unconventional Computation, UC 2005, organized under the auspices of EATCS by the Centre for Discrete Mathematics and Theoretical Computer Science and the Department of C- puter Science and Arti?cial Intelligence of the University of Seville, was held in Seville, October 3–7, 2005. Seville, one of the most beautiful cities in Spain, is at its best in October. An explosion of colour and contrast: ?amenco, bull?ghting, and a lively at- sphere in the streets due to the open and friendly nature of its people. The river Guadalquivir, the Cathedral and the Golden Tower are all places full of magic where the visitor can feel the spirit of a city which is eternally romantic. The series of International Conferences Unconventional Computation (UC),https://www.cs.auckland.ac.nz/CDMTCS/conferences/uc/isdevoted to all aspects of unconventional computation, theory as well as experiments and applications. Typical, but not exclusive, topics are: natural computing including quantum, cellular,molecular, neural and evolutionarycomputing; chaosand – namical systems based computing; and various proposals for computations that go beyond the Turing model. The ?rst venue of the Unconventional Computation Conference (formerly called Unconventional Models of Computation) was Auckland, New Zealand in 1998; subsequent sites of the conference were Brussels, Belgium in 2000 and Kobe, Japan in 2002. The titles of the proceedings volumes from past UC Conferences are as follows: 1. C.S. Calude, J. Casti, M.J. Dinneen (eds.). Unconventional Models of C- putation, Springer-Verlag, Singapore, 1998, viii + 426 pp. ISBN: 981-3083- 69-7.

---

Table of contents :
Front Matter….Pages –
Using Genetic Algorithms to Evolve Behavior in Cellular Automata….Pages 1-10
Quantum Searching Amidst Uncertainty….Pages 11-18
Logic Functions of the Genomic Cis-regulatory Code….Pages 19-19
Structural DNA Nanotechnology: Molecular Construction and Computation….Pages 20-31
Natural Inspiration for Artificial Adaptivity: Some Neurocomputing Experiences in Robotics….Pages 32-45
On Self-assembly in Population P Systems….Pages 46-57
A Web-Based P Systems Simulator and Its Parallelization….Pages 58-69
Communication Complexity as a Principle of Quantum Mechanics….Pages 70-81
On Model-Checking of P Systems….Pages 82-93
Looking for Simple Common Schemes to Design Recognizer P Systems with Active Membranes That Solve Numerical Decision Problems….Pages 94-104
P Systems with Active Membranes, Without Polarizations and Without Dissolution: A Characterization of P….Pages 105-116
Discrete State Transition Systems on Continuous Space-Time: A Theoretical Model for Amorphous Computing….Pages 117-129
On Reversible Cellular Automata with Finite Cell Array….Pages 130-141
A Computational Model for Self-assembling Flexible Tiles….Pages 142-156
On Formulations of Firing Squad Synchronization Problems….Pages 157-168
Computation in One-Dimensional Piecewise Maps and Planar Pseudo-Billiard Systems….Pages 169-175
On the Importance of Parallelism for Quantum Computation and the Concept of a Universal Computer….Pages 176-190
On Computational Complexity of Counting Fixed Points in Symmetric Boolean Graph Automata….Pages 191-205
A New Sibling of BQP….Pages 206-213
A Twelve-State Optimum-Time Synchronization Algorithm for Two-Dimensional Rectangular Cellular Arrays….Pages 214-223
Computing by Self-reproduction: Autopoietic Automata….Pages 224-236
Lower Bounds on the Computational Power of an Optical Model of Computation….Pages 237-250
On Counterfactual Computation….Pages 251-266
Back Matter….Pages –