Ferreira / Löwe / Mayordomo Programs, Proofs, Processes

6th Conference on Computability in Europe, CiE, 2010, Ponta Delgada, Azores, Portugal, June 30 - July 4, 2010, Proceedings
Erscheinungsjahr 2010
ISBN: 978-3-642-13962-8
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, Band 6158, 450 Seiten, eBook

Reihe: Lecture Notes in Computer Science

Zielgruppe

Research

Autoren/Hrsg.

Ferreira, Fernando

Löwe, Benedikt

Mayordomo, Elvira

Gomes, Luís Mendes

Inhaltsverzeichnis

Avoiding Simplicity Is Complex.- Higher-Order Containers.- On the Completeness of Quantum Computation Models.- The Ordinal of Skolem + Tetration Is ? 0.- Proofs, Programs, Processes.- Ergodic-Type Characterizations of Algorithmic Randomness.- How Powerful Are Integer-Valued Martingales?.- A Faster Algorithm for Finding Minimum Tucker Submatrices.- Processes in Space.- Computability of Countable Subshifts.- The Limits of Tractability in Resolution-Based Propositional Proof Systems.- Haskell before Haskell: Curry’s Contribution to Programming (1946–1950).- A Miniaturisation of Ramsey’s Theorem.- Graph Structures and Algorithms for Query-Log Analysis.- On the Complexity of Local Search for Weighted Standard Set Problems.- Computational Interpretations of Analysis via Products of Selection Functions.- The Peirce Translation and the Double Negation Shift.- Counting the Changes of Random Sets.- Boole: From Calculating Numbers to Calculating Thoughts.- Approximability and Hardness in Multi-objective Optimization.- Is Not a Heyting Algebra.- Lower Bounds for Reducibility to the Kolmogorov Random Strings.- Spatial Models for Virtual Networks.- DNA Rearrangements through Spatial Graphs.- On Index Sets of Some Properties of Computable Algebras.- The Strength of the Besicovitch-Davies Theorem.- Circuit Complexity and Multiplicative Complexity of Boolean Functions.- Definability in the Subword Order.- Undecidability in Weihrauch Degrees.- Degrees with Almost Universal Cupping Property.- Incomputability in Physics.- Approximate Self-assembly of the Sierpinski Triangle.- Hairpin Lengthening.- Infinities in Quantum Field Theory and in Classical Computing: Renormalization Program.- Computational Complexity Aspects in Membrane Computing.- Computable Ordered AbelianGroups and Fields.- Focusing in Asynchronous Games.- A Note on the Least Informative Model of a Theory.- Three Roots for Leibniz’s Contribution to the Computational Conception of Reason.- Development of a Bacteria Computer: From in silico Finite Automata to in vitro and in vivo.- The Complexity of Explicit Constructions.- Kolmogorov Complexity Cores.- Every -Set Is Natural, Up to Turing Equivalence.- Computable Fields and Weak Truth-Table Reducibility.- What Is the Problem with Proof Nets for Classical Logic?.- Quasi-linear Dialectica Extraction.- Computing with Concepts, Computing with Numbers: Llull, Leibniz, and Boole.- Inference Concerning Physical Systems.