Logic List Mailing Archive
CiE 2006: Swansea, Jun/Jul 2006, Call for Participation
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).