Programs, Proofs, Processes : 6th Conference on Computability in Europe, CiE, 2010, Ponta Delgada, Azores, Portugal, June 30 - July 4, 2010, Proceedings

by Ferreira, Fernanda; Lowe, Benedikt; Mayordomo, Elvira; Gomes, Luis Mendes

• ISBN13: 9783642139611
• ISBN10: 3642139612
• Format: Paperback
• Copyright: 2010-07-14
• Publisher: Springer-Verlag New York Inc

Summary

This book constitutes the refereed proceedings of the 6th Conference on Computability in Europe, CiE 2010, held in Ponta Delgada, Azores, Portugal, in June/July 2010. The 28 revised papers presented together with 20 invited lectures were carefully reviewed and selected from 90 submissions. The papers address not only the more established lines of research of computational complexity and the interplay between proofs and computation, but also novel views that rely on physical and biological processes and models to find new ways of tackling computations and improving their efficiency.

Table of Contents

Avoiding Simplicity Is Complex	p. 1
Higher-Order Containers	p. 11
On the Completeness of Quantum Computation Models	p. 21
The Ordinal of Skolem + Tetration Is ¿0	p. 31
Proofs, Programs, Processes	p. 39
Ergodic-Type Characterizations of Algorithmic Randomness	p. 49
How Powerful Are Integer-Valued Martingales?	p. 59
A Faster Algorithm for Finding Minimum Tucker Submatrices	p. 69
Processes in Space	p. 78
Computability of Countable Subshifts	p. 88
The Limits of Tractability in Resolution-Based Propositional Proof Systems	p. 98
Haskell before Haskell: Curry's Contribution to Programming (1946-1950)	p. 108
A Miniaturisation of Ramsey's Theorem	p. 118
Graph Structures and Algorithms for Query-Log Analysis	p. 126
On the Complexity of Local Search for Weighted Standard Set Problems	p. 132
Computational Interpretations of Analysis via Products of Selection Functions	p. 141
The Peirce Translation and the Double Negation Shift	p. 151
Counting the Changes of Random ¿02 Sets	p. 162
Boole: From Calculating Numbers to Calculating Thoughts	p. 172
Approximability and Hardness in Multi-objective Optimization	p. 180
Pw Is Not a Heyting Algebra	p. 190
Lower Bounds for Reducibility to the Kolmogorov Random Strings	p. 195
Spatial Models for Virtual Networks	p. 201
DNA Rearrangements through Spatial Graphs	p. 211
On Index Sets of Some Properties of Computable Algebras	p. 219
The Strength of the Besicovitch-Davies Theorem	p. 229
Circuit Complexity and Multiplicative Complexity of Boolean Functions	p. 239
Definability in the Subword Order	p. 246
Undecidability in Weihrauch Degrees	p. 256
Degrees with Almost Universal Cupping Property	p. 266
Incomputability in Physics	p. 276
Approximate Self-assembly of the Sierpinski Triangle	p. 286
Hairpin Lenthening	p. 296
Infinities in Quantum Field Theory and in Classical Computing: Renormalization Program	p. 307
Computational Complexity Aspects in Membrane Computing	p. 317
Computable Ordered Abelian Groups and Fields	p. 321
Focusing in Asynchronous Games	p. 331
A Note on the Least Informative Model of a Theory	p. 342
Three Roots for Leibniz's Contribution to the Computational Conception of Reason	p. 352
Development of a Bacteria Computer: From in silico Finite Automata to in vitro and in vivo	p. 362
The Complexity of Explicit Constructions	p. 372
Kolmogorov Complexity Cores	p. 376
Every ¿02-Set Is Natural, Up to Turing Equivalence	p. 386
Computable Fields and Weak Truth-Table Reducibility	p. 394
What Is the Problem with Proof Nets for Classical Logic?	p. 406
Quasi-linear Dialectica Extraction	p. 417
Computing with Concepts, Computing with Numbers: Llull, Leibniz, and Boole	p. 427
Inference Concerning Physical Systems	p. 438
Author Index	p. 449
Table of Contents provided by Ingram. All Rights Reserved.