## Models of Computation in Context: 7th Conference on Computability in Europe, CiE 2011, Sofia, Bulgaria, June 27 - July 2, 2011, ProceedingsBenedikt Löwe, Dag Normann, Ivan Soskov, Alexandra Soskova This book constitutes the refereed proceedings of the 7th Conference on Computability in Europe, CiE 2011, held in Sofia, Bulgaria, in June/July 2011. The 22 revised papers presented together with 11 invited lectures were carefully reviewed and selected with an acceptance rate of under 40%. The papers cover the topics computability in analysis, algebra, and geometry; classical computability theory; natural computing; relations between the physical world and formal models of computability; theory of transfinite computations; and computational linguistics. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Applying Causality Principles to the Axiomatization of Probabilistic Cellular Automata | 1 |

ProofReaders and Verifiers | 11 |

A Computational Approach to an Alternative Working Environment for the Constructible Universe | 21 |

Automatic Learners with Feedback Queries | 31 |

Accepting Versus Generating | 41 |

Effective Categoricity of Injection Structures | 51 |

Consistency and Optimality | 61 |

A Unifying Approach | 71 |

MultiResolution Cellular Automata for Real Computation | 181 |

Deciding According to the Shortest Computations | 191 |

Computation of SimilaritySimilarity Search as Computation | 201 |

Adapting Rabins Theorem for Differential Fields | 211 |

Quantum Information Channels in Curved Spacetime | 221 |

Recognizing Synchronizing Automata with Finitely Many Minimal Synchronizing Words is PSPACEComplete | 230 |

Cut or Swap | 239 |

Current Developments on Computational Modeling Using P Systems | 250 |

On the Kolmogorov Complexity of Continuous Real Functions | 81 |

Defining Languages by ForbiddingEnforcing Systems | 92 |

Axiomatizing Resource Bounds for Measure | 102 |

Complexity Issues for Preorders on Finite Labeled Forests | 112 |

Randomness and the Ergodic Decomposition | 122 |

Computability of the RadonNikodym Derivative | 132 |

Extracting Winning Strategies in Update Games | 142 |

A Generalised Dynamical System Infinite Time Register Machines and Π11CA0 | 152 |

Computability Power of Mobility in Enhanced Mobile Membranes | 160 |

NatureBased Problems in Cellular Automata | 171 |

Automata on Ordinals and Linear Orders | 252 |

A Fine Hierarchy of ωRegular kPartitions | 260 |

On a Relative Computability Notion for Real Functions | 270 |

Towards an Axiomatic System for Kolmogorov Complexity | 280 |

OneSided Recursive Halving Based | 290 |

Conservative Extensions of Abstract Structures | 300 |

On a Hierarchy of PlusCupping Degrees | 310 |

319 | |

### Other editions - View all

### Common terms and phrases

algebraic algebraic closure algorithm array automatic learner automaton Berlin Heidelberg 2011 Cantor space cell cellular automata characterization computable function computable injection structure computably isomorphic Computer Science consider construction countable deciding Q0 deﬁned Deﬁnition denote differential field elements enumeration ergodic ergodic measures exists extended F-computable fe-systems finite ﬁrst function f given graph Heidelberg hence infinite initial segment input word isomorphic k-partitions Kolmogorov complexity labeled language Lemma linear LNCS Löwe membrane MRCA natural number nodes notion operator oracle Turing machine orbits of type ordinals overlap class Player polynomial probability measure problem proof properties Proposition prove random map real functions real numbers recursive register machine resource bound result satisﬁed satisfying sequence space splicing systems Springer stage string strong minimal subset symbols synchronization Theorem theory Turing degrees Turing machine update game winning strategy