| Description |
1 online resource (xiv, 510 pages) : illustrations |
| Series |
Lecture notes in computer science, 0302-9743 ; 5635 |
|
LNCS sublibrary: SL 1 - Theoretical computer science and general issues |
|
Lecture notes in computer science ; 5635.
|
|
LNCS sublibrary. SL 1, Theoretical computer science and general issues.
|
| Contents |
First-order universality for real programs / Thomas Anberrée -- Skolem + tetration is well-ordered / Mathias Barra and Philipp Gerhardy -- Structures of some strong reducibilities / David R. Bélanger -- Complexity of existential positive first-order logic / Manuel Bodirsky, Miki Hermann, and Florian Richoux -- Stochastic programs and hybrid automata for (biological) modeling / Luca Bortolussi and Alberto Policriti -- Numberings and randomness / Paul Brodhead and Bjørn Kjos-Hanssen -- The strength of the Grätzer-Schmidt theorem / Paul Brodhead and Bjørn Kjos-Hanssen -- Hyperloops do not threaten the notion of an effective procedure / Tim Button -- Minimum entropy combinatorial optimization problems / Jean Cardinal, Samuel Fiorini, and Gwenaël Joret -- Program self-reference in constructive Scott subdomains / John Case and Samuel E. Moelius III -- [capital Greek]Sigma⁰₁ and [capital Greek]Pi⁰₁ equivalence structures / Douglas Cenzer, Valentina Harizanov, and Jeffrey B. Remmel -- Immunity for closed sets / Douglas Cenzer, Rebecca Weber, and Guohua Wu -- Lower bounds for kernelizations and other preprocessing procedures / Yijia Chen, Jörg Flum, and Moritz Müller -- Infinite-time Turing machines and Borel reducibility / Samuel Coskey -- Cutting planes and the parameter cutwidth / Stefan Dantchev and Barnaby Martin -- Members of random closed sets / David Diamondstone and Bjørn Kjos-Hanssen -- Lowness for Demuth randomness / Rod Downey and Keng Meng Ng -- |
|
Graph states and the necessity of Euler decomposition / Ross Duncan and Simon Perdrix -- On stateless multicounter machines / Ömer Eğecioğlu and Oscar H. Ibarra -- Computability of continuous solutions of higher-type equations / Martín Escardó -- Equivalence relations on classes of computable structures / Ekaterina B. Fokina and Sy-David Friedman -- Fractals generated by algorithmically random Brownian motion / Willem L. Fouché -- Computable exchangeable sequences have computable de Finetti measures / Cameron E. Freer and Daniel M. Roy -- Spectra of algebraic fields and subfields / Andrey Frolov, Iskander Kalimullin, and Russell Miller -- Definability in the local theory of the [lowercase Greek]Omega-enumeration degrees / Hristo Ganchev -- Computability of analytic functions with analytic machines / Tobias Gärtner and Günter Hotz -- An application of Martin-Löf randomness to effective probability theory / Mathieu Hoyrup and Cristóbal Rojas -- Index sets and universal numberings / Sanjay Jain, Frank Stephan, and Jason Teutsch -- Ordinal computability / Peter Koepke -- A Gandy theorem for abstract structures and applications to first-order definability / Oleg V. Kudinov and Victor L. Selivanov -- Constructing new aperiodic self-simulating tile sets / Grégory Lafitte and Michael Weiss -- Relationship between Kanamori-McAloon principle and Paris-Harrington theorem / Gyesik Lee -- The first order theories of the Medvedev and Muchnik lattices / Andrew Lewis, André Nies, and Andrea Sorbi -- Infima of [lowercase italic]d.[lowercase italic]r.[lowercase italic]e. degrees / Jiang Liu, Shengling Wang, and Guohua Wu -- |
|
A divergence formula for randomness and dimension / Jack H. Lutz -- On Ladner's result for a class of real machines with restricted use of constants / Klaus Meer -- 0"-categorical completely decomposable torsion-free Abelian groups / Alexander G. Melnikov -- Notes on the jump of a structure / Antonio Montalbán -- A general representation theorem for probability functions satisfying spectrum exchangeability / J. B. Paris and A. Vencovská -- Stability under strategy switching / Soumya Paul, R. Ramanujam, and Sunil Simon -- Computational heuristics for simplifying a biological model / Ion Petre, Andrzej Mizera, and Ralph-Johan Back -- Functions definable by arithmetic circuits / Ian Pratt-Hartmann and Ivo Düntsch -- Survey on oblivious routing strategies / Harald Räcke -- An approach to the engineering of cellular models based on P systems / Francisco J. Romero-Campero and Natalio Krasnogor -- Decidability of sub-theories of polynomials over a finite field / Alla Sirokofskich -- Chaitin [capital Greek]Omega numbers and halting problems / Kohtaro Tadaki -- Bayesian data integration and enrichment analysis for predicting gene function in malaria / Philip M. R. Tedder, James R. Bradford, Chris J. Needham, Glenn A. McConkey, Andrew J. Bulpitt, and David R. Westhead -- Dialectica interpretation with fine computational control / Trifon Trifonov -- Algorithmic minimal sufficient statistic revisited / Nikolay Vereshchagin -- A computation of the maximal order type of the term ordering on finite multisets / Andreas Weiermann -- On generating independent random strings / Marius Zimand |
| Summary |
This book constitutes the proceedings of the 5th Conference on Computability in Europe, CiE 2009, held in Heidelberg, Germany, during July 19-24, 2009. The 34 papers presented together with 17 invited lectures were carefully reviewed and selected from 100 submissions. The aims of the conference is to advance our theoretical understanding of what can and cannot be computed, by any means of computation. It is the largest international meeting focused on computability theoretic issues |
| Bibliography |
Includes bibliographical references at chapter ends, and index |
| Notes |
Print version record |
| Subject |
Computable functions -- Congresses
|
|
Computational complexity -- Congresses
|
|
Computer science -- Mathematics -- Congresses
|
|
Informatique.
|
|
Computable functions
|
|
Computational complexity
|
|
Computer science -- Mathematics
|
| Genre/Form |
proceedings (reports)
|
|
Conference papers and proceedings
|
|
Conference papers and proceedings.
|
|
Actes de congrès.
|
| Form |
Electronic book
|
| Author |
Ambos-Spies, Klaus. editor.
|
|
Löwe, Benedikt. editor.
|
|
Merkle, Wolfgang. editor.
|
| LC no. |
2009930216 |
| ISBN |
9783642030734 |
|
3642030734 |
|
9788364203077 |
|
836420307X |
|
