Skip to main content
SpringerLink
Log in

Computability and Complexity

Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday

  • Book
  • © 2017

Overview

Editors:
  1. Adam Day

    1. Victoria University of Wellington, Wellington, New Zealand

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Michael Fellows

    1. University of Bergen, Bergen, Norway

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Noam Greenberg

    1. Victoria University of Wellington, Wellington, New Zealand

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  4. Bakhadyr Khoussainov

    1. University of Auckland, Auckland, New Zealand

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  5. Alexander Melnikov

    1. Massey University, Auckland, New Zealand

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  6. Frances Rosamond

    1. University of Bergen, Bergen, Norway

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  • Contains papers and laudations that showcase the broad and important scientific, leadership and mentoring contributions made by Rodney Downey
  • Presents original unpublished research
  • Includes several surveys that make the various areas accessible to non-specialists
  • Includes supplementary material: sn.pub/extras

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

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

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

Access this book

Log in via an institution
eBook USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and 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

Licence this eBook for your library

Institutional subscriptions

Table of contents (43 chapters)

  1. Front Matter

    Pages I-XLII
    Download chapter PDF

  2. Memories, Complexity and Horizons

    1. Front Matter

      Pages 1-1
      Download chapter PDF

    2. Cameo of a Consummate Computabilist

      • Robert Goldblatt
      Pages 3-8

    3. Surfing with Rod

      • Michael R. Fellows
      Pages 9-18

    4. Prequel to the Cornell Computer Science Department

      • Anil Nerode
      Pages 19-21

    5. Some Questions in Computable Mathematics

      • Denis R. Hirschfeldt
      Pages 22-55

    6. Introduction to Autoreducibility and Mitoticity

      • Christian Glaßer, Dung T. Nguyen, Alan L. Selman, Maximilian Witek
      Pages 56-78

    7. The Complexity of Complexity

      • Eric Allender
      Pages 79-94

    8. Bounded Pushdown Dimension vs Lempel Ziv Information Density

      • Pilar Albert, Elvira Mayordomo, Philippe Moser
      Pages 95-114

    9. Complexity with Rod

      • Lance Fortnow
      Pages 115-121

    10. On Being Rod’s Graduate Student

      • Keng Meng Ng
      Pages 122-123

  3. Computable Combinatorics, Reverse Mathematics

    1. Front Matter

      Pages 125-125
      Download chapter PDF

    2. Herrmann’s Beautiful Theorem on Computable Partial Orderings

      • Carl G. Jockusch Jr.
      Pages 127-133

    3. Effectiveness of Hindman’s Theorem for Bounded Sums

      • Damir D. Dzhafarov, Carl G. Jockusch Jr., Reed Solomon, Linda Brown Westrick
      Pages 134-142

    4. Reverse Mathematics of Matroids

      • Jeffry L. Hirst, Carl Mummert
      Pages 143-159

    5. Weakly Represented Families in Reverse Mathematics

      • Rupert Hölzl, Dilip Raghavan, Frank Stephan, Jing Zhang
      Pages 160-187

    6. The Vitali Covering Theorem in the Weihrauch Lattice

      • Vasco Brattka, Guido Gherardi, Rupert Hölzl, Arno Pauly
      Pages 188-200

    7. Parallel and Serial Jumps of Weak Weak König’s Lemma

      • Laurent Bienvenu, Rutger Kuyper
      Pages 201-217

  4. Computable Model Theory, Computable Algebra

    1. Front Matter

      Pages 219-219
      Download chapter PDF

    2. Effectively Existentially-Atomic Structures

      • Antonio Montalbán
      Pages 221-237
Back to top

Keywords

About this book

This Festschrift is published in honor of Rodney G. Downey, eminent logician and computer scientist, surfer and Scottish country dancer, on the occasion of his 60th birthday.


The Festschrift contains papers and laudations that showcase the broad and important scientific, leadership and mentoring contributions made by Rod during his distinguished career. The volume contains 42 papers presenting original unpublished research, or expository and survey results in Turing degrees, computably enumerable sets, computable algebra, computable model theory, algorithmic randomness, reverse mathematics, and parameterized complexity, all areas in which Rod Downey has had significant interests and influence. The volume contains several surveys that make the various areas accessible to non-specialists while also including some proofs that illustrate the flavor of the fields.

Editors and Affiliations

  • Victoria University of Wellington, Wellington, New Zealand

    Adam Day, Noam Greenberg

  • University of Bergen, Bergen, Norway

    Michael Fellows, Frances Rosamond

  • University of Auckland, Auckland, New Zealand

    Bakhadyr Khoussainov

  • Massey University, Auckland, New Zealand

    Alexander Melnikov

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation