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

Luigi Acerbi, Alberto Dennunzio, Enrico Formenti (auth.), S. Barry Cooper, Benedikt Löwe, Andrea Sorbi (eds.)3540730001, 9783540730002

This book constitutes the refereed proceedings of the Third International Conference on Computability in Europe, CiE 2007, held in Sienna, Italy, in June 2007.

The 50 revised full papers presented together with 36 invited papers were carefully reviewed and selected from 167 submissions. Among them are papers corresponding to 12 plenary talks and papers of 8 special sessions entitled doing without turing machines: constructivism and formal topology, approaches to computational learning, real computation, computability and mathematical structure, complexity of algorithms and proofs, logic and new paradigms of computability, computational foundations of physics and biology, as well as a women in computability workshop.

---

Table of contents :
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 –