Computability and Complexity : Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday / edited by Adam Day, Michael Fellows, Noam Greenberg, Bakhadyr Khoussainov, Alexander Melnikov, Frances Rosamond.

Format:

Book

Contributor:

Day, Adam (Adam R.), editor.

Fellows, M. R. (Michael Ralph), 1952- editor.

Greenberg, Noam, editor.

Khoussainov, Bakhadyr, 1961- editor.

Melnikov, Alexander, editor.

Rosamond, Frances, editor.

SpringerLink (Online service)

Series:

Computer Science (Springer-11645)

LNCS sublibrary. Theoretical computer science and general issues ; SL 1, 10010.

Theoretical Computer Science and General Issues ; 10010

Language:

English

Subjects (All):

Algorithms.

Computers.

Data structures (Computer science).

Computer science--Mathematics.

Computer science.

Logic, Symbolic and mathematical.

Computer logic.

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.

Local Subjects:

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.

Physical Description:

1 online resource (XLII, 755 pages) : 22 illustrations.

Edition:

First edition 2017.

Contained In:

Springer eBooks

Place of Publication:

Cham : Springer International Publishing : Imprint: Springer, 2017.

System Details:

text file PDF

Summary:

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.

Contents:

Cameo of a Consummate Computabilist

Surfing with Rod

Prequel to the Cornell Computer Science Department

Some Questions in Computable Mathematics

Introduction to Autoreducibility and Mitoticity

The Complexity of Complexity

Bounded Pushdown Dimension vs Lempel Ziv Information Density

On Being Rod's Graduate Student

Herrmann's Beautiful Theorem on Computable Partial Orderings

Effectiveness of Hindman's Theorem for Bounded Sums

Reverse Mathematics of Matroids

Weakly Represented Families in Reverse Mathematics

The Vitali Covering Theorem in the Weihrauch Lattice

Parallel and Serial Jumps of Weak König's Lemma

Effectively Existentially-Atomic Structures

Irreducibles and Primes in Computable Integral Domains

Revisiting Uniform Computable Categoricity: For the Sixtieth Birthday of Prof. Rod Downey

Enumeration Reducibility and Computable Structure Theory

Strength and Weakness in Computable Structure Theory

On Constructive Nilpotent Groups

Computable Model Theory over the Reals

The Lattice of Computably Enumerable Vector Spaces

Injection Structures Specified by Finite State Transducers

A Survey on Universal Computably Enumerable Equivalence Relations

Higher Computability

Σ1 1 in Every Real in a Σ1 1 Class of Reals is Σ1

A Survey of Results on the D-C.E. and N-C.E. Degrees

There Are no Maximal D.C.E. WTT-Degrees

A Rigid Cone in the Truth-Table Degrees with Jump

Asymptotic Density and the Theory of Computability : A Partial Survey

On Splits of Computably Enumerable Sets

1-Generic Degrees Bounding Minimal Degrees Revisited

Nondensity of Double Bubbles in the D.C.E. Degrees

On the Strongly Bounded Turing Degrees of the Computably Enumerable Sets

Permutations of the Integers Induce Only the Trivial Automorphism of the Turing Degrees

On the Reals which Cannot Be Random

A Note on the Differences of Computably Enumerable Reals

Effective Bi-immunity and Randomness

On Work of Barmpalias and Lewis-Pye: A Derivation on the D.C.E. Reals

Turing Degrees and Muchnik Degrees of Recursively Bounded DNR Functions

Algorithmic Statistics: Forty Years Later

Lowness, Randomness, and Computable Analysis. .

Other Format:

Printed edition:

ISBN:

978-3-319-50062-1

9783319500621

Access Restriction:

Restricted for use by site license.