EPTCS 1
Proceedings International Workshop on
The Complexity of Simple Programs
Cork, Ireland, 6-7th December 2008
Edited by: Turlough Neary, Damien Woods, Tony Seda and Niall Murphy
|
Preface
Turlough Neary, Damien Woods and Anthony K. Seda | 1 |
|
Playing With Population Protocols
Olivier Bournez, Jérémie Chalopin, Johanne Cohen and Xavier Koegler | 3 |
|
Simplicity via Provability for Universal Prefix-free Turing Machines
Cristian S. Calude | 16 |
|
Complexity through the Observation of Simple Systems
Matteo Cavaliere and Peter Leupold | 22 |
|
A Concrete View of Rule 110 Computation
Matthew Cook | 31 |
|
On the boundaries of solvability and unsolvability in tag systems. Theoretical and Experimental Results.
Liesbeth De Mol | 56 |
|
Limitations of Self-Assembly at Temperature One (extended abstract)
David Doty, Matthew J. Patitz and Scott M. Summers | 67 |
|
Small Turing universal signal machines
Jérôme Durand-Lose | 70 |
|
Communications in cellular automata
Eric Goles, Pierre-Etienne Meunier, Ivan Rapaport and Guillaume Theyssier | 81 |
|
Multi-Head Finite Automata: Characterizations, Concepts and Open Problems
Markus Holzer, Martin Kutrib and Andreas Malcher | 93 |
|
Computational Power of P Systems with Small Size Insertion and Deletion Rules
Alexander Krassovitskiy, Yurii Rogozhin and Sergey Verlan | 108 |
|
Some Considerations on Universality
Manfred Kudlek | 118 |
|
Busy beavers gone wild
Grégory Lafitte | 123 |
|
The Pagoda Sequence: a Ramble through Linear Complexity, Number Walls, D0L Sequences, Finite State Automata, and Aperiodic Tilings
Fred Lunnon | 130 |
|
A Divergence Formula for Randomness and Dimension (Short Version)
Jack H. Lutz | 149 |
|
On the injectivity of the global function of a cellular automaton in the hyperbolic plane (extended abstract)
Maurice Margenstern | 153 |
|
A General Notion of Useful Information
Philippe Moser | 164 |
|
On acceptance conditions for membrane systems: characterisations of L and NL
Niall Murphy and Damien Woods | 172 |
|
Representing a P-complete problem by small trellis automata
Alexander Okhotin | 185 |
|
Intrinsically Universal Cellular Automata
Nicolas Ollinger | 199 |
|
A Particular Universal Cellular Automaton
Nicolas Ollinger and Gaétan Richard | 205 |
|
Self-Assembly of Infinite Structures
Matthew J. Patitz and Scott M. Summers | 215 |
|
Computational Processes and Incompleteness
Klaus Sutner | 226 |
|
New Choice for Small Universal Devices: Symport/Antiport P Systems
Sergey Verlan and Yurii Rogozhin | 235 |
The International Workshop on The Complexity of Simple Programs was hosted at University College Cork on the 6th and 7th of December, 2008. All speakers were invited. We were delighted by the positive response to the workshop and we would like to thank the speakers and their co-authors for submitting such an interesting selection of topics and results. All of the papers went through a thorough peer-review process and we thank the anonymous reviewers for their outstanding efforts. We would also like to acknowledge the valuable contribution of Leonid A. Levin who attended the workshop and presented joint work with Gene Itkis on simple self-organizing networks. This work is from their paper "Flat Holonomies on Automata Networks" which is not in this volume but may be found
here.
As can be seen from this volume, the topics and results presented at the meeting have a common thread that weaves through a large number of computational paradigms and ideas. However at the core, many of the same concerns are being addressed. One of the motivations for the meeting was to give an opportunity for the cross-fertilisation and communication of ideas and techniques, and to provide a starting-point for future collaborations.
Given the subject matter of the meeting, it is indeed fitting that it was generously sponsored by the Boole Centre for Research in Informatics (BCRI) here at University College Cork. BCRI is an ambitious project bringing together the expertise of the School of Mathematics, Applied Mathematics and Statistics and the Department of Computer Science to carry out interdisciplinary research under the banner of Informatics. The Boole Centre represents the interface between the two disciplines and provides the motivation for the link with the name of George Boole, who was the first Professor of Mathematics at the former Queen's College, Cork. We are deeply indebted to BCRI, and in particular to its co-directors John Morrison and Pat Fitzpatrick, for providing generous financial support for the meeting. Without this support the meeting could not have happened, and we hope this volume represents a fitting token to the generosity of BCRI.
We would like to give a very special mention to Maureen Dwane. Maureen did splendid work in the organisation of the workshop. Her efforts were well above the call of duty and we thank her for a job well-done. A sincere thanks goes to Niall Murphy for doing a great job on compiling the papers for this volume, and to Martin Flemming for valuable technical assistance during the workshop. Finally, we would like to thank EPTCS, in particular Rob van Glabbeek and Lane A. Hemaspaandra, for their help and for enabling us to bring this proceedings volume to a wide audience.
Turlough Neary
Damien Woods
Anthony K. Seda
Co-chairs
Cork, May 2009