Models of Computation in Context

Name: Models of Computation in Context | 7th Conference on Computability in Europe, CiE 2011, Sofia, Bulgaria, June 27 - July 2, 2011, Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

7th Conference on Computability in Europe, CiE 2011, Sofia, Bulgaria, June 27 - July 2, 2011, Proceedings

Benedikt Löwe Dag Normann Ivan Soskov Alexandra Soskova(Herausgeber*in)

Springer (Verlag)

Erschienen am 15. September 2011

XIII, 319 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-21875-0 (ISBN)

53,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

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

Systemvoraussetzungen

Als PDF speichern Als Link merken