The following papers have been accepted for presentation at CiE 2010. Some of them have been accepted for publication in the pre-proceedings volume published in the Springer Lecture Notes in Computer Science series, the others will be published in our abstract and handout booklet. All authors of papers presented at CiE 2010 may be invited to submit papers to one of the post-conference publications.

Author (s) | Title | |
---|---|---|

Eric Allender | Avoiding Simplicity is Complex | LNCS |

Mikhail Andreev, Ilya Razenshteyn and Alexander Shen | Not Every Domain of a Plain Decompressor Contains the Domain of a Prefix-Free One | Booklet |

Anderson de Araújo | Nonstandard Models of Peano Arithmetic and Turing Computability | Booklet |

Thorsten Altenkirch, Paul Levy and Sam Staton | Higher Order Containers | LNCS |

Bogdan Aman and Gabriel Ciobanu | Verifying Behavioural Properties of Membrane Systems with Delays via Timed Colored Petri Nets | Booklet |

Mauricio Ayala-Rincon and Flavio de Moura | Formalization of Security Proofs Using PVS in the Dolev-Yao Model | Booklet |

Mathias Barra and Philipp Gerhardy | The ordinal of Skolem + Tetration is τ_{0} |
LNCS |

Bruno Bauwens | m-sophistication | Booklet |

Hannah Bast | The CompleteSearch engine - Basics and recent developments | Booklet |

Edwin Beggs, José Félix Costa and John Tucker | Comparing complexity classes relative to physical oracles | Booklet |

Laurent Bienvenu, Frank Stephan and Jason Teutsch | How powerful are integer-valued martingales? | LNCS |

Laurent Bienvenu, Adam Day, Ilya Mezhirov and Alexander Shen | Ergodic-type characterizations of algorithmic randomness | LNCS |

Guillaume Blin, Romeo Rizzi and Stéphane Vialette | A faster algorithm for finding minimum Tucker submatrices | LNCS |

Cristian S. Calude, Kai Salomaa and Tania K. Roblot | Finite-State Complexity and Randomness | Booklet |

Luca Cardelli and Philippa Gardner | Processes in Space | LNCS |

Merlin Carl and Peter Koepke | Natural Language in Algorithms and Proofs - an Outline of the Naproche Project | Booklet |

Gregorio de Miguel Casado | Fractional Positional Notation for Exact Rational Arithmetic | Booklet |

Douglas Cenzer, Ali Dashti, Ferit Toska and Sebastian Wyman | Computability of Countable Subshifts | LNCS |

Zoltán Csajbók | Partial Approximative Set Theory | Booklet |

Stefan Dantchev and Barnaby Martin | The limits of tractability in Resolution-based propositional proof systems | LNCS |

Edgar Daylight | The Advent of Recursion in Programming, 1950s – 1960s | Booklet |

Barnaby Dawson | α-computability | Booklet |

Alberto Dennunzio, Enrico Formenti and Michael Weiss | 2D Cellular Automata: dynamics and undecidability | Booklet |

Luis Descalço, Alexandre Madeira and Manuel Martins | Applying Abstract Algebraic Logic to Classical Automata Theory: an exercise | Booklet |

Debora Donato | Graph Structures and Algorithms for Query-Log Analysis | LNCS |

Gilles Dowek and Pablo Arrighi | On the completeness of quantum computation models | LNCS |

Dominic Dumrauf and Tim Süß | On the Complexity of Local Search for Weighted Standard Set Problems | LNCS |

Jérôme Durand-Lose | The coordinates of isolated accumulations are exactly computable real numbers | Booklet |

Martin Escardo and Paulo Oliva | Searchable Sets, Dubuc-Penon Compactness, Omniscience Principles, and the Drinker Paradox | Booklet |

Martin Escardo and Paulo Oliva | Computational Interpretations of Analysis via Products of Selection Functions | LNCS |

Martin Escardo and Paulo Oliva | The Peirce Translation and the Double Negation Shift | LNCS |

Santiago Figueira, Denis Hirschfeldt, Joseph S. Miller, Selwyn Ng and André Nies | Counting the changes of random Δ^{0}_{2} sets |
LNCS |

Willem Fouche | Countable dense sets of reals and Kolmogorov complexity | Booklet |

Giuditta Franco and Natasa Jonoska | The power of a single membrane | Booklet |

Michele Friend | Boole: From Calculating Numbers to Calculating Thoughts | LNCS |

Alexander Gavryushkin | Computable Limit Models | Booklet |

Christian Glasser, Christian Reitwießner, Heinz Schmitz and Maximilian Witek | Approximability and Hardness in Multi-Objective Optimization | LNCS |

Hugo Gouveia, Nelma Moreira and Rogério Reis | Small NFAs from Regular Expressions: Some Experimental Results | Booklet |

Ferruccio Guidi | An Efficient Validation Procedure for the Formal System lambda-delta | Booklet |

Kojiro Higuchi | Pw is not a Heyting algebra | LNCS |

John Hitchcock | Lower Bounds for Reducibility to the Kolmogorov Random Strings | LNCS |

Jeannette Janssen | Spatial models for virtual networks | LNCS |

Jeannette Janssen and Nauzer Kalyaniwalla | Comparing tree structures using compression | Booklet |

Natasa Jonoska and Masahico Saito | DNA rearrangements through spatial graphs | LNCS |

