[FOM] Computability in Europe 2006 - Call for Participation

[S B Cooper]

                            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 at 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 at 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).