Complexity of Simple Programs: Preface

Abstract

This is a special issue that grew out of work presented at The International Workshop on The Complexity of Simple Programs which was hosted at University College Cork, Ireland on the 6th and 7th of December, 2008. Speakers were by invitation, and the peer-reviewed workshop proceedings were published in the first volume of Electronic Proceedings in Theoretical Computer Science. The papers in this journal special issue were significantly extended from the workshop proceedings versions, with new results and more complete exposition, and all went through a thorough review process. We sincerely thank the anonymous reviewers for their valuable contribution in bringing the papers to their final form. The main topics of the workshop centred around simple models of computation and short programs that give rise to complicated behaviour. In particular, this special issue contains a number of papers that make connections between simple models of computation, program-size complexity, computational complexity, computational universality, Kolmogorov complexity, algorithmic self-assembly, and geometry. The International Workshop on The Complexity of Simple Programs was generously funded by the Boole Centre for Research in Informatics at University College Cork, to whom we are very grateful. The Boole Centre is funded by The Programme for Research in Third Level Institutions which is co-funded by the Irish Government and the European Union under Ireland's EU Structural Funds Programme 2007–2013. We would also like to thank Giorgio Ausiello, Ioannis Havoutis, Ella Chen and Chen Jie for their help with the special issue.

Additional details