Models of Computation in Context
7th Conference on Computability in Europe, CiE 2011, Sofia, Bulgaria, June 27 - July 2, 2011, Proceedings
Published on 15. September 2011
XIII, 319 pages
978-3-642-21875-0 (ISBN)
Description
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.
More details
Other editions
Additional editions
Benedikt Löwe | Dag Normann | Ivan Soskov
Models of Computation in Context
7th Conference on Computability in Europe, CiE 2011, Sofia, Bulgaria, June 27 - July 2, 2011, Proceedings
Book
06/2011
Springer
€53.49
Shipment within 7-9 days
Content
- Title Page
- Preface
- Organization
- Table of Contents
- Applying Causality Principles to the Axiomatization of Probabilistic Cellular Automata
- Introduction
- Continuity
- Avoiding Spontaneous Correlations
- Common Cause Principle
- Concluding Definition
- References
- Three Theorems on n-REA Degrees: Proof-Readers and Verifiers
- Introduction
- Basic Conventions and Notions
- Proof of the First Theorem: Proof-Readers
- $m$=2
- $m$=3
- General Case
- Proof of the Second Theorem: Verifiers
- $m$=2
- $m$=3
- General Case
- Proof of the Third Theorem: Proof-Readers again
- References
- A Computational Approach to an Alternative Working Environment for the Constructible Universe
- Infinitary Computations and Fine Structure
- The $F$-hierarchy
- Extension of Embeddings
- A Sample Application: An Approximation Lemma for L
- Hyperings
- Further Plans
- References
- Automatic Learners with Feedback Queries
- Introduction
- Learning with Feedback and Memory Limitations
- Some Illustrative Examples
- Learning with Feedback Queries
- Learning Using a Marked Memory Space
- References
- Splicing Systems: Accepting Versus Generating
- Introduction
- Basic Definitions and Notation
- Computational Power
- Final Remarks
- References
- Effective Categoricity of Injection Structures
- Introduction
- Computably Categorical Structures
- ?02 Categorical Structures
- Conclusions and Future Research
- References
- Consistency and Optimality
- Introduction
- Some Preliminaries
- Diagonalizing over Algorithms
- Algorithms and Arithmetical Theories
- Proof of Theorem 1
- References
- Cupping and Diamond Embeddings: A Unifying Approach
- Introduction
- Requirements
- Strategies
- A G-Strategy
- An N-Strategy
- An R-Strategy
- The Interaction between one R-Strategy and one G-Strategy
- Interactions between one R-strategy and two G-strategies
- Interaction between N-Strategies and R-Strategies
- References
- On the Kolmogorov Complexity of Continuous Real Functions
- Introduction
- Kolmogorov Complexity of a Continuous Real Function
- Invariant Ideals
- Prevalence and Shyness
- Main Theorem
- An Asymptotic Bound on the Kolmogorov Complexities of Computable Functions
- Summary and Discussion
- Future Work
- References
- Defining Languages by Forbidding-Enforcing Systems
- Introduction
- Forbidding-Enforcing Systems
- Forbidding Systems, $f$-languages
- Enforcing Systems, $e$-languages
- Forbidding-Enforcing Systems, fe-languages
- Basic Properties of Forbidding-Enforcing Systems
- Relationship between $f$-families and $f$-languages
- Characterizing Formal Languages by Forbidding-Enforcing Systems
- Forbidding through Enforcing
- $k$-colorability Problem
- Modeling Splicing
- Concluding Remarks
- References
- Axiomatizing Resource Bounds for Measure
- Introduction
- Preliminaries
- Type-2 Functionals
- Resource Bounds
- Adequacy for Measure
- References
- Complexity Issues for Preorders on Finite Labeled Forests
- Introduction
- Preliminaries
- TheComplexityof =0
- TheComplexityof =1
- TheComplexityof =2
- Some Open Questions
- References
- Randomness and the Ergodic Decomposition
- Introduction
- Preliminaries
- Effective Randomness
- Randomness and Continuous Combination of Measures
- Randomness and Ergodic Decomposition
- Background from Ergodic Theory
- Randomness and Ergodic Theorems
- First Answer: Effective Decomposition
- V'yugin's Example
- A Particular Case: Effective Compact Classes of Ergodic Measures
- A Weaker Answer: Finitely Decomposable Measures
- References
- Computability of the Radon-Nikodym Derivative
- Introduction
- Preliminaries
- Little bit of Computability via Representations
- Computable Measurable Spaces
- Effective Radon-Nikodym Theorem
- An Upper Bound
- Locating the Non-computability
- References
- Extracting Winning Strategies in Update Games
- Introduction
- Preliminaries
- Update Games and their Basic Properties
- Contraction and Unfolding Operators
- Extracting Winning Strategies
- Update Games with a Fixed Number of Nondeterministic Nodes
- References
- A Generalised Dynamical System, Infinite Time Register Machines, and $?11-CA0$
- References
- Computability Power of Mobility in Enhanced Mobile Membranes
- Introduction
- Enhanced Mobile Membranes
- Computability Power of Mobility
- References
- Nature-Based Problems in Cellular Automata
- Introduction
- Cellular Automata
- French Flag Problem
- Synchronization of Growing Cellular Automata
- Oblivious Cellular Automata
- The Fault-Tolerant Early Bird Problem
- References
- Multi-Resolution Cellular Automata for Real Computation
- Introduction
- Real Computation and Small Boundaries
- Multi-Resolution Cellular Automata
- MRCA Characterization of Computability
- Conclusion
- References
- Deciding According to the Shortest Computations
- Preliminaries
- Shortest Computations
- The First Shortest Computation
- Conclusions and Further Work
- References
- Computation of Similarity-Similarity Search as Computation
- Introduction and Road Map
- Similarity Search in Natural Language Processing
- Speech Recognition
- Statistical Machine Translation
- Text Correction
- Interpreting Historical Texts
- Approximate Search Methods
- Approximate Search in Large Lexica
- Viterbi Search in Huge HMMs
- Synthesis
- Some Experimental Results
- Conclusion
- References
- Adapting Rabin's Theorem for Differential Fields
- Introduction
- Computable Differential Fields
- Constraints
- Decidability in the Constraint Set
- Decidability in the Rabin Image
- References
- Quantum Information Channels in Curved Spacetime
- Quantum Communication in Rindler Spacetime
- Quantum Capacity and Private Quantum Capacity
- Private Quantum Capacity: General Case
- Capacity Results
- Where Do We Go from Here?
- References
- Recognizing Synchronizing Automata with Finitely Many Minimal Synchronizing Words is PSPACE-Complete
- Preliminaries
- PSPACE-Completeness of FINITENESS
- References
- Consecutive Ones Property Testing: Cut or Swap
- Introduction
- Computing Overlap Classes
- Swap Overlap Order
- Partitioning Each Overlap Class
- References
- Current Developments on Computational Modeling Using P Systems
- References
- Automata on Ordinals and Linear Orders
- Introduction
- Ordinals
- Linear Orders
- References
- A Fine Hierarchy of ?-Regular $k$-Partitions
- Introduction
- Preliminaries
- Labeled Trees and Forests
- Fine Hierarchy of k-Partitions
- Operations on k-Partitions
- Main Results
- References
- On a Relative Computability Notion for Real Functions
- Introduction
- F-Substitutional Mappings
- Conditional F-Computability of Real Functions
- Substitution in Conditionally F-Computable Real Functions
- LocalUniformF-Computability of the Conditionally F-Computable Functions
- UniformF-Computability of the Locally Uniformly F-Computable Functions with Compact Domains
- References
- Towards an Axiomatic System for Kolmogorov Complexity
- Introduction
- Plain Complexity
- Weakening the Hypotheses
- An Axiomatic System for Prefix Complexity
- References
- A New Optimum-Time Firing Squad Synchronization Algorithm for Two-Dimensional Rectangle Arrays: One-Sided Recursive Halving Based
- Introduction
- Firing Squad Synchronization Problem on Two-Dimensional Arrays
- One-Sided Recursive Halving Mark
- A New Two-Dimensional Optimum-Time Synchro-nization Algorithm
- Overview of the Algorithm
- Applying the Wider-Than-Long Column Synchronization Algorithm to Rectangles Longer than Wide
- Synchronization of Rectangle Longer than Wide
- Stopping of Undesirable Synchronization Operations
- Final Algorithm
- Conclusions
- References
- Conservative Extensions of Abstract Structures
- Introduction
- Conservative Extensions
- Moschovakis' Extension
- The set $KAn$
- Applications
- Degree Spectra of Structures
- Jumps of Structures
- Marker's Extensions
- References
- On a Hierarchy of Plus-Cupping Degrees
- Introduction
- Proof of Theorem 1
- Strategy for $Pe$
- Strategy for $Re$
- Strategy for $Se,i$
- Strategy for $Qe$
- Strategy for $Te,i$
- More Interactions
- References
- Author Index