Takayuki Kihara | Medvedev and Muchnik degrees of Π^{1}_{0} classes with incomplete c.e. filters |
Booklet |

Bakh Khoussainov and Andrey Morozov | On index sets of some properties of computable algebras | LNCS |

Arist Kojevnikov and Alexander Kulikov | Circuit Complexity and Multiplicative Complexity of Boolean Functions | LNCS |

Ekaterina Komendantskaya, Krysia Broda and Artur d'Avila Garcez | Using Inductive Types for Ensuring Correctness of Neuro-Symbolic Computations | Booklet |

Lars Kristiansen and Bedeho Mender | Two notion of non-determinism and fragments of Gödel's T. | Booklet |

Oleg Kudinov, Victor Selivanov and Lyudmila Yartseva | Definability in the Subword Order | LNCS |

Oleg Kudinov, Victor Selivanov and Anton Zhukov | Undecidability in Weihrauch Degrees | LNCS |

Giuseppe Longo | Incomputability in Physics | LNCS |

Jack H. Lutz and Brad Shutters | Approximate Self-Assembly of the Sierpinski Triangle | LNCS |

Lili Ma, Xin Jiang, Zhanli Zhang, Shaoting Tang and Zhiming Zheng | Hidden metric space: an essential of network modularity | Booklet |

Florin Manea, Carlos Martin-Vide and Victor Mitrana | Hairpin Lengthening | LNCS |

Yuri I. Manin | Infinities in Quantum Field Theory and in Classical Computing: Renormalization Program | LNCS |

Giancarlo Mauri, Alberto Leporati, Antonio Porreca and Claudio Zandron | Computational Complexity Aspects in Membrane Computing | LNCS |

Armando Matos, Andreia Teixeira and André Souto | On the largest monochromatic combinatorial rectangles with an application to Communication Complexity | Booklet |

Alexander Melnikov | On computable ordered abelian groups and fields | LNCS |

Liesbeth De Mol, Maarten Bullynck and Martin Carlé | Haskell before Haskell. Curry's contribution to programming (1946 - 1950) | LNCS |

Fernando Vasconcelos Mendes and Rubens Viana Ramos | Quantum Teleportation of Qudit Gates | Booklet |

Samuel Mimram | Focusing in Asynchronous Games | LNCS |

Benedek Nagy and Peter Battyanyi | DNA-Prolog | Booklet |

Juan Ospina and Mario Velez | Bicategorification of he Baez-Stay Rosseta Stone: Programs = Proofs = Processes= Cobordisms | Booklet |

João Luzeilton de Oliveira and Rubens Viana Ramos | Quantum Algorithm for Finding the Period of a Periodic Function Using asymptotic Quantum Search | Booklet |

Sergey Ospichev | Computable Family of Σ^{-1}_{a}-Sets without Friedberg Numberings |
Booklet |

Jeff Paris and Soroush Rad | A note on the least informative model of a theory | LNCS |

Arno Pauly | The Complexity of Iterated Strategy Elimination | Booklet |

João Pedro Pedroso and Yves Smeers | Equilibria on a Game with Discrete Variables | Booklet |

Olga Pombo | Three roots of Leibniz’s contribution to the Computational Conception of Reason | LNCS |

Giuseppe Primiero | Constructive contextual modal judgments for reasoning from open assumptions | Booklet |

Jan Reimann and Bjørn Kjos-Hanssen | The strength of the Besicovitch-Davies Theorem | LNCS |

Yasubumi Sakakibara | Development of a Bacteria Computer: From in silico finite automata to in vitro and in vivo | LNCS |

Eleonora Riva Sanseverino, Roberto Candela and Giuseppe Fileccia Scimemi | Adaptive continuous Ant Colony Optimization for parameters identification in electrical engineering | Booklet |

Rahul Santhanam | The Complexity of Explicit Constructions | LNCS |

Monika Seisenberger and Ulrich Berger | Proofs, programs, processes | LNCS |

Jian-Jun Shu | Multiple DNA sequence alignment using joint weight matrix | Booklet |

Michiel De Smet and Andreas Weiermann | A miniaturisation of Ramsey's theorem | LNCS |

Boris Solon | Quasi-minimal cover e-degrees for an ideals in the upper semilattice of e-degrees | Booklet |

André Souto and Andreia Teixeira | One-way functions using Kolmogorov complexity | Booklet |

André Souto | Kolmogorov Complexity Cores | LNCS |

Dieter Spreen | Every Δ^{0}_{2}-Set is Natural, up to Turing Equivalence |
LNCS |

Ludwig Staiger and Klaus W. Wagner | There are 49 Kuratowski Lattices | Booklet |

Rebecca Steiner | Computable Fields and Weak Truth-Table Reducibility | LNCS |

Lutz Strassburger | What is the Problem with Proof Nets for Classical Logic? | LNCS |

Trifon Trifonov | Quasi-linear Dialectica extraction | LNCS |

Regina Tukhbatullina | Autostable of Boolean Algebra Bw with Distinguished Automorphism | Booklet |

Sara L. Uckelman | Computing with Concepts, Computing with Numbers: Llull, Leibniz, & Boole | LNCS |

David H. Wolpert | Physical inference of dynamical systems | LNCS |

Guohua Wu and Jiang Liu | Degrees with almost universal cupping property | LNCS |