Skip to main content
  • Conference proceedings
  • © 2009

Mathematical Theory and Computational Practice

5th Conference on Computability in Europe, CiE 2009, Heidelberg, Germany, July 19-24, 2009, Proceedings

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 5635)

Part of the book sub series: Theoretical Computer Science and General Issues (LNTCS)

Conference series link(s): CiE: Conference on Computability in Europe

Conference proceedings info: CiE 2009.

Buy it now

Buying options

eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

This is a preview of subscription content, log in via an institution to check for access.

Table of contents (51 papers)

  1. Front Matter

  2. First-Order Universality for Real Programs

    • Thomas Anberrée
    Pages 1-10
  3. Skolem + Tetration Is Well-Ordered

    • Mathias Barra, Philipp Gerhardy
    Pages 11-20
  4. Structures of Some Strong Reducibilities

    • David R. Bélanger
    Pages 21-30
  5. Complexity of Existential Positive First-Order Logic

    • Manuel Bodirsky, Miki Hermann, Florian Richoux
    Pages 31-36
  6. Stochastic Programs and Hybrid Automata for (Biological) Modeling

    • Luca Bortolussi, Alberto Policriti
    Pages 37-48
  7. Numberings and Randomness

    • Paul Brodhead, Bjørn Kjos-Hanssen
    Pages 49-58
  8. The Strength of the Grätzer-Schmidt Theorem

    • Paul Brodhead, Bjørn Kjos-Hanssen
    Pages 59-67
  9. Minimum Entropy Combinatorial Optimization Problems

    • Jean Cardinal, Samuel Fiorini, Gwenaël Joret
    Pages 79-88
  10. Program Self-reference in Constructive Scott Subdomains

    • John Case, Samuel E. Moelius III
    Pages 89-98
  11. \(\Sigma^0_1\) and \(\Pi^0_1\) Equivalence Structures

    • Douglas Cenzer, Valentina Harizanov, Jeffrey B. Remmel
    Pages 99-108
  12. Immunity for Closed Sets

    • Douglas Cenzer, Rebecca Weber, Guohua Wu
    Pages 109-117
  13. Lower Bounds for Kernelizations and Other Preprocessing Procedures

    • Yijia Chen, Jörg Flum, Moritz Müller
    Pages 118-128
  14. Cutting Planes and the Parameter Cutwidth

    • Stefan Dantchev, Barnaby Martin
    Pages 134-143
  15. Members of Random Closed Sets

    • David Diamondstone, Bjørn Kjos-Hanssen
    Pages 144-153
  16. Lowness for Demuth Randomness

    • Rod Downey, Keng Meng Ng
    Pages 154-166
  17. Graph States and the Necessity of Euler Decomposition

    • Ross Duncan, Simon Perdrix
    Pages 167-177
  18. On Stateless Multicounter Machines

    • Ömer Eğecioğlu, Oscar H. Ibarra
    Pages 178-187

Other Volumes

  1. Mathematical Theory and Computational Practice

About this book

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.

Editors and Affiliations

  • University of Heidelberg, Heidelberg, Germany

    Klaus Ambos-Spies

  • Universiteit van Amsterdam, Amsterdam, The Netherlands

    Benedikt Löwe

  • Institut für Informatik, Ruprecht-Karls-Universität Heidelberg, Heidelberg, Germany

    Wolfgang Merkle

Bibliographic Information

Buy it now

Buying options

eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access