Computation and Logic in the Real World: Third Conference on Computability in Europe, CiE 2007, Siena, Italy, June 18-23, 2007. Proceedings

Front Matter....Pages -
Shifting and Lifting of Cellular Automata....Pages 1-10
Learning as Data Compression....Pages 11-24
Reachability Problems: An Update....Pages 25-27
RZ: A Tool for Bringing Constructive and Computable Mathematics Closer to Programming Practice....Pages 28-42
Producer/Consumer in Membrane Systems and Petri Nets....Pages 43-52
A Minimal Pair in the Quotient Structure M / NCup ....Pages 53-62
Constructive Dimension and Weak Truth-Table Degrees....Pages 63-72
A Classification of Viruses Through Recursion Theorems....Pages 73-82
Borel Complexity of Topological Operations on Computable Metric Spaces....Pages 83-97
Colocatedness and Lebesgue Integrability....Pages 98-104
Computing with Genetic Gates....Pages 105-114
Resource Restricted Computability Theoretic Learning: Illustrative Topics and Problems....Pages 115-124
Characterizing Programming Systems Allowing Program Self-reference....Pages 125-134
K -Trivial Closed Sets and Continuous Functions....Pages 135-145
Pseudojump Operators and $\Pi^0_1$ Classes....Pages 146-151
Sofic Trace Subshift of a Cellular Automaton....Pages 152-161
Thin Maximal Antichains in the Turing Degrees....Pages 162-168
Effective Computation for Nonlinear Systems....Pages 169-178
On Rules and Parameter Free Systems in Bounded Arithmetic....Pages 179-188
The New Promise of Analog Computation....Pages 189-195
Comparing C.E. Sets Based on Their Settling Times....Pages 196-204
Time-Complexity Semantics for Feasible Affine Recursions....Pages 205-217
Algebraic Model of an Arithmetic Unit for TTE-Computable Normalized Rational Numbers....Pages 218-227
Feasible Depth....Pages 228-237
Abstract Geometrical Computation and the Linear Blum, Shub and Smale Model....Pages 238-247
A Continuous Derivative for Real-Valued Functions....Pages 248-257
Refocusing Generalised Normalisation....Pages 258-267
The Complexity Ecology of Parameters: An Illustration Using Bounded Max Leaf Number....Pages 268-277
Parameterized Complexity and Logic....Pages 278-289
Index Sets of Computable Structures with Decidable Theories....Pages 290-296
Minimal Representations for Majority Games....Pages 297-306
Linear Transformations in Boolean Complexity Theory....Pages 307-315
Exact Pair Theorem for the ω -Enumeration Degrees....Pages 316-324
Operational Semantics for Positive Relevant Logics Without Distribution....Pages 325-335
Multi-valued Logics, Effectiveness and Domains....Pages 336-347
Internal Computability....Pages 348-357
Post’s Problem for Ordinal Register Machines....Pages 358-367
Unique Existence and Computability in Constructive Reverse Mathematics....Pages 368-377
Input-Dependence in Function-Learning....Pages 378-388
Some Notes on Degree Spectra of the Structures....Pages 389-397
Confluence of Cut-Elimination Procedures for the Intuitionistic Sequent Calculus....Pages 398-407
The Polynomial and Linear Hierarchies in V 0 ....Pages 408-415
The Uniformity Principle for Σ -Definability with Applications to Computable Analysis....Pages 416-425
Circuit Complexity of Regular Languages....Pages 426-435
Definability in the Homomorphic Quasiorder of Finite Labeled Forests....Pages 436-445
Physics and Computation: The Status of Landauer’s Principle....Pages 446-454
Strict Self-assembly of Discrete Sierpinski Triangles....Pages 455-464
Binary Trees and (Maximal) Order Types....Pages 465-473
A Weakly 2-Random Set That Is Not Generalized Low....Pages 474-477
Speed-Up Theorems in Type-2 Computation....Pages 478-487
The Complexity of Quickly ORM-Decidable Sets....Pages 488-496
On Accepting Networks of Splicing Processors of Size 3....Pages 497-506
Liquid Computing....Pages 507-516
Quotients over Minimal Type Theory....Pages 517-531
Hairpin Completion Versus Hairpin Reduction....Pages 532-541
Hierarchies in Fragments of Monadic Strict NP ....Pages 542-550
Membrane Systems and Their Application to Systems Biology....Pages 551-553
Some Aspects of a Complexity Theory for Continuous Time Systems....Pages 554-565
Enumerations and Torsion Free Abelian Groups....Pages 566-574
Locally Computable Structures....Pages 575-584
Logic and Control....Pages 585-597
Nash Stability in Additively Separable Hedonic Games Is NP-Hard....Pages 598-605
Comparing Notions of Computational Entropy....Pages 606-620
From Logic to Physics: How the Meaning of Computation Changed over Time....Pages 621-631
Theories and Ordinals: Ordinal Analysis....Pages 632-637
Computable Riemann Surfaces....Pages 638-647
Rank Lower Bounds for the Sherali-Adams Operator....Pages 648-659
Infinite Computations and a Hierarchy in Δ 3 ....Pages 660-669
Natural Computing: A Natural and Timely Trend for Natural Sciences and Science of Computation....Pages 670-671
Biochemical Reactions as Computations....Pages 672-673
Doing Without Turing Machines: Constructivism and Formal Topology....Pages 674-675
Problems as Solutions....Pages 676-684
A Useful Undecidable Theory....Pages 685-694
On the Computational Power of Flip-Flop Proteins on Membranes....Pages 695-704
Computability and Incomputability....Pages 705-715
A Jump Inversion Theorem for the Degree Spectra....Pages 716-726
Cupping $\Delta_2^0$ Enumeration Degrees to 0 e ′....Pages 727-738
What Is the Lesson of Quantum Computing?....Pages 739-741
Does the Cell Compute?....Pages 742-747
Computational Complexity of Constraint Satisfaction....Pages 748-757
Finding Most Likely Solutions....Pages 758-767
Turing Unbound: Transfinite Computation....Pages 768-780
Computability in Amorphous Structures....Pages 781-790
The Complexity of Small Universal Turing Machines....Pages 791-798
Approximating Generalized Multicut on Trees....Pages 799-808
(Short) Survey of Real Hypercomputation....Pages 809-824
Characterizing Programming Systems Allowing Program Self-reference....Pages E1-E1
Back Matter....Pages -