Logical Methods

1. Front Matter

   Pages i-xiv

   PDF

2. The Work of Anil Nerode: A Retrospective

   • J. B. Remmel, J. N. Crossley

   Pages 1-91

3. Embedding Distributive Lattices Preserving 1 below a Nonzero Recursively Enumerable Turing Degree

   • Klaus Ambos-Spies, Ding Decheng, Peter A. Fejer

   Pages 92-129

4. Prime Isols and the Theorems of Fermat and Wilson

   • J. Barback

   Pages 130-142

5. Problem Solving Strategies for the Derivation of Programs

   • Jaime Bohórquez, Rodrigo Cardoso

   Pages 143-161

6. Effective Real Dynamics

   • Douglas Cenzer

   Pages 162-177

7. An integer lattice arising in the model theory of wreath products

   • Gregory Cherlin, Gary Martin

   Pages 178-193

8. Undecidability and Definability for Parametrized Polynomial Time m-Reducibilities

   • Peter Cholak, Rod Downey

   Pages 194-221

9. Extracting programs from proofs by an extension of the Curry-Howard process

   • John N. Crossley, John C. Shepherdson

   Pages 222-288

10. A Bird’s-Eye View of Twilight Combinatorics

    • J. C. E. Dekker

    Pages 289-313

11. Effectively and Noneffectively Nowhere Simple Subspaces

    • R. G. Downey, Jeffrey B. Remmel

    Pages 314-351

12. Index Sets in Recursive Combinatorics

    • William Gasarch, Georgia Martin

    Pages 352-385

13. Computability in Unitary Representations of Compact Groups

    • Xiaolin Ge, J. Ian Richards

    Pages 386-421

14. Recursive Properties of Intervals of Recursive Linear Orders

    • Geoffrey Hird

    Pages 422-437

15. Algorithmic Stability of Models

    • B. M. Khoussainov, R. Dadajanov

    Pages 438-466

16. The Combinatorics of the Friedberg-Muchnick Theorem

    • Kyriakos Kontostathis

    Pages 467-489

17. Partial Automata and Finitely Generated Congruences: An Extension of Nerode’s Theorem

    • D. Kozen

    Pages 490-511

18. Minimal Pair Constructions and Iterated Trees of Strategies

    • S. Lempp, M. Lerman, F. Weber

    Pages 512-554

19. Intuitionistic L

    • Robert S. Lubarsky

    Pages 555-571

20. n-Recursive Linear Orders without (n+1)-Recursive Copies

    • Michael Moses

    Pages 572-592

The twenty-six papers in this volume reflect the wide and still expanding range of Anil Nerode's work. A conference on Logical Methods was held in honor of Nerode's sixtieth birthday (4 June 1992) at the Mathematical Sciences Institute, Cornell University, 1-3 June 1992. Some of the conference papers are here, but others are from students, co-workers and other colleagues. The intention of the conference was to look forward, and to see the directions currently being pursued, in the development of work by, or with, Nerode. Here is a brief summary of the contents of this book. We give a retrospective view of Nerode's work. A number of specific areas are readily discerned: recursive equivalence types, recursive algebra and model theory, the theory of Turing degrees and r.e. sets, polynomial-time computability and computer science. Nerode began with automata theory and has also taken a keen interest in the history of mathematics. All these areas are represented. The one area missing is Nerode's applied mathematical work relating to the environment. Kozen's paper builds on Nerode's early work on automata. Recursive equivalence types are covered by Dekker and Barback, the latter using directly a fundamental metatheorem of Nerode. Recursive algebra is treated by Ge & Richards (group representations). Recursive model theory is the subject of papers by Hird, Moses, and Khoussainov & Dadajanov, while a combinatorial problem in recursive model theory is discussed in Cherlin & Martin's paper. Cenzer presents a paper on recursive dynamics.

• Equivalence
• Problem solving
• algorithm
• algorithms
• automata
• automata theory
• calculus
• combinatorics
• computability
• computer science
• decidability
• logic
• model theory
• proof
• semantics

• Dept. of Mathematics / Comp. Science, Monash University, Clayton, Australia

  John N. Crossley

• Dept. of Mathematics, University of California at San Diego, La Jolla, USA

  Jeffrey B. Remmel

• Mathematical Sciences Institute, Cornell University, Ithaca, USA

  Richard A. Shore, Moss E. Sweedler

Policies and ethics