Institute for Logic, Language and Computation
CiE 2005: Contributed Papers

Contributed Papers

The following papers have been accepted for presentation at CiE 2005. Some of these papers (indicated by ) have been accepted for publication in the pre-proceedings volume published in the Springer Lecture Notes in Computer Science. All authors of papers presented at CiE 2005 can be invited to submit papers to one of the post-conference publications.

Matthias Baaz (Vienna), Rosalie Iemhoff (Vienna) Skolemization in Intuitionistic Logic
Jose L. Balcazar (Barcelona) Query learning of Horn formulas revisited
George Barmpalias (Leeds) Computably enumerable sets in the Solovay and Strong Weak truth table degrees
Mathias Barra (Oslo), Lars Kristiansen (Oslo) The Small Grzegorczyk Classes and the Typed lambda-Calculus
Giulia Battilotti (Padova), Paola Zizzi (Padova) The internal logic of Bell's states
Josef Berger (München) The Fan Theorem and Uniform Continuity
Udi Boker (Tel Aviv), Nachum Dershowitz How to Compare the Power of Computational Models
Douglas Cenzer, Jeff Remmel The Complexity of Inductive Definability
Yi-Xiang Chen (Shanghai), Jie Zhou Fuzzy Interval-valued Processes Algebra
Pieter Collins (Amsterdam) Computable Analysis in Systems and Control
Jose Felix Costa (Lisboa), Jerzy Mycka (Lublin) Polynomial complexity for analog computation
Laura Crosilla, Andrea Cantini Constructive set theory with operations
Jérôme Durand-Losé (Orléans) Abstract geometrical computation: Turing-computing ability and undecidability
Olivier Finkel (Paris) Borel ranks and Wadge degrees of context free omega-languages
Dina Goldin (Storrs CT), Peter Wegner (Providence RI) The Church-Turing Thesis: Breaking the Myth
Daniel Graça (Faro), Manuel Campagnolo (Lisbon), Jorge Buescu (Lisbon) Robust Simulations of Turing Machines with Analytic Maps and Flows
Vince Grolmusz (Budapest) Defying dimensions modulo 6
Miguel Ángel Gutiérrez-Naranjo, Mario Pérez-Jiménez Francisco José Romero-Campero Solving SAT with membrane creation
Charles Harris Symmetric Enumeration Reducibility
Montserrat Hermo (San Sebastián), Joxe Gaintzarain, Marisa Navarro Learning Conjunctions of Hornsupset Clauses
Eiju Hirowatari, Kouichi Hirata, Tetsuhiro Miyahara, Setsuo Arikawa On the Prediction of Recursive Real-Valued Functions
Paulin Jacobe de Naurois, Olivier Bournez, Felipe Cucker, Jean-Yves Marion Logical Characterizations of P and NP over an Arbitrary Structure K
Herman Ruge Jervell (Oslo) Finite trees as ordinals
Herman Ruge Jervell (Oslo) Labeled finite trees as ordinal diagrams
Viv Kendon, William J Munro Entanglement and its Role in Shor's Algorithm
Ali A.Khanban (London), Abbas Edalat (London), A. Lieutier (Aix-en-Provence, Grenoble) Computability in Computational Geometry
Tien D. Kieu Hypercomputability in Quantum Mechanics
Bjørn Kjos-Hanssen (Storrs CT) Almost everywhere domination and K-triviality
Peter Koepke (Bonn) Computing a Model of Set Theory
Margarita Korovina, Oleg Kudinov Towards Computability of Higher Type Continuous Data
Lars Kristiansen (Oslo), Neil D. Jones (Copenhagen) The Flow of Data and the Complexity of Algorithms
Igor Kuznetsov (Ulyanovsk) On an embedding of N5 lattice into the Turing degrees
Branimir Lambov Complexity in a Type-1 Framework for Computable Analysis
Branimir Lambov RealLib: an efficient implementation of exact real numbers
Joseph Manning, Michel Schellekens A Programming Language for Automated Average-Case Time Analysis
Klaus Meer On some relations between approximation problems and PCPs over the real numbers
Krzysztof Michalak (Wrocław) , Halina Kwaśnicka (Wrocław) Correlation Dimension and the Quality of Forecasts Given by a Neural Network
Kees Middelburg (Eindhoven), Jan Bergstra (Amsterdam) A Thread Algebra with Multi-Level Strategic Interleaving
Pierluigi Minari Proof-Theoretical Methods in Combinatory Logic and Lambda-Calculus
Victor Mitrana, Florin Manea, Carlos Martin-Vide Accepting Networks of Splicing Processors
Erich Monteleone On the infinitary formal systems and Infinite Time Turing Machines
Marcin Mostowski Potential infinity and the Church thesis
Benedek Nagy An Interval-valued Computing Device
Stela Nikolova On the notion of forall-definedness of non-deterministic programs
Thanases Pheidas, Xavier Vidaux Complexity of addition and the set of squares: The analogue of Büchi's problem for rational functions
Igor Potapov (Liverpool), Oleksiy Kurganskyy Universality of Walking Automata on a Class of Geometric Environments
Jan Reimann (Heidelberg), Rod Downey (Wellington) Schnorr Dimension
Victor Selivanov (Novosibirsk) Some reducibilities on regular sets
Krishna Shankara Narayanan (Mumbai) The Power of Mobility : Four Membranes Suffice
Dimiter Skordev A computability notion for locally finite lattices
Boris Solon Non-total enumeration degrees
Ivan Soskov (Sofia) Uniform Operators
Alexandra Soskova (Sofia) Minimal Pairs and Quasi-Minimal Degrees for the Joint Spectra of Structures
Alexey Stukachev Presentations of Structures in Admissible Sets
Haibin Sun (Changchun), Wenhui Li Rules-based Spatial Reasoning Combining Topological and Cardinal Directional Relations
Apostolos Syropoulos Fuzzy P Systems: Steps Towards Hypercomputation
Paul Taylor (Manchester) A lambda calculus for real analysis
Sebastiaan Terwijn (Vienna) Kripke models, distributive lattices, and Medvedev degrees
John V Tucker (Swansea), Edwin Beggs (Swansea) Newtonian systems, bounded in space, time, mass and energy can compute all functions
Raymond Turner Computability in Specification
Puzarenko Vadim Computable Principles in admissible structures
Paul J. Voda, Lars Kristiansen Kleene-Kreisel Functionals and Computational Complexity
Andreas Weiermann (Utrecht) A very slow growing hierarchy for the Howard Bachmann ordinal
Philip Welch (Bristol) Arithmetical Quasi-inductive definitions and the transfinite action of 1-tape Turing Machines
Damien Woods (Cork), J. Paul Gibson Complexity of continuous space machine operations
Zheng Xizhong (Cottbus), Robert Rettinger (Hagen) On the Turing Degrees of Divergence Bounded Computable Reals
Konrad Zdanowski (Siedlce), Marcin Mostowski (Warsaw) FM--representabiliy and beyond
Martin Ziegler Computability and Continuity on the Real Arithmetic Hierarchy
Paola Zizzi Computability at the Planck scale
Jeffery Zucker (Hamilton), John V Tucker (Swansea) A network model of analogue computation over metric algebras

P.014 P.017 P.019 P.018 P.227
June 8th
16:50-17:10 Terwijn Gutiérrez-Naranjo
et al.
Durand-Losé Solon
17:10-17:30 Voda
et al.
June 9th
12:00-12:20 Pheidas
Kieu Middelburg
Grolmusz Stukachev
12:20-12:40 Turner Kendon
Nagy Vadim
June 11th
11:10-11:30 Baaz
Finkel Costa
Collins Soskova
11:30-11:50 J Berger Koepke Tucker
Lambov Xizhong
11:50-12:10 Crosilla
Welch Woods
Ziegler Soskov
12:10-12:30 Jacobe de Naurois
et al.
Meer Zdanowski
12:30-12:50 Nikolova
Taylor Skordev
June 11th
15:50-16:10 Khanban
et al.
Weiermann Mitrana
et al.
Balcazar Harris
16:10-16:30 Boker
Jervell Michalak
et al.
et al.
16:30-16:50 Kristiansen
June 12th
11:00-11:20 Manning
Minari Goldin
11:20-11:40 Jervell Barra
Mostowski Hirowatari
et al.
11:40-12:00 Lambov Barmpalias