Models of Computation in Context: 7th Conference on Computability in Europe, CiE 2011, Sofia, Bulgaria, June 27 - July 2, 2011. Proceedings

Front Matter....Pages -
Applying Causality Principles to the Axiomatization of Probabilistic Cellular Automata....Pages 1-10
Three Theorems on n -REA Degrees: Proof-Readers and Verifiers....Pages 11-20
A Computational Approach to an Alternative Working Environment for the Constructible Universe....Pages 21-30
Automatic Learners with Feedback Queries....Pages 31-40
Splicing Systems: Accepting Versus Generating....Pages 41-50
Effective Categoricity of Injection Structures....Pages 51-60
Consistency and Optimality....Pages 61-70
Cupping and Diamond Embeddings: A Unifying Approach....Pages 71-80
On the Kolmogorov Complexity of Continuous Real Functions....Pages 81-91
Defining Languages by Forbidding-Enforcing Systems....Pages 92-101
Axiomatizing Resource Bounds for Measure....Pages 102-111
Complexity Issues for Preorders on Finite Labeled Forests....Pages 112-121
Randomness and the Ergodic Decomposition....Pages 122-131
Computability of the Radon-Nikodym Derivative....Pages 132-141
Extracting Winning Strategies in Update Games....Pages 142-151
A Generalised Dynamical System, Infinite Time Register Machines, and $\\Pi^1_1$ -CA 0 ....Pages 152-159
Computability Power of Mobility in Enhanced Mobile Membranes....Pages 160-170
Nature-Based Problems in Cellular Automata....Pages 171-180
Multi-Resolution Cellular Automata for Real Computation....Pages 181-190
Deciding According to the Shortest Computations....Pages 191-200
Computation of Similarity—Similarity Search as Computation....Pages 201-210
Adapting Rabin’s Theorem for Differential Fields....Pages 211-220
Quantum Information Channels in Curved Spacetime....Pages 221-229
Recognizing Synchronizing Automata with Finitely Many Minimal Synchronizing Words is PSPACE-Complete....Pages 230-238
Consecutive Ones Property Testing: Cut or Swap....Pages 239-249
Current Developments on Computational Modeling Using P Systems....Pages 250-251
Automata on Ordinals and Linear Orders....Pages 252-259
A Fine Hierarchy of ω -Regular k -Partitions....Pages 260-269
On a Relative Computability Notion for Real Functions....Pages 270-279
Towards an Axiomatic System for Kolmogorov Complexity....Pages 280-289
A New Optimum-Time Firing Squad Synchronization Algorithm for Two-Dimensional Rectangle Arrays: One-Sided Recursive Halving Based....Pages 290-299
Conservative Extensions of Abstract Structures....Pages 300-309
On a Hierarchy of Plus-Cupping Degrees....Pages 310-318
Back Matter....Pages -