# Accepted Papers

The following papers have been accepted for presentation at CiE 2011. 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 2011 may be invited to submit papers to one of the post-conference publications.

Please note that Dimiter Skordev and Ivan Georgiev's Slides have been updated on October 5th 2011.

LIST OF PAPERS FOR PUBLICATION IN THE LNCS PRE-PROCEEDINGS VOLUME

• Pablo Arrighi, Renan Fargetton, Vincent Nesme and Eric Thierry.
Applying causality principles to the axiomatization of probabilistic cellular automata Abstract Slides
• Mingzhong Cai.
Three Theorems on $n$-REA Degrees: Proof-readers and Verifiers Abstract Slides
• Merlin Carl.
Computational approach to an alternative 'working environment' for the constructible universe Abstract Slides
• John Case, Sanjay Jain, Yuh Shin Ong, Pavel Semukhin and Frank Stephan.
Automatic Learners with Feedback Queries Abstract Slides
• Juan Castellanos, Victor Mitrana and Eugenio Santos.
Splicing Systems: Accepting versus Generating Abstract Slides
• Douglas Cenzer, Valentina Harizanov and Jeffrey B. Remmel.
Effective Categoricity of Injection Structures Abstract Slides
• Yijia Chen, Jörg Flum and Moritz Müller.
Consistency and Optimality Abstract Slides
• Chengling Fang, Jiang Liu and Guohua Wu.
Cupping and Diamond Embeddings: A Unifying Approach Abstract Slides
• Amin Farjudian.
On the Kolmogorov Complexity of Continuous Real Functions Abstract Slides
• Daniela Genova.
Defining Languages by Forbidding-Enforcing Systems Abstract
• Xiaoyang Gu, Jack Lutz, Satyadev Nandakumar and James Royer.
Axiomatizing Resource Bounds for Measure Abstract Slides
• Peter Hertling and Victor Selivanov.

Complexity Issues for Some Initial Segments of Weihrauch Degrees Abstract Slides
• Mathieu Hoyrup.
Randomness and the ergodic decomposition Abstract Slides
• Mathieu Hoyrup, Cristobal Rojas and Klaus Weihrauch.
Computability of the Radon-Nikodym derivative Abstract Slides
• Imran Khaliq, Bakhadyr Khoussainov and Jiamou Liu.

Extracting Winning Strategies in Update Games Abstract
• Martin Kutrib.

Nature-Based Problems in Cellular Automata Abstract Slides
• James Lathrop, Jack H. Lutz and Brian Patterson.
Multi-Resolution Cellular Automata for Real Computation Abstract Slides
• Florin Manea.
Deciding according to the shortest computations Abstract Slides
• Stoyan Mihov and Klaus Schulz.
Computation of Similarity - Similarity Search as Computation Abstract Slides
• Russell Miller and Alexey Ovchinnikov.

Adapting Rabin's Theorem for Differential Fields Abstract Slides

Quantum Information Channels in Curved Spacetime Abstract Slides
• Mathieu Raffinot.
Consecutive ones property testing: cut or swap Abstract
• Agustín Riscos-Núñez.

Current developments on computational modeling using P systems Abstract Slides
• Emanuele Rodaro and Elena Pribavkina.

PSPACE-completeness for finitely generated synchronizing automata Abstract Slides
• Krishna S and Gabriel Ciobanu.
Computability Power of Mobility in Enhanced Mobile Membranes Abstract
• Victor Selivanov.

Fine Hierarchy of $\omega$-Regular $k$-Partitions Abstract Slides
• Dimiter Skordev and Ivan Georgiev.

On a Relative Computability Notion for Real Functions Abstract Slides
• Antoine Taveneaux.

Towards an axiomatic system for Kolmogorov complexity Abstract Slides
• Hiroshi Umeo.
A New Optimum-Time Firing Squad Synchronization Algorithm for Two-Dimensional Rectangle Arrays Abstract Slides
• Stefan Vatev.
Conservative Extensions of Abstract Structures Abstract Slides
• Shenling Wang and Guohua Wu.

On a Hierarchy of Plus-cupping Degrees Abstract Slides
• Philip Welch and Peter Koepke.
A Generalised Dynamical System, Infinite Time Register Machines and Pi^1_1-Comprehension Abstract Slides

LIST OF PAPERS FOR INCLUSION IN THE BOOKLET

