Computability in Europe 2006
Logical Approaches to Computational Barriers

Contributed Papers

The following papers have been accepted for presentation at CiE 2006. Some of these papers (indicated by LNCS logo) have been accepted for publication in the pre-proceedings volume published in the Lecture Notes in Computer Science volume 3988, the others will be published in our local proceedings. All authors of papers presented at CiE 2006 can be invited to submit papers to one of the post-conference publications.

Author Title
Hajnal Andréka Relativity theory for logicians and new computing paradigms
Marat Arslanov Generalized tabular reducibilities in infinite levels of Ershov hierarchy
LNCS logo Josef Berger The logical strength of the uniform continuity theorem
Jens Blanck Note on Reducibility Between Domain Representations
LNCS logo Paul Brodhead, Douglas Cenzer and Seyyed Dashti Random Closed Sets
Riccardo Bruni Gödel, Turing, the Undecidability Results and the Nature of Human Mind
LNCS logo Douglas Cenzer and Zia Uddin Logspace Complexity of Functions and Structures
LNCS logo Alexey Chernov and Juergen Schmidhuber Prefix-like Complexities and Computability in the Limit
Jose Felix Costa and Jerzy Mycka The conjecture P ≠ NP given by some analytic condition
Paolo Cotogno Decidability of arithmetic through hypercomputation: a logical objection
LNCS logo Fredrik Dahlgren Partial Continuous Functions and Admissible Domain Representations
LNCS logo Stefan Dantchev On the complexity of the Sperner Lemma
LNCS logo Gregorio de Miguel Casado and Juan Manuel García Chamizo The Role of Algebraic Models and Type-2 Theory of Effectivity in Special
LNCS logo Paulin Jacobe de Naurois A Measure of Space for Computing over the Reals
Pavel Demenkov Computer simulation replacements aminoacids in proteins
LNCS logo David Doty Every sequence is decompressible from a random one
LNCS logo Jérôme Durand-Lose Reversible conservative rational abstract geometrical computation is Turing-universal
Birgit Elbl On generalising predicate abstraction
Willem Fouche Brownian motion and Kolmogorov complexity
Gaßner Christine A Structure with P = NP
Gaßner Christine Expansions of Structures with P = NP
Alexander Gavryushkin On Complexity of Ehrenfeucht Theories with Computable Model
Philipp Gerhardy Functional interpretation and modified realizability interpretation of the double-negation shift
LNCS logo Guido Gherardi An Analysis of Urysohn and Tietze-Urysohn Lemmas according to Borel Computability
Lev Gordeev Toward combinatorial proof of P < NP. Basic approach
Neal Harman Models of Timing Abstraction in Simultaneous Multithreaded and Multi-Core Processors
LNCS logo Charles Milton Harris Enumeration reducibility with polynomial time bounds
Eiju Hirowatari, Kouichi Hirata and Tetsuhiro Miyahara Finite Prediction of Recursive Real-Valued Functions
LNCS logo Tie Hou Coinductive Proof for Basic Real Computation
Iskander Kalimullin The Dyment reducibility on the algebraic structures and on the families of subsets of ω
Dazhou Kang, Baowen Xu, Jianjiang Lu and Yanhui Li Reasoning within the Extended Fuzzy Description Logics with Restricted TBoxes
LNCS logo Peter Koepke Infinite time register machines
Peter Koepke and Ryan Siders Computing the Recursive Truth Predicate on Ordinal Register Machines
Ekaterina Komendantskaya and Anthony Seda Bilattice-based Logic Programs: Automated Reasoning and Neural Computation
LNCS logo Krishna Shankara Narayanan Upper and Lower Bounds for the Computational Power of P Systems with Mobile Membranes
LNCS logo Lars Kristiansen Complexity-Theoretic Hierarchies
LNCS logo Oleg Kudinov and Victor Selivanov Undecidability in the Homomorphic Quasiorder of Finite Labeled Forests
LNCS logo Ugo Dal Lago and Simone Martini An Invariant Cost Model for the Lambda Calculus
LNCS logo Andrew Edwin Marcus Lewis The jump classes of minimal covers
Chung-Chih Li Clocking Type-2 Computation in The Unit Cost Model
John Longley On the calculating power of Laplace's demon
Maria Lopez-Valdes Scaled Dimension of Individual Strings
LNCS logo Barnaby Martin and Florent Madelaine Towards a trichotomy for quantified H-coloring.
LNCS logo Klaus Meer and Martin Ziegler Uncomputability below and up to the Real Halting Problem
LNCS logo Greg Michaelson and Paul Cockshott Constraints on hypercomputation
LNCS logo Philippe Moser Martingale Families and Dimension in P
Benedek Nagy and Sándor Vályi Solving a PSPACE-complete problem by a linear interval-valued computation
LNCS logo Keng Meng Ng, Frank Stephan and Guohua Wu Degrees of weakly computable reals
LNCS logo Peter Peshev and Dimiter Skordev A subrecursive refinement of the fundamental theorem of algebra
Petrus Hendrik Potgieter Hypercomputing the Mandelbrot Set?
Vadim Puzarenko Definability of the Field of Reals in Admissible Sets
Rose Hafsah Abdul Rauf Integrating Functional Programming Into C++:Implementation and Verification
LNCS logo Peter Schuster and Júlia Zappe Do Noetherian modules have Noetherian basis functions?
Victor Selivanov The Algebra of Labeled Forests Modulo Homomorphic Equivalence
LNCS logo Anton Setzer Partial Recursive Functions in Martin-Löf Type Theory
LNCS logo Merlijn Sevenster and Tero Tulenheimo Partially ordered connectives and ∑11 on finite models
Alan Skelley Third-Order Computation and Bounded Arithmetic
LNCS logo Boris Solon Co-total enumeration degrees
LNCS logo Alexandra Soskova Relativized Degree Spectra
Alexey Stukachev On inner constructivizability of admissible sets
Andreas Weiermann and Arnoud den Boer A sharp phase transition threshold for elementary descent recursive functions
Albert Ziegler Some Reflections on the Principle of Image Collection
LNCS logo Jeffery Zucker Primitive Recursive Selection Functions over Abstract Algebras

websites: Arnold Beckmann 2006-04-16