Machines, Computations and Universality

September 9-11, 2013
University of Zürich, Switzerland






Program

Monday, September 9, 2013

Registration and Opening
8.30 - 9.20	Registration
9.20 - 9.30	Opening of MCU 2013
9.30 - 10.30	Invited talk: Universal Pattern Generation by Cellular Automata Jarkko Kari
10.30 - 11.00	Coffee Break
Session 1
11.00 - 11.30	How to Obtain Universality in P Systems with One Catalyst Rudolf Freund and Gheorghe Păun
11.30 - 12.00	One-dimensional Array Grammars and P Systems with Array Insertion and Deletion Rules Rudolf Freund, Sergiu Ivanov, Marion Oswald and K.G. Subramanian
12.00 - 12.30	A Small Universal Petri Net Dmitry Zaitsev
12.30 - 14.00	Lunch
14.00 - 15.00	Invited talk: Intrinsic universality and the computational power of self-assembly Damien Woods
15.00 - 15.30	Coffee Break
Session 2
15.30 - 16.00	On the Equivalence of Cellular Automata and the Tile Assembly Model Matthew Patitz and Jacob Hendricks
16.00 - 16.30	Intrinsic Universality of Causal Graph Dynamics Simon Martiel and Bruno Martin
16.30 - 17.00	About Strongly Universal Cellular Automata Maurice Margenstern

Tuesday, September 10, 2013

9.00 - 10.00	Invited talk: Ludicrously fast universal computation and construction with reconfigurable molecular robots Erik Winfree
10.00 - 10.30	Coffee Break
Session 3
10.30 - 11.00	AND and/or OR: Uniform Polynomial-Size Circuits Niall Murphy and Damien Woods
11.00 - 11.30	Satisfiability of cross product terms is complete for real nondeterministic polytime Blum-Shub-Smale machines Christian Herrmann, Johanna Sokoli and Martin Ziegler
11.30 - 12.00	Topology and Non-Deterministic Polynomial Time Computation : Avoidance of The Misbehaviour of Hub-Free Diagrams and Consequences Anthony Gasperin
12.00 - 13.30	Lunch
13.30 - 15.00	Open problems session
15.00 - 15.30	Coffee Break
15.30 - 17.00	Open problems session
19.00	Conference dinner at Die Giesserei

Wednesday, September 11, 2013

9.00 - 10.00	Invited talk: Reversible Logic Elements with Memory and Their Universality Kenichi Morita
10.00 - 10.30	Coffee Break
Session 4
10.30 - 11.00	Tiling Problems on Baumslag-Solitar groups Nathalie Aubrun and Jarkko Kari
11.00 - 11.30	Hyperbolic tilings and formal language theory Maurice Margenstern and K.G. Subramanian
11.30 - 11.50	Fractal Dimension of Space-time Diagrams and the Runtime Complexity of Small Turing Machines Joost Joosten, Fernando Soler-Toscano and Hector Zenil
11.50 - 12.10	Machine Spaces: Axioms and Metrics Jörg Zimmermann and Armin Cremers
12.10 - 13.30	Lunch
13.30 - 14.30	Invited talk: Explorations in computer-assisted computer science Liesbeth De Mol
14.30 - 15.00	Coffee Break
Session 5
15.00 - 15.20	Causal sets for geometrical Gandy machines and Gandy machines over multisets Adam Obtułowicz
15.20 - 15.40	Array Automata on Cayley Grids Rudolf Freund and Marion Oswald
15.40 - 16.00	Formal Language Questions for Eulerian Trails Henning Fernau and Meenakshi Paramasivan
16.00 - 16.20	(An Outline Of) A Fault-Tolerant Turing Machine Ilir Çapuni