[Apologies for multiple copies] CiE 2006 Computability in Europe 2006 : Logical Approaches to Computational Barriers 30 June - 5 July 2006 Swansea University, United Kingdom http://www.cs.swansea.ac.uk/cie06/ cie06@swansea.ac.uk CALL FOR PARTICIPATION Important deadlines: Informal Presentations 30 April, 2006 Early registration 15 May, 2006 * Some grants for UK students are still available * CiE 2006 is the second of a new conference series which serves as an interdisciplinary forum for researchers into all aspects of computability and the foundations of computer science. The scientific programme consists of two three-hour tutorials, nine plenary talks, six special sessions with four talks each, and over sixty contributed talks. For more details on the programme see the full list of talks below, or visit http://www.cs.swansea.ac.uk/cie06/ The conference venue and accommodation will be on the campus of Swansea University. Swansea lies at the southcoast of Wales, next to the beautiful Gower Peninsula. To register, submit an informal presentations, apply for a UK student grant, or to obtain any other information visit http://www.cs.swansea.ac.uk/cie06/ Contact: cie06@swansea.ac.uk ********* PROGRAMME ********* TUTORIALS Samuel R. Buss (San Diego, CA) Proof Complexity and computational hardness Julia Kempe (Paris) Quantum Algorithms PLENARY TALKS Jan Bergstra (Amsterdam) Elementary Algebraic Specifications of the Rational Function Field Luca Cardelli (Microsoft Research) Biological systems as reactive systems Martin Davis (New York, NY) The Church-Turing thesis: consensus and opposition John W Dawson (York, PA) Goedel and the origins of computer science Jan Krajicek (Prague) Forcing with random variables and proof complexity Elvira Mayordomo Camara (Zaragoza) The fractal dimension of complexity classes Istvan Nemeti (Budapest) Can general relativistic computers break the Turing barrier? Helmut Schwichtenberg (Munich) Program extraction from proofs in constructive analysis Andreas Weiermann (Utrecht) Phase transition thresholds in recursion theory SPECIAL SESSIONS PROOFS AND COMPUTATION organised by Alessandra Carbone and Thomas Strahm Kai Bruennler (Bern) Deep inference Roy Dyckhoff (St Andrews) LJQ: a focused calculus for intuitionistic logic Thomas Ehrhard (Marseille) About the Krivine machine and the Taylor expansion of lambda-terms Georges Gonthier (Microsoft Research) Using reflection to prove the Four Colour Theorem COMPUTABLE ANALYSIS organised by Peter Hertling and Dirk Pattinson Margarita Korovina (Aarhus) Complexity of bisimulations on Pfaffian hybrid systems Paulo Oliva (London) Computational interpretations of proofs in classical analysis Matthias Schroeder (Edinburgh) Admissible representations in computable analysis Xizhong Zheng (Cottbus) Computability theory of real numbers CHALLENGES IN COMPLEXITY organised by Klaus Meer and Jacobo Toran Johannes Koebler (Berlin) Complexity of graph isomorphism for restricted graph classes Sophie Laplante (Paris) Lower bounds using Kolmogorov complexity Janos A. Makowsky (Haifa) Computable graph invariants Mihai Prunescu (Freiburg) The fast elimination of quantifiers and some structures with P=NP according to the unit-cost model of computation FOUNDATIONS OF PROGRAMMING organised by Inge Bethke and Martin Escardo Erika Abraham (Freiburg) Fully abstract semantics of concurrent class-based languages Roland Backhouse (Nottingham) Datatype-Generic Reasoning James Leifer (INRIA, Le Chesnay) Transactional atomicity in programming languages Alban Ponse (Amsterdam) Program and thread algebra MATHEMATICAL MODELS OF COMPUTERS AND HYPERCOMPUTERS organised by Joel D Hamkins and Martin Ziegler Jean-Charles Delvenne (Louvain-la-Neuve) Turing-universal dynamical systems Benedikt Loewe (Amsterdam) Infinite time complexity theory Klaus Meer (Odense) Optimization and approximation problems related to polynomial system solving Philip Welch (Bristol) Admissibility and infinite time computation GOEDEL CENTENARY: HIS LEGACY FOR COMPUTABILITY organised by Matthias Baaz and John W Dawson Arnon Avron (Tel Aviv) From constructibility and absoluteness to computability and safety Torkel Franzen (Lulea) What does the incompleteness theorem add to the unsolvability of the halting problem? Wilfried Sieg (Pittsburgh, PA) Goedel's Conflicting approaches to effective calculability Richard Zach (Calgary, AB) Kurt Goedel, logic, and theoretical computer science CONTRIBUTED TALKS Hajnal Andreka (Budapest) Relativity theory for logicians and new computing paradigms Marat Arslanov (Kazan) Generalized tabular reducibilities in infinite levels of Ershov hierarchy Josef Berger (Munich) The logical strength of the uniform continuity theorem Jens Blanck (Swansea) Note on Reducibility Between Domain Representations Paul Brodhead, Douglas Cenzer and Seyyed Dashti (Florida) Random Closed Sets Riccardo Bruni (Florence) Goedel, Turing, the Undecidability Results and the Nature of Human Mind Douglas Cenzer (Florida) and Zia Uddin (Lock Haven, PA) Logspace Complexity of Functions and Structures Alexey Chernov (Manno) and Juergen Schmidhuber (Munich) Prefix-like Complexities and Computability in the Limit Jose Felix Costa (Lisbon) and Jerzy Mycka (Lublin) The conjecture P =/= NP given by some analytic condition Paolo Cotogno (Brescia) Decidability of arithmetic through hypercomputation: a logical objection Fredrik Dahlgren (Uppsala) Partial Continuous Functions and Admissible Domain Representations Ugo Dal Lago and Simona Martini (Bologna) An Invariant Cost Model for the Lambda Calculus Stefan Dantchev (Durham) On the complexity of the Sperner Lemma Gregorio de Miguel Casado and Juan Manuel Garcia Chamizo (Alicante) The Role of Algebraic Models and TTE in Special Purpose Processor Design Paulin Jacobe de Naurois (Paris) A Measure of Space for Computing over the Reals Pavel Demenkov (Novosibirsk) Computer simulation replacements aminoacids in proteins David Doty (Iowa) Every Sequence is Decompressible from a Random One Jerome Durand-Lose (Orleans) Reversible conservative rational abstract geometrical computation is Turing-universal Birgit Elbl (Munich) On generalising predicate abstraction Willem Fouche (Pretoria) Brownian motion and Kolmogorov complexity Gassner Christine (Greifswald) A Structure with P = NP Alexander Gavryushkin (Novosibirsk) On Complexity of Ehrenfeucht Theories with Computable Model Annelies Gerber (Paris) Some mathematical properties of input resolution refutations with non-tautological resolvents Philipp Gerhardy (Darmstadt) Functional interpretation and modified realizability interpretation of the double-negation shift Guido Gherardi (Siena) An Analysis of the Lemmas of Urysohn and Urysohn-Tietze according to effective Borel measurability Lev Gordeev (Tuebingen) Toward combinatorial proof of P < NP. Basic approach Neal Harman (Swansea) Models of Timing Abstraction in Simultaneous Multithreaded and Multi-Core Processors Charles Milton Harris (Leeds) Enumeration reducibility with polynomial time bounds Eiju Hirowatari (Kitakyushu), Kouichi Hirata (Kyushu) and Tetsuhiro Miyahara (Hiroshima) Finite Prediction of Recursive Real-Valued Functions Tie Hou (Swansea) Coinductive Proofs for Basic Real Computation Iskander Kalimullin (Kazan, Russia) The Dyment reducibility on the algebraic structures and on the families of subsets of omega Dazhou Kang, Baowen Xu, Jianjiang Lu and Yanhui Li (Southeast University, China) Reasoning within the Extended Fuzzy Description Logics with Restricted Boxes Peter Koepke (Bonn) Infinite time register machines Peter Koepke (Bonn) and Ryan Siders (Helsinki) Computing the Recursive Truth Predicate on Ordinal Register Machines Ekaterina Komendantskaya and Anthony Seda (Cork) Bilattice-based Logic Programs: Automated Reasoning and Neural Computation Shankara Narayanan Krishna (Bombay) Upper and Lower Bounds for the Computational Power of P Systems with Mobile Membranes Lars Kristiansen (Oslo) Complexity-Theoretic Hierarchies Oleg Kudinov and Victor Selivanov (Novosibirsk) Undecidability in the Homomorphic Quasiorder of Finite Labeled Forests Andrew Edwin Marcus Lewis (Siena) The jump classes of minimal covers Chung-Chih Li (Beaumont, TX) Clocking Type-2 Computation in The Unit Cost Model John Longley (Edinburgh) On the calculating power of Laplace's demon Maria Lopez-Valdes (Zaragoza) Scaled Dimension of Individual Strings Barnaby Martin and Florent Madelaine (Durham) Towards a Trichotomy for Quantified H-Coloring Klaus Meer (Odense) and Martin Ziegler (Paderborn) Uncomputability below the Real Halting Problem Greg Michaelson (Edinburgh) and Paul Cockshott (Glasgow) Constraints on hypercomputation Philippe Moser (Maria de Luna) Martingale Families and Dimension in P Benedek Nagy and Sandor Valyi (Debrecen) Solving a PSPACE-complete problem by a linear interval-valued computation Keng Meng Ng (Wellington), Frank Stephan (Singapore) and Gouhua Wu (Singapore) Degrees of Weakly Compact Reals Peter Peshev and Dimiter Skordev (Sofia) A Subrecursive Refinement of the Fundamental Theorem of Algebra Petrus Hendrik Potgieter (Pretoria) Hypercomputing the Mandelbrot Set? Vadim Puzarenko (Novosibirsk) Definability of the Field of Reals in Admissible Sets Rose Hafsah Abdul Rauf (Swansea) Integrating Functional Programming Into C++: Implementation and Verification Mihai Prunesco (Bucharest/Freiburg) Fast quantifier elimination means P = NP Peter Schuster and Julia Zappe (Munich) Do Noetherian modules have Noetherian basis functions? Anton Setzer (Swansea) Partial Recursive Functions in Martin-Loef Type Theory Merlijn Sevenster (Amsterdam) and Tero Tulenheimo (Helsinki) Partially ordered connectives and Sigma-1-1 on finite models Alan Skelley (Prague) Third-Order Computation and Bounded Arithmetic Boris Solon (Ivanovo) Co-total enumeration degrees Ivan Soskov (Sofia) Extensions of the semi-lattice of the enumeration degrees Alexandra Soskova (Sofia) Relativized Degree Spectra Alexey Stukachev (Novosibirsk) On inner constructivizability of admissible sets Andreas Weiermann and Arnoud den Boer (Utrecht) A sharp phase transition threshold for elementary descent recursive functions Albert Ziegler (Munich) Some Reflections on the Principle of Image Collection Jeffery Zucker (McMaster) Primitive Recursive Selection Functions over Abstract Algebras PROGRAMME COMMITTEE Samson Abramsky (Oxford), Benedikt Loewe (Amsterdam), Klaus Ambos-Spies (Heidelberg), Yuri Matiyasevich (St. Petersburg), Arnold Beckmann (co-chair), Dag Normann (Oslo), Ulrich Berger (Swansea), Giovanni Sambin (Padova), Olivier Bournez (Nancy), Uwe Schoening (Ulm), Barry Cooper (Leeds), Andrea Sorbi (Siena), Laura Crosilla (Florence), Ivan Soskov (Sofia), Costas Dimitracopoulos (Athens), Leen Torenvliet (Amsterdam), Abbas Edalat (London), John Tucker (Swansea, co-chair), Fernando Ferreira (Lisbon), Peter van Emde Boas (Amsterdam), Ricard Gavalda (Barcelona), Klaus Weihrauch (Hagen), Giuseppe Longo (Paris) ORGANISERS Arnold Beckmann, Ulrich Berger, S Barry Cooper, Phil Grant, Oliver Kullmann, Benedikt Loewe, Faron Moller, Monika Seisenberger, Anton Setzer, John V Tucker CiE 2006 received financial support by the Department of Computer Science at Swansea, the British Logic Colloquium (BLC), the British Engineering and Physical Sciences Research Council (EPSRC), the Kurt Goedel Society (KGS) in Vienna, the London Mathematical Society (LMS), the Welsh Development Agency (WDA) and IT Wales. Other sponsors are the Association for Symbolic Logic (ASL), the British Computer Society (BCS) and the European Association for Theoretical Computer Science (EATCS).