• Jörg Ackermann and Ina Koch.
Network Decomposition in Biology - Computational Challenges Abstract Slides
• Philippe Balbiani.

The word problem in semiconcept algebras Abstract Slides
• Luca Bortolussi and Alberto Policriti.

Comparing expressivity of hybrid automata and stochastic programs. Abstract
• Irina Georgescu.
Expected Utility Operators and Their Possibilistic Covariances Abstract Slides
• Francisco Hernández-Quiroz and Raymundo Morado.

Unbounded effectiveness: Turing's departure from Hilbert's desiderata Abstract Slides
• Takayuki Kihara.

Incomputability of Simply Connected Planar Continua Abstract Slides
• Margarita Korovina and Oleg Kudinov.

Algorithmic Properties of $\Sigma$--definability over Positive Predicate Structures Abstract
• Margarita Korovina and Oleg Kudinov.
A Finite Language for Computable Metric Spaces Abstract
• Roussanka Loukanova.

Generalization of Abstract Syntax in the Grammatical Framework GF Abstract
• Alexandre Madeira, Manuel A. Martins and Luis Barbosa.

Models as arrows: the role of dialgebras Abstract Slides
• Armando Matos, André Souto and Andreia Teixeira.

Distinguishing probability ensembles Abstract Slides
• Sergey Ospichev.

Families with Infinite Rogers Semilattices in Ershov Hierarchy Abstract
• Paul Potgieter.

The Rapid Points of a Complex Oscillation Abstract Slides
• Caroline Rogers.

Quantum Measurements Cannot be Proved to be Random Abstract Slides
• Maxime Senot, Denys Duchier and Jérôme Durand-Lose.

Solving Q-SAT in bounded space and time by geometrical computation Abstract Slides
• Velislava Stoykova.

Representing Nominal Inflectional Morphology for Slavonic Languages in DAlTR Abstract Slides
• Paul Tarau and Brenda Luderman.
Emulating Boolean Computations with Pairing and Unpairing Functions Abstract
• Stijn Vermeeren.

A New Total Injection Betting Strategy Abstract

LIST OF INFORMAL PRESENTATIONS

• Amir Ben-Amram and Lars Kristiansen.

Decidable and Undecidable Problems Related to Complexity Analysis of Loop Programs Abstract Slides
• Angel Ditchev.
Rigidity of the uppersemilattice of the enumeration degrees  Abstract
• Dan Hernest.
Pierce translation in MinLog Abstract
• Gregory Igusa.
Lack of a Minimal Pair for Generic Computability Abstract Slides
• Viv Kendon.
Where to quantum walk? Abstract Slides
• Takayuki Kihara and Kojiro Higuchi.

Mass problems and relative learnability Abstract Slides
• Thorsten Kräling.

The Theories of the Computably Enumerable ibT- and cl-Degrees are not Elementarily Equivalent Abstract Slides
• Alexander Kreuzer.
The Bolzano-Weierstrass principle, the cohesive principle and program extraction Abstract Slides
• Sabine Koppelberg, Ivo Düntsch and Michael Winter.
A remark on the existence of contact relations on Boolean algebras Abstract Slides
• Chung-Chih Li.
Honesty and Time-Constructibility in Type-2 Computation Abstract Slides
• Kyung Il Lee, Charles Harris and Barry Cooper.

Automorphisms of Computable Linear Orders and the Ershov Hierarchy. Abstract Slides
• Andrew Marks.

Universality of recursive isomorphism Abstract Slides
• Kenshi Miyabe.

Characterizing randomness by function tests Abstract Slides
• Pavol Safarik.
A quantitative nonlinear ergodic theorem Abstract Slides
• Michiel De Smet and Andreas Weiermann.

Phase transitions related to the pigeonhole principle Abstract Slides
• Sam Sanders.

Reverse Mathematics and Nonstandard Analysis: Making sense of infinite computations Abstract Slides
• Rebecca M. Steiner.

Orbit relation and Isomorphism Type for Computable Trees Under Predecessor Abstract Slides
• Jason Teutsch.

How to build a warped online casino Abstract
• Trifon Trifonov.

Improving the efficiency of programs extracted via Gödel’s Dialectica interpretation Abstract Slides
• Steven Vandendriessche.

The Complexity of Countable Abelian P-Groups Abstract Slides