Editors:
- 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)
Buy it now
Buying options
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 (43 chapters)
-
Front Matter
-
Memories, Complexity and Horizons
-
Front Matter
-
-
Computable Combinatorics, Reverse Mathematics
-
Front Matter
-
-
Computable Model Theory, Computable Algebra
-
Front Matter
-
About this book
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.
Keywords
- algorithmic randomness
- computability theory
- generic-case complexity
- parameterized complexity
- Turing degrees
- chains/antichains
- computable algebra
- computable combinatorics
- computable model theory
- computably enumerable sets
- degree spectra
- enumeration reducibility
- finite state
- generic computability
- induction
- information lossless compressors
- injection structures
- Lempel-Ziv compression algorithm
- matroid
- reverse mathematics
- algorithm analysis and problem complexity
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
Book Title: Computability and Complexity
Book Subtitle: Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday
Editors: Adam Day, Michael Fellows, Noam Greenberg, Bakhadyr Khoussainov, Alexander Melnikov, Frances Rosamond
Series Title: Lecture Notes in Computer Science
DOI: https://doi.org/10.1007/978-3-319-50062-1
Publisher: Springer Cham
eBook Packages: Computer Science, Computer Science (R0)
Copyright Information: Springer International Publishing AG 2017
Softcover ISBN: 978-3-319-50061-4Published: 06 December 2016
eBook ISBN: 978-3-319-50062-1Published: 30 November 2016
Series ISSN: 0302-9743
Series E-ISSN: 1611-3349
Edition Number: 1
Number of Pages: XLII, 755
Number of Illustrations: 22 b/w illustrations
Topics: Algorithm Analysis and Problem Complexity, Computation by Abstract Devices, Data Structures, Discrete Mathematics in Computer Science, Mathematical Logic and Formal Languages, Logics and Meanings of Programs