Computability in Europe 2006 - Call for Participation

Computability in Europe 2006 - Call for Participation

[Arnold Beckmann]

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