%% Created for Peter Cholak at 2007-09-27 14:39:39 -0400
%% Saved with string encoding Western (ASCII)
@incollection{MR2185446,
Address = {La Jolla, CA},
Author = {Simpson, Stephen G.},
Booktitle = {Reverse mathematics 2001},
Date-Added = {2007-09-27 13:26:49 -0400},
Date-Modified = {2007-09-27 13:26:49 -0400},
Mrclass = {03F35 (03B30 03D30 03D80)},
Mrnumber = {MR2185446 (2006g:03110)},
Pages = {352--378},
Publisher = {Assoc. Symbol. Logic},
Series = {Lect. Notes Log.},
Title = {{$\Pi\sp 0\sb 1$} sets and models of {$\rm WKL\sb 0$}},
Volume = {21},
Year = {2005}}
@article{MR0071379,
Author = {Myhill, John},
Date-Added = {2007-09-27 12:59:38 -0400},
Date-Modified = {2007-09-27 12:59:38 -0400},
Fjournal = {Zeitschrift f\"ur Mathematische Logik und Grundlagen der Mathematik},
Journal = {Z. Math. Logik Grundlagen Math.},
Mrclass = {02.0X},
Mrnumber = {MR0071379 (17,118g)},
Mrreviewer = {J. C. E. Dekker},
Pages = {97--108},
Title = {Creative sets},
Volume = {1},
Year = {1955}}
@article{MR1640265,
Author = {Harrington, Leo and Soare, Robert I.},
Coden = {APALD7},
Date-Added = {2007-09-27 11:26:09 -0400},
Date-Modified = {2007-09-27 11:26:09 -0400},
Fjournal = {Annals of Pure and Applied Logic},
Issn = {0168-0072},
Journal = {Ann. Pure Appl. Logic},
Mrclass = {03D25},
Mrnumber = {MR1640265 (99f:03055)},
Mrreviewer = {Peter Cholak},
Note = {Conference on Computability Theory (Oberwolfach, 1996)},
Number = {1-3},
Pages = {97--125},
Title = {Definable properties of the computably enumerable sets},
Volume = {94},
Year = {1998}}
@article{MR2210058,
Author = {Binns, Stephen and Kjos-Hanssen, Bj{\o}rn and Lerman, Manuel and Solomon, Reed},
Coden = {JSYLA6},
Date-Added = {2007-09-27 09:17:49 -0400},
Date-Modified = {2007-09-27 09:17:49 -0400},
Fjournal = {The Journal of Symbolic Logic},
Issn = {0022-4812},
Journal = {J. Symbolic Logic},
Mrclass = {03D28 (28A12)},
Mrnumber = {MR2210058 (2006m:03070)},
Mrreviewer = {A. Ku{\v{c}}era},
Number = {1},
Pages = {119--136},
Title = {On a conjecture of {D}obrinen and {S}impson concerning almost everywhere domination},
Volume = {71},
Year = {2006}}
@unpublished{Aharoni.Berger:nd,
Author = {Aharoni, R. and Berger, E.},
Date-Added = {2007-09-27 08:22:09 -0400},
Date-Modified = {2007-09-27 09:05:14 -0400},
Note = {Draft available},
Title = {Menger's theorem for infinite graphs},
Url = {www.math.haifa.ac.il/berger/Menger.ps},
Year = {2006}}
@article{Federson2002,
Author = {Federson, M. and Bianconi, R.},
Date-Added = {2007-09-27 08:22:09 -0400},
Date-Modified = {2007-09-27 08:22:09 -0400},
Journal = {Journal of Applied Analysis},
Local-Url = {file://localhost/Users/swalsh/Documents/Sean/Library/Federson2002.pdf},
Note = {\href{http://www.ams.org/mathscinet-getitem?mr=MR1921473}{MR1921473}. \href{http:/www.emis.de/MATH-item?1043.45010}{Zbl 1043.45010}.},
Number = {1},
Pages = {83-110},
Title = {Linear {F}redholm {I}ntegral {E}quations and the {I}ntegral of {K}urzweil},
Volume = {8},
Year = {2002}}
@unpublished{Hirschfeldt.Jockusch.ea:nd,
Author = {Hirschfeldt, D. and Jockusch, C. and Kjos-Hannssen, B. and Lempp, S. and Slaman, T.},
Date-Added = {2007-09-27 08:22:09 -0400},
Date-Modified = {2007-09-27 08:22:09 -0400},
Note = {To appear in the preceedings of the Program on Computational Prospects of Infinity, Singapore},
Title = {Some Remarks on the Proof-theoretic Strength of Some Combinatorial Principles},
Year = {2005}}
@article{DoughertyKechris1991,
Author = {Dougherty, Randall and Kechris, Alexander S.},
Date-Added = {2007-09-27 08:22:09 -0400},
Date-Modified = {2007-09-27 08:22:09 -0400},
Journal = {Advances in Mathematics},
Keywords = {Mathematics},
Note = {\href{http://www.ams.org/mathscinet-getitem?mr=MR1120611}{MR1120611}. \href{http:/www.emis.de/MATH-item?0739.26005}{Zbl 0739.26005}.},
Number = {2},
Pages = {145-169},
Title = {The {C}omplexity of {A}ntidifferentiation},
Volume = {88},
Year = {1991}}
@unpublished{kjos-hanssen:_low_ness_notion_measur_and_domin,
Author = {B. Kjos-Hanssen and J. Miller and D. Solomon},
Date-Added = {2007-09-27 08:22:09 -0400},
Date-Modified = {2007-09-27 09:19:34 -0400},
Note = {Preprint available from authors},
Title = {Low- ness notions, measure and domination},
Year = {2007}}
@unpublished{LMSV:nd,
Author = {Bienvenu, L. and A. Muchnik and A. Shen and N. Vereshchagin},
Date-Added = {2007-09-27 08:22:09 -0400},
Date-Modified = {2007-09-27 09:05:32 -0400},
Note = {Draft available from authors},
Title = {Limit Complexities Revisited},
Year = {2007}}
@unpublished{Hirschfeldt.Shore:nd,
Author = {Hirschfeldt, Denis R. and Shore, Richard A. and Slaman, T.},
Date-Added = {2007-09-27 08:22:09 -0400},
Date-Modified = {2007-09-27 09:10:35 -0400},
Note = {Draft available from authors},
Title = {The Atomic Model Theorem},
Url = {http://www.math.cornell.edu/~shore/papers/pdf/amtnew5.pdf},
Year = {2007}}
@article{MR2298478,
Author = {Hirschfeldt, Denis R. and Shore, Richard A.},
Coden = {JSYLA6},
Date-Added = {2007-09-27 08:22:09 -0400},
Date-Modified = {2007-09-27 08:22:09 -0400},
Fjournal = {The Journal of Symbolic Logic},
Issn = {0022-4812},
Journal = {J. Symbolic Logic},
Mrclass = {03F35 (03B30)},
Mrnumber = {MR2298478},
Mrreviewer = {Roman Kossak},
Number = {1},
Pages = {171--206},
Title = {Combinatorial principles weaker than {R}amsey's theorem for pairs},
Volume = {72},
Year = {2007}}
@unpublished{Eleftheriou1,
Author = {P. Eleftheriou and S. Starchenko},
Date-Added = {2007-09-27 08:22:09 -0400},
Date-Modified = {2007-09-27 08:22:09 -0400},
Note = {to appear in Journal of Symbolic Logic},
Title = {Groups definable in ordered vector spaces over ordered division rings},
Year = {2007}}
@unpublished{Slaman.Woodin:conjecture,
Author = {Theodore A. Slaman and W. Hugh Woodin},
Date-Added = {2007-09-27 08:22:09 -0400},
Date-Modified = {2007-09-27 14:39:38 -0400},
Note = {Personal communication},
Title = {Slaman-{W}oodin Conjecture},
Year = {1989}}
@unpublished{Avigad:02,
Author = {Avigad, J.},
Date-Added = {2007-09-27 08:22:09 -0400},
Date-Modified = {2007-09-27 08:22:09 -0400},
Note = {Carnegie Mellon Technical Report CMU-PHIL-125},
Title = {Notes on ${\Pi}^1_1$ conservativity, $\omega$-models, and the collection shema},
Url = {http://www.andrew.cmu.edu/user/avigad/Papers/omegasubmodels.pdf},
Year = {2002}}
@incollection{MR1057822,
Address = {Providence, RI},
Author = {Hirst, Jeffry L.},
Booktitle = {Logic and computation (Pittsburgh, PA, 1987)},
Date-Added = {2007-09-27 08:22:09 -0400},
Date-Modified = {2007-09-27 08:22:10 -0400},
Mrclass = {03F35},
Mrnumber = {MR1057822 (91k:03141)},
Mrreviewer = {P. {\v{S}}t{\v{e}}p{\'a}nek},
Pages = {181--196},
Publisher = {Amer. Math. Soc.},
Series = {Contemp. Math.},
Title = {Marriage theorems and reverse mathematics},
Volume = {106},
Year = {1990}}
@article{jockusch:72,
Author = {Jockusch, Jr., Carl G.},
Date-Added = {2007-09-27 08:22:09 -0400},
Date-Modified = {2007-09-27 08:22:10 -0400},
Journal = {J. Symbolic Logic},
Pages = {268--280},
Title = {Ramsey's theorem and recursion theory},
Volume = {37},
Year = {1972}}
@unpublished{kjos-hanssen:_low_for_random_reals_and,
Author = {B. Kjos-Hanssen},
Date-Added = {2007-09-27 08:22:09 -0400},
Date-Modified = {2007-09-27 09:19:26 -0400},
Note = {to appear in Proceedings of the American Mathematical Society,},
Title = {Low for random reals and positive-measure domination},
Year = {2005}}
@book{Kress1999,
Author = {Kress, Rainer},
Date-Added = {2007-09-27 08:22:09 -0400},
Date-Modified = {2007-09-27 08:22:10 -0400},
Edition = {second},
Note = {\href{http://www.ams.org/mathscinet-getitem?mr=MR1723850}{MR1723850}. \href{http:/www.emis.de/MATH-item?0920.45001}{Zbl 0920.45001}.},
Publisher = {Springer},
Series = {Applied Mathematical Sciences},
Title = {Linear {I}ntegral {E}quations},
Volume = {82},
Year = {1999}}
@book{Kurzweil2000,
Address = {Singapore},
Author = {Kurzweil, Jaroslav},
Date-Added = {2007-09-27 08:22:09 -0400},
Date-Modified = {2007-09-27 08:22:10 -0400},
Keywords = {Mathematics},
Note = {\href{http://www.ams.org/mathscinet-getitem?mr=MR1763305}{MR1763305}. \href{http:/www.emis.de/MATH-item?0954.28001}{Zbl 0954.28001}.},
Publisher = {World Scientific},
Series = {Series in Real Analysis},
Title = {Henstock-{K}urzweil {I}ntegration: {I}ts {R}elation to {T}opological {V}ector {S}paces},
Volume = {7},
Year = {2000}}
@phdthesis{Mileti:04,
Author = {J. Mileti},
Date-Added = {2007-09-27 08:22:09 -0400},
Date-Modified = {2007-09-27 08:22:10 -0400},
School = {University of Illinios at Urbana-Champaign},
Title = {Partition Theorems and Computbility Theory},
Year = {2004}}
@unpublished{miller:nd,
Author = {J. Miller},
Date-Added = {2007-09-27 08:22:09 -0400},
Date-Modified = {2007-09-27 09:12:01 -0400},
Note = {Talk at FRG Workshop September 15-19, 2007},
Title = {Extracting information is hard},
Year = {2007}}
@article{miller:01,
Author = {Miller, Russell},
Coden = {JSYLA6},
Date-Added = {2007-09-27 08:22:09 -0400},
Date-Modified = {2007-09-27 08:22:10 -0400},
Fjournal = {The Journal of Symbolic Logic},
Issn = {0022-4812},
Journal = {J. Symbolic Logic},
Mrclass = {03D45},
Mrnumber = {2002e:03065},
Mrreviewer = {Peter Cholak},
Number = {2},
Pages = {470--486},
Title = {The ${\Delta}\sp 0\sb 2$-spectrum of a linear order},
Volume = {66},
Year = {2001}}
@book{Prest1988,
Address = {Cambridge},
Author = {Prest, Mike},
Date-Added = {2007-09-27 08:22:09 -0400},
Date-Modified = {2007-09-27 08:22:10 -0400},
Note = {\href{http://www.ams.org/mathscinet-getitem?mr=MR933092}{MR933092}. \href{http:/www.emis.de/MATH-item?0634.03025}{Zbl 0634.03025}.},
Publisher = {Cambridge University Press},
Series = {London Mathematical Society Lecture Note Series},
Title = {Model {T}heory and {M}odules},
Volume = {130},
Year = {1988}}
@unpublished{Reimann:nd,
Author = {Jan Reimann},
Date-Added = {2007-09-27 08:22:09 -0400},
Date-Modified = {2007-09-27 09:11:37 -0400},
Note = {Submitted},
Title = {Randomness beyond Lebesgue measure},
Url = {http://math.berkeley.edu/~reimann/Publications/randomness_beyond_preprint.pdf},
Year = {2007}}
@book{Saks1937,
Address = {New York},
Author = {Saks, Stanis{\l}aw},
Date-Added = {2007-09-27 08:22:09 -0400},
Date-Modified = {2007-09-27 08:22:10 -0400},
Note = {With two additional notes by Stefan Banach. Translated by L.C. Young. \href{http://www.ams.org/mathscinet-getitem?mr=MR0167578}{MR0167578}. \href{http:/www.emis.de/MATH-item?63.0183.05}{JFM 63.0183.05}.},
Publisher = {Stechert},
Series = {Monografie Matematyczne},
Title = {Theory of the {I}ntegral},
Volume = {7},
Year = {1937}}
@book{samuel:70,
Address = {Boston, Mass.},
Author = {Samuel, Pierre},
Date-Added = {2007-09-27 08:22:09 -0400},
Date-Modified = {2007-09-27 08:22:10 -0400},
Mrclass = {10.01},
Mrnumber = {42 \#177},
Pages = {109},
Publisher = {Houghton Mifflin Co.},
Title = {Algebraic theory of numbers},
Year = {1970}}
@article{MR929498,
Author = {Shelah, Saharon},
Date-Added = {2007-09-27 08:22:09 -0400},
Date-Modified = {2007-09-27 08:22:10 -0400},
Fjournal = {Journal of the American Mathematical Society},
Issn = {0894-0347},
Journal = {J. Amer. Math. Soc.},
Mrclass = {05A17 (03D20)},
Mrnumber = {MR929498 (89a:05017)},
Mrreviewer = {Andreas Blass},
Number = {3},
Pages = {683--697},
Title = {Primitive recursive bounds for van der {W}aerden numbers},
Volume = {1},
Year = {1988}}
@unpublished{simpson2,
Author = {Steve Simpson},
Date-Added = {2007-09-27 08:22:09 -0400},
Date-Modified = {2007-09-27 13:27:12 -0400},
Note = {to appear in Mathematical Logic Quarterly},
Title = {Almost everywhere domination and superhighness},
Year = {2006}}
@book{Swartz2001,
Address = {Singapore},
Author = {Swartz, Charles},
Date-Added = {2007-09-27 08:22:09 -0400},
Date-Modified = {2007-09-27 08:22:10 -0400},
Keywords = {Mathematics},
Note = {\href{http://www.ams.org/mathscinet-getitem?mr=MR1845270}{MR1845270}. \href{http:/www.emis.de/MATH-item?0982.26006}{Zbl 0982.26006}.},
Publisher = {World Scientific},
Title = {Introduction to {G}auge {I}ntegrals},
Year = {2001}}
@article{MR0369312,
Author = {Szemer{\'e}di, E.},
Date-Added = {2007-09-27 08:22:09 -0400},
Date-Modified = {2007-09-27 08:22:10 -0400},
Fjournal = {Polska Akademia Nauk. Instytut Matematyczny. Acta Arithmetica},
Issn = {0065-1036},
Journal = {Acta Arith.},
Mrclass = {10L10},
Mrnumber = {MR0369312 (51 \#5547)},
Mrreviewer = {S. L. G. Choi},
Note = {Collection of articles in memory of Juri\u\i\ Vladimirovi\v c Linnik},
Pages = {199--245},
Title = {On sets of integers containing no {$k$} elements in arithmetic progression},
Volume = {27},
Year = {1975}}
@unpublished{tao:nd,
Author = {Tao, T.},
Date-Added = {2007-09-27 08:22:09 -0400},
Date-Modified = {2007-09-27 09:12:19 -0400},
Note = {to appear, ICM 2006 proceedings.},
Title = {The dichotomy between structure and randomness, arithmetic progressions,},
Year = {2006}}
@phdthesis{walk:99,
Author = {Stephen M. Walk},
Date-Added = {2007-09-27 08:22:09 -0400},
Date-Modified = {2007-09-27 08:22:10 -0400},
School = {University of Notre Dame},
Title = {Toward the definability of the array noncomputable degrees},
Year = 1999}
@unpublished{K,
Author = {J. Knight},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:42 -0400},
Note = {in preparation},
Title = {A computable structure of Scott rank $\omega_1^{CK}$ whose computable infinitary theory is not $\aleph_0$-categorical}}
@article{Hjorth1,
Author = {Greg Hjorth},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:42 -0400},
Journal = {Notre Dame J. Formal Logic},
Number = {1},
Pages = {49-51},
Title = {A Note on Counterexamples to the Vaught Conjecture},
Volume = {48},
Year = {2007}}
@article{MR1987431,
Author = {Binns, Stephen},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:42 -0400},
Fjournal = {MLQ. Mathematical Logic Quarterly},
Issn = {0942-5616},
Journal = {MLQ Math. Log. Q.},
Mrclass = {03D30},
Mrnumber = {MR1987431 (2004f:03079)},
Mrreviewer = {Peter Cholak},
Number = {4},
Pages = {327--335},
Title = {A splitting theorem for the {M}edvedev and {M}uchnik lattices},
Volume = {49},
Year = {2003}}
@article{tric,
Author = {Peterzil, Ya'acov and Starchenko, Sergei},
Coden = {PLMTAL},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:43 -0400},
Fjournal = {Proceedings of the London Mathematical Society. Third Series},
Issn = {0024-6115},
Journal = {Proc. London Math. Soc. (3)},
Mrclass = {03C45 (03C40 03C60 12L12)},
Mrnumber = {MR1643405 (2000b:03123)},
Mrreviewer = {O. V. Belegradek},
Number = {3},
Pages = {481--523},
Title = {A trichotomy theorem for o-minimal structures},
Volume = {77},
Year = {1998}}
@unpublished{rodenisbook,
Author = {Rod Downey and Denis R. Hirschfeldt},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:43 -0400},
Note = {Draft available.},
Title = {Algorithmic Randomness and Complexity}}
@article{Axon4p,
Author = {Barmpalias, George and Broadhead, Paul and Cenzer, Douglas and Dashti, Seyyed and Weber, Rebecca},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:43 -0400},
Journal = {Journal for Logic and Computation},
Title = {Algorithmic Randomness of Closed Sets},
Year = {to appear}}
@article{MR2078930,
Author = {Dobrinen, Natasha L. and Simpson, Stephen G.},
Coden = {JSYLA6},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:43 -0400},
Fjournal = {The Journal of Symbolic Logic},
Issn = {0022-4812},
Journal = {J. Symbolic Logic},
Mrclass = {03D28 (03B30 03F35 28A05 28E15)},
Mrnumber = {2005d:03079},
Mrreviewer = {Denis R. Hirschfeldt},
Number = {3},
Pages = {914--922},
Title = {Almost everywhere domination},
Volume = {69},
Year = {2004}}
@article{M,
Author = {Makkai, M.},
Coden = {JSYLA6},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:43 -0400},
Fjournal = {The Journal of Symbolic Logic},
Issn = {0022-4812},
Journal = {J. Symbolic Logic},
Mrclass = {03C70},
Mrnumber = {MR613284 (82m:03049)},
Mrreviewer = {Bienvenido F. Nebres},
Number = {2},
Pages = {301--318},
Title = {An example concerning {S}cott heights},
Volume = {46},
Year = {1981}}
@book{Kaplansky1976,
Address = {Paris},
Author = {Kaplansky, Irving},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:44 -0400},
Edition = {Second},
Keywords = {Mathematics},
Note = {\href{http://www.ams.org/mathscinet-getitem?mr=MR0460303}{MR0460303}. \href{http:/www.emis.de/MATH-item?0954.12500 }{Zbl 0954.12500}.},
Number = {1251},
Publisher = {Hermann},
Series = {Actualit\'es Scientifiques et Industrielles},
Title = {An {I}ntroduction to {D}ifferential {A}lgebra},
Year = {1976}}
@article{MR831773,
Author = {Asarin, E. A. and Pokrovski{\u\i}, A. V.},
Coden = {AVTEAI},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:44 -0400},
Fjournal = {Akademiya Nauk SSSR. Avtomatika i Telemekhanika},
Issn = {0005-2310},
Journal = {Avtomat. i Telemekh.},
Mrclass = {93E03},
Mrnumber = {MR831773 (87e:93096)},
Number = {1},
Pages = {25--33},
Title = {Application of {K}olmogorov complexity to the analysis of the dynamics of controllable systems},
Year = {1986}}
@article{MR1782129,
Author = {Fouch{\'e}, Willem},
Coden = {JSYLA6},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:44 -0400},
Fjournal = {The Journal of Symbolic Logic},
Issn = {0022-4812},
Journal = {J. Symbolic Logic},
Mrclass = {68Q30 (03D15 60J65)},
Mrnumber = {MR1782129 (2002b:68038)},
Mrreviewer = {Andreas Blass},
Number = {1},
Pages = {421--442},
Title = {Arithmetical representations of {B}rownian motion. {I}},
Volume = {65},
Year = {2000}}
@unpublished{MS,
Author = {J. Millar andd G. Sacks},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:44 -0400},
Note = {preprint},
Title = {Atomic models higher up}}
@article{Soare:74*1,
Author = {Soare, Robert I.},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:45 -0400},
Journal = {Bull. Amer. Math. Soc.},
Mrclass = {02F25},
Mrnumber = {MR0373858 (51 \#10058)},
Mrreviewer = {Manuel Lerman},
Pages = {53--58},
Title = {Automorphisms of the lattice of recursively enumerable sets},
Volume = {80},
Year = {1974}}
@unpublished{CGK2,
Author = {W. Calvert and J. Knight and S.Goncharov},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:45 -0400},
Note = {in preparation},
Title = {Boolean algebras and rank preservation}}
@article{MR2248591,
Author = {Downey, Rod and Hirschfeldt, Denis R. and Nies, Andr{\'e} and Terwijn, Sebastiaan A.},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:45 -0400},
Fjournal = {The Bulletin of Symbolic Logic},
Issn = {1079-8986},
Journal = {Bull. Symbolic Logic},
Mrclass = {03D80 (60A05 68Q30)},
Mrnumber = {MR2248591},
Number = {3},
Pages = {411--491},
Title = {Calibrating randomness},
Volume = {12},
Year = {2006}}
@unpublished{CGKM,
Author = {W. Calvert and J. Knight and S. Goncharov and J. Millar},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:45 -0400},
Note = {in preparation},
Title = {Categorical computable infinitary theories}}
@unpublished{HJK,
Author = {V. Harizanov and J. Knight and Carl Jockusch},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:45 -0400},
Note = {in preparation},
Title = {Chains and anti-chains in partial orders}}
@phdthesis{walkerwhite:00,
Address = {Ithaca, NY, USA},
Author = {Walker M. White},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:46 -0400},
School = {Cornell University},
Title = {Characterizations for Computable Structures},
Year = 2000}
@article{CK,
Author = {W. Calvert and J. Knight},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:46 -0400},
Journal = {Bull. Symbolic Logic},
Note = {Solicited expository paper},
Number = {191-218},
Title = {Classification from a computable point of view},
Volume = {12},
Year = {2006}}
@incollection{DK,
Address = {Providence, RI},
Author = {D'Aquino, Paola and Knight, Julia F.},
Booktitle = {Nonstandard models of arithmetic and set theory},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:46 -0400},
Mrclass = {03H15 (03C62)},
Mrnumber = {MR2089274 (2005h:03126)},
Mrreviewer = {Constantine Dimitracopoulos},
Pages = {23--36},
Publisher = {Amer. Math. Soc.},
Series = {Contemp. Math.},
Title = {Coding in {$I\Delta\sb 0$}},
Volume = {361},
Year = {2004}}
@phdthesis{Hirst:87,
Author = {Hirst, Jeffry L.},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:46 -0400},
School = {The Pennsylvania State University},
Title = {Combinatorics in {S}ubsystems of {S}econd {O}rder {A}rithmetic},
Year = {1987}}
@unpublished{el2,
Author = {Pantelis Eleftheriou},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:46 -0400},
Note = {Submitted, preprint available},
Title = {Compact domination for groups definable in linear o-minimal structures},
Year = {2006}}
@article{MR2135656,
Author = {Ambos-Spies, Klaus and Kjos-Hanssen, Bj{\o}rn and Lempp, Steffen and Slaman, Theodore A.},
Coden = {JSYLA6},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:46 -0400},
Fjournal = {The Journal of Symbolic Logic},
Issn = {0022-4812},
Journal = {J. Symbolic Logic},
Mrclass = {03D28 (03F35 03F60)},
Mrnumber = {MR2135656},
Number = {4},
Pages = {1089--1104},
Title = {Comparing {DNR} and {WWKL}},
Volume = {69},
Year = {2004}}
@article{CCKM,
Author = {Calvert, Wesley and Cummins, D. and Julia Knight and Miller, S.},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:47 -0400},
Fjournal = {Algebra i Logika. Institut Diskretno\u\i\ Matematiki i Informatiki},
Issn = {0373-9252},
Journal = {Algebra Logika},
Mrclass = {03C57 (03C13 03C15 03D45)},
Mrnumber = {MR2135387 (2006e:03049)},
Mrreviewer = {Andrey Morozov},
Number = {6},
Pages = {666--701, 759},
Title = {Comparison of classes of finite structures},
Volume = {43},
Year = {2004}}
@unpublished{crele,
Author = {Peterzil, Ya'acov and Starchenko, Sergei},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:47 -0400},
Note = {submitted, preprint available},
Title = {Complex analytic geometry and analytic-geometric categories},
Year = {2006}}
@unpublished{newtonan,
Author = {Peterzil, Ya'acov and Starchenko, Sergei},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:47 -0400},
Note = {to appear in the Special Volume of Isaak Newton Institute},
Title = {Complex analytic geometry in non-standard setting},
Year = {2006}}
@article{MR2136634,
Author = {Soare, Robert I.},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:47 -0400},
Fjournal = {The Bulletin of Symbolic Logic},
Issn = {1079-8986},
Journal = {Bull. Symbolic Logic},
Mrclass = {03D25 (03D10 53C23)},
Mrnumber = {MR2136634 (2005m:03084)},
Number = {4},
Pages = {457--486},
Title = {Computability theory and differential geometry},
Volume = {10},
Year = {2004}}
@unpublished{ChKM2,
Author = {J. Chisholm and J. Knight and S. Miller},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:47 -0400},
Note = {to appear in J.\ Symb. Logic},
Title = {Computable embeddings and strongly minimal theories}}
@unpublished{HKLMMMW,
Author = {V. Harizanov and J. Knight and Karen Lange and C. Maher and S. Miller and C. McCoy and J. Wallbaum},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:48 -0400},
Note = {in preparation},
Title = {Computable fields}}
@unpublished{GrK,
Author = {Noam Greenberg and J. Knight},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:48 -0400},
Note = {in preparation},
Title = {Computable structure theory on $\omega_1$}}
@book{MR1767842,
Address = {Amsterdam},
Author = {Ash, C. J. and Knight, J.},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:48 -0400},
Isbn = {0-444-50072-3},
Mrclass = {03D45 (03-02 03D28 03D30)},
Mrnumber = {MR1767842},
Mrreviewer = {Rodney G. Downey},
Pages = {xvi+346},
Publisher = {North-Holland Publishing Co.},
Series = {Studies in Logic and the Foundations of Mathematics},
Title = {Computable structures and the hyperarithmetical hierarchy},
Volume = {144},
Year = {2000}}
@inbook{CGK,
Author = {W. Calvert and S. Goncharov and J. Knight},
Booktitle = {Advances in Logic},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:48 -0400},
Editor = {Gao and Jackson and Zhang},
Pages = {43-66},
Publisher = {AMS},
Series = {Con.\ Math},
Title = {Computable structures of Scott rank $\omega_1^{CK}$ in familiar classes},
Year = {2007}}
@article{MR2210068,
Author = {Calvert, Wesley and Knight, Julia F. and Millar, Jessica},
Coden = {JSYLA6},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:48 -0400},
Fjournal = {The Journal of Symbolic Logic},
Issn = {0022-4812},
Journal = {J. Symbolic Logic},
Mrclass = {03D45 (03C75)},
Mrnumber = {MR2210068},
Number = {1},
Pages = {283--298},
Title = {Computable trees of {S}cott rank {$\omega\sb 1\sp {CK}$}, and computable approximation},
Volume = {71},
Year = {2006}}
@article{CKM,
Author = {W. Calvert and J. Knight and J. Millar},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:48 -0400},
Journal = {J. Symbolic Logic},
Number = {283-298},
Title = {Computable trees of Scott rank $\omega_1^{CK}$, and computable approximation},
Volume = {71},
Year = {2006}}
@article{pps1,
Author = {Peterzil, Y. and Pillay, A. and Starchenko, S.},
Coden = {TAMTAM},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:49 -0400},
Fjournal = {Transactions of the American Mathematical Society},
Issn = {0002-9947},
Journal = {Trans. Amer. Math. Soc.},
Mrclass = {03C60 (03C64 20A15)},
Mrnumber = {MR1707202 (2001b:03036)},
Mrreviewer = {H. Dugald Macpherson},
Number = {10},
Pages = {4397--4419},
Title = {Definably simple groups in o-minimal structures},
Volume = {352},
Year = {2000}}
@phdthesis{kautz,
Author = {Steven Kautz},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:49 -0400},
School = {Cornell University},
Title = {Degrees of Random Sets},
Year = {1991}}
@article{MR2001061,
Author = {Cenzer, Douglas and Hinman, Peter G.},
Coden = {AMLOEH},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:49 -0400},
Fjournal = {Archive for Mathematical Logic},
Issn = {0933-5846},
Journal = {Arch. Math. Logic},
Mrclass = {03D30 (03D65)},
Mrnumber = {MR2001061 (2004k:03081)},
Mrreviewer = {C. G. Jockusch, Jr.},
Number = {6},
Pages = {583--600},
Title = {Density of the {M}edvedev lattice of {$\Pi\sp 0\sb 1$} classes},
Volume = {42},
Year = {2003}}
@book{Cohn1965,
Address = {New York},
Author = {Cohn, Richard M.},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:49 -0400},
Note = {\href{http://www.ams.org/mathscinet-getitem?mr=MR0205987}{MR0205987}. \href{http:/www.emis.de/MATH-item?0127.26402}{Zbl 0127.26402}.},
Publisher = {Interscience},
Title = {Difference {A}lgebra},
Year = {1965}}
@article{CCHM,
Author = {Calvert, Wesley and Cenzer, Douglas and Harizanov, Valentina and Morozov, Andrei},
Coden = {APALD7},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:49 -0400},
Fjournal = {Annals of Pure and Applied Logic},
Issn = {0168-0072},
Journal = {Ann. Pure Appl. Logic},
Mrclass = {03C57 (03D45)},
Mrnumber = {MR2229930},
Number = {1-2},
Pages = {61--78},
Title = {Effective categoricity of equivalence structures},
Volume = {141},
Year = {2006}}
@unpublished{Co,
Author = {Joshua A. Cole},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:50 -0400},
Note = {Submitted},
Title = {Embedding $FD(\omega)$ into $\mathcal{P}_s$ densely},
Year = {2007}}
@article{MR2052891,
Author = {Binns, Stephen and Simpson, Stephen G.},
Coden = {AMLOEH},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:50 -0400},
Fjournal = {Archive for Mathematical Logic},
Issn = {0933-5846},
Journal = {Arch. Math. Logic},
Mrclass = {03D30},
Mrnumber = {MR2052891 (2004m:03156)},
Mrreviewer = {Peter Cholak},
Number = {3},
Pages = {399--414},
Title = {Embeddings into the {M}edvedev and {M}uchnik lattices of {$\Pi\sp 0\sb 1$} classes},
Volume = {43},
Year = {2004}}
@article{GHKMMS,
Author = {Goncharov, Sergey and Harizanov, Valentina and Knight, Julia and McCoy, Charles and Miller, Russell and Solomon, Reed},
Coden = {APALD7},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:50 -0400},
Fjournal = {Annals of Pure and Applied Logic},
Issn = {0168-0072},
Journal = {Ann. Pure Appl. Logic},
Mrclass = {03D45 (03C57)},
Mrnumber = {MR2169684 (2006f:03071)},
Mrreviewer = {Denis R. Hirschfeldt},
Number = {3},
Pages = {219--246},
Title = {Enumerations in computable structure theory},
Volume = {136},
Year = {2005}}
@article{MR2275865,
Author = {Csima, Barbara F. and Downey, Rod and Greenberg, Noam and Hirschfeldt, Denis R. and Miller, Joseph S.},
Coden = {JSYLA6},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:50 -0400},
Fjournal = {The Journal of Symbolic Logic},
Issn = {0022-4812},
Journal = {J. Symbolic Logic},
Mrclass = {03D80 (03D28)},
Mrnumber = {MR2275865},
Mrreviewer = {Liang Yu},
Number = {4},
Pages = {1385--1393},
Title = {Every 1-generic computes a properly 1-generic},
Volume = {71},
Year = {2006}}
@article{ps1,
Author = {Peterzil, Ya'acov and Starchenko, Sergei},
Coden = {SMATF6},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:50 -0400},
Fjournal = {Selecta Mathematica. New Series},
Issn = {1022-1824},
Journal = {Selecta Math. (N.S.)},
Mrclass = {03C64 (12J15 12L12 30C35)},
Mrnumber = {MR1868299 (2002m:03056)},
Mrreviewer = {G. Cherlin},
Number = {3},
Pages = {409--445},
Title = {Expansions of algebraically closed fields in o-minimal structures},
Volume = {7},
Year = {2001}}
@article{ps2,
Author = {Peterzil, Ya'acov and Starchenko, Sergei},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:51 -0400},
Fjournal = {Journal of Mathematical Logic},
Issn = {0219-0613},
Journal = {J. Math. Log.},
Mrclass = {03C64 (03H05 12J15 12L12)},
Mrnumber = {MR1978941 (2004f:03072)},
Mrreviewer = {Christopher L. Miller},
Number = {1},
Pages = {1--35},
Title = {Expansions of algebraically closed fields. {II}. {F}unctions of several variables},
Volume = {3},
Year = {2003}}
@article{Lippelpaper,
Author = {Lippel, David},
Coden = {JSYLA6},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:51 -0400},
Fjournal = {The Journal of Symbolic Logic},
Issn = {0022-4812},
Journal = {J. Symbolic Logic},
Mrclass = {03C45 (03C35 18C50)},
Mrnumber = {MR2140041 (2005m:03058)},
Mrreviewer = {Alexandre Ivanov},
Number = {2},
Pages = {460--472},
Title = {Finitely axiomatizable {$\omega$}-categorical theories and the {M}azoyer hypothesis},
Volume = {70},
Year = {2005}}
@book{MR0265324,
Address = {South Bend, Ind.},
Author = {Artin, Emil},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:51 -0400},
Mrclass = {12.40},
Mrnumber = {MR0265324 (42 \#234)},
Pages = {iii+82},
Publisher = {University of Notre Dame Press},
Series = {Edited and supplemented with a section on applications by Arthur N. Milgram. Second edition, with additions and revisions. Fifth reprinting. Notre Dame Mathematical Lectures, No. 2},
Title = {Galois theory},
Year = {1959}}
@article{geocalc,
Author = {Peterzil, Ya'acov and Starchenko, Sergei},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:52 -0400},
Fjournal = {The Bulletin of Symbolic Logic},
Issn = {1079-8986},
Journal = {Bull. Symbolic Logic},
Mrclass = {03C45},
Mrnumber = {MR1380825 (97d:03045)},
Mrreviewer = {Bruno Poizat},
Number = {1},
Pages = {72--83},
Title = {Geometry, calculus and {Z}ilber's conjecture},
Volume = {2},
Year = {1996}}
@unpublished{el1,
Author = {Pantelis Eleftheriou},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:52 -0400},
Note = {Submitted, preprint available},
Title = {Groups definable in linear o-minimal structures},
Year = {2006}}
@incollection{MR1640327,
Address = {Amsterdam},
Author = {Fairtlough, Matt and Wainer, Stanley S.},
Booktitle = {Handbook of proof theory},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:52 -0400},
Mrclass = {03D20 (03F30)},
Mrnumber = {MR1640327 (2000a:03063)},
Mrreviewer = {Alessandro Berarducci},
Pages = {149--207},
Publisher = {North-Holland},
Series = {Stud. Logic Found. Math.},
Title = {Hierarchies of provably recursive functions},
Volume = {137},
Year = {1998}}
@unpublished{CFGKKMP,
Author = {W. Calvert and E. Fokina and S. Goncharov and J. Knight and O. Kudinov and A. S. Morosov and V. Puzarenko},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:53 -0400},
Note = {to appear in J.\ Symb. Logic},
Title = {Index sets for classes of high rank structures}}
@article{CHKM,
Author = {W. Calvert and V. Harizanov and J. Knight and S. Miller},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:53 -0400},
Journal = {Algebra and Logic},
Pages = {306-325},
Title = {Index sets for computable structures},
Volume = {45},
Year = {2006}}
@unpublished{ChFGHKM,
Author = {J. Chisholm and E. Fokina and S. Goncharov and J. Knight and S. Miller},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:53 -0400},
Note = {preprint},
Title = {Intrinsic bounds on complexity at limit levels}}
@article{Weber:06,
Author = {Weber, Rebecca},
Coden = {TAMTAM},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:53 -0400},
Fjournal = {Transactions of the American Mathematical Society},
Issn = {0002-9947},
Journal = {Trans. Amer. Math. Soc.},
Mrclass = {03D28 (03D25)},
Mrnumber = {MR2216257 (2006k:03076)},
Mrreviewer = {Steffen Lempp},
Number = {7},
Pages = {3023--3059 (electronic)},
Title = {Invariance in {$\mathcal{E}^*$} and {$\mathcal{E}_{\Pi}$}},
Volume = {358},
Year = {2006}}
@unpublished{kaneb,
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:54 -0400},
Title = {Kaneb Center},
Url = {http://kaneb.nd.edu/ta/}}
@article{MR2251554,
Author = {Downey, Rod and Nies, Andre and Weber, Rebecca and Yu, Liang},
Coden = {JSYLA6},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:54 -0400},
Fjournal = {The Journal of Symbolic Logic},
Issn = {0022-4812},
Journal = {J. Symbolic Logic},
Mrclass = {03D80 (68Q30)},
Mrnumber = {MR2251554},
Number = {3},
Pages = {1044--1052},
Title = {Lowness and {$\Pi\sp 0\sb 2$} nullsets},
Volume = {71},
Year = {2006}}
@article{MR2166184,
Author = {Nies, Andr{\'e}},
Coden = {ADMTA4},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:54 -0400},
Fjournal = {Advances in Mathematics},
Issn = {0001-8708},
Journal = {Adv. Math.},
Mrclass = {68Q30 (03D28)},
Mrnumber = {MR2166184 (2006j:68052)},
Mrreviewer = {Joseph S. Miller},
Number = {1},
Pages = {274--305},
Title = {Lowness properties and randomness},
Volume = {197},
Year = {2005}}
@unpublished{simpson1,
Author = {Stephen G. Simpson},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:55 -0400},
Note = {to appear in Mathematical Logic Quarterly},
Title = {Mass Problems and Almost Everywhere Domination},
Year = {2006}}
@unpublished{CoSi,
Author = {Joshua A. Cole and Stephen G. Simpson},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:55 -0400},
Note = {Submitted},
Title = {Mass Problems and Hyperarithmeticity},
Year = {2006}}
@article{MR2125147,
Author = {Simpson, Stephen G.},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:55 -0400},
Fjournal = {The Bulletin of Symbolic Logic},
Issn = {1079-8986},
Journal = {Bull. Symbolic Logic},
Mrclass = {03D30 (03D25 03D80 03F15 03F35 68Q30)},
Mrnumber = {2125147},
Number = {1},
Pages = {1--27},
Title = {Mass problems and randomness},
Volume = {11},
Year = {2005}}
@book{O,
Address = {New York},
Author = {Oxtoby, John C.},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:55 -0400},
Edition = {Second},
Isbn = {0-387-90508-1},
Mrclass = {28-02 (54H99)},
Mrnumber = {MR584443 (81j:28003)},
Note = {A survey of the analogies between topological and measure spaces},
Pages = {x+106},
Publisher = {Springer-Verlag},
Series = {Graduate Texts in Mathematics},
Title = {Measure and category},
Volume = {2},
Year = {1980}}
@article{MR2250550,
Author = {Fuchino, Sakae and Greenberg, Noam and Shelah, Saharon},
Coden = {APALD7},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:55 -0400},
Fjournal = {Annals of Pure and Applied Logic},
Issn = {0168-0072},
Journal = {Ann. Pure Appl. Logic},
Mrclass = {03E55 (03E35)},
Mrnumber = {MR2250550 (2007d:03091)},
Mrreviewer = {Stefan Geschke},
Number = {1-3},
Pages = {380--397},
Title = {Models of real-valued measurability},
Volume = {142},
Year = {2006}}
@article{Seetapun.Slaman:95,
Author = {Seetapun, David and Slaman, Theodore A.},
Coden = {NDJFAM},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:56 -0400},
Fjournal = {Notre Dame Journal of Formal Logic},
Issn = {0029-4527},
Journal = {Notre Dame J. Formal Logic},
Note = {Special Issue: Models of arithmetic},
Number = {4},
Pages = {570--582},
Title = {On the strength of {R}amsey's theorem},
Volume = {36},
Year = {1995}}
@article{MR961012,
Author = {Simpson, Stephen G.},
Coden = {JSYLA6},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:56 -0400},
Fjournal = {The Journal of Symbolic Logic},
Issn = {0022-4812},
Journal = {J. Symbolic Logic},
Mrclass = {03F35 (03B30 12L12 13L05)},
Mrnumber = {MR961012 (89j:03052)},
Mrreviewer = {Peter P{\"a}ppinghaus},
Number = {3},
Pages = {961--974},
Title = {Ordinal numbers and the {H}ilbert basis theorem},
Volume = {53},
Year = {1988}}
@article{d-vdd,
Author = {Denef, J. and van den Dries, L.},
Coden = {ANMAAH},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:57 -0400},
Fjournal = {Annals of Mathematics. Second Series},
Issn = {0003-486X},
Journal = {Ann. of Math. (2)},
Mrclass = {03C10 (03C60 14G20 14G30 32B20)},
Mrnumber = {MR951508 (89k:03034)},
Mrreviewer = {Max A. Dickmann},
Number = {1},
Pages = {79--138},
Title = {{$p$}-adic and real subanalytic sets},
Volume = {128},
Year = {1988}}
@article{MR2058190,
Author = {Goncharov, Sergey S. and Harizanov, Valentina S. and Knight, Julia F. and Shore, Richard A.},
Coden = {JSYLA6},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:57 -0400},
Fjournal = {The Journal of Symbolic Logic},
Issn = {0022-4812},
Journal = {J. Symbolic Logic},
Mrclass = {03D45 (03D28 03D55 03F15)},
Mrnumber = {2058190},
Mrreviewer = {C. G. Jockusch, Jr.},
Number = {2},
Pages = {585--611},
Title = {{$\Pi^1_1$} relations and paths through {$\mathcal{O}$}},
Volume = {69},
Year = {2004}}
@article{GHKS,
Author = {Goncharov, Sergey S. and Harizanov, Valentina S. and Knight, Julia F. and Shore, Richard A.},
Coden = {JSYLA6},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:57 -0400},
Fjournal = {The Journal of Symbolic Logic},
Issn = {0022-4812},
Journal = {J. Symbolic Logic},
Mrclass = {03D45 (03D28 03D55 03F15)},
Mrnumber = {MR2058190 (2005d:03083)},
Mrreviewer = {C. G. Jockusch, Jr.},
Number = {2},
Pages = {585--611},
Title = {{$\Pi\sp 1\sb 1$} relations and paths through {$\mathcal{O}$}},
Volume = {69},
Year = {2004}}
@book{MR0385969,
Author = {Matheron, G.},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:57 -0400},
Mrclass = {60D05},
Mrnumber = {MR0385969 (52 \#6828)},
Mrreviewer = {Pamela Davy},
Note = {With a foreword by Geoffrey S. Watson, Wiley Series in Probability and Mathematical Statistics},
Pages = {xxiii+261},
Publisher = {John Wiley\thinspace \&\thinspace Sons, New York-London-Sydney},
Title = {Random sets and integral geometry},
Year = {1975}}
@unpublished{CHKMo,
Author = {W. Calvert and V. Harizanov and J. Knight and A. Morozov},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:57 -0400},
Title = {Rank preservation and the Malcev embedding}}
@unpublished{greenberg1,
Author = {Noam Greenberg and Antonio Montalb\'an},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:57 -0400},
Note = {To appear in the Transactions of the American Mathematical Society},
Title = {Ranked structures and arithmetic transfinite recursion}}
@book{rm2001,
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:58 -0400},
Editor = {S. G. Simpson},
Note = {X + 401 pages},
Publisher = {Association for Symbolic Logic},
Series = {Lecture {N}otes in {L}ogic},
Title = {Reverse {M}athematics 2001},
Volume = 21,
Year = 2005}
@unpublished{Downey.Montalban:nd,
Author = {R. Downey and A. Montalb{\'a}n},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:58 -0400},
Note = {Submitted},
Title = {Slender Classes},
Year = 2006}
@unpublished{DK2,
Author = {D'Aquino, Paola and Knight, Julia F.},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:58 -0400},
Note = {to appear in Fund. Math},
Title = {Strong initial segments of models of $I\Delta_0$}}
@article{GK,
Author = {S. Goncharov and J. Knight},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:59 -0400},
Journal = {Algebra and Logic},
Pages = {351-373},
Title = {Structure and non-structure theorems},
Volume = {41},
Year = {2002}}
@article{bupiwa:cb,
Author = {Buechler, Steven and Pillay, Anand and Wagner, Frank},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:59 -0400},
Fjournal = {Journal of the American Mathematical Society},
Journal = {J. Amer. Math. Soc.},
Number = {1},
Pages = {109--124 (electronic)},
Title = {Supersimple theories},
Volume = {14},
Year = {2001}}
@unpublished{teaching,
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:59 -0400},
Title = {Teaching Seminar},
Url = {http://ndmathed.blogspot.com/2007/03/mathed-events-2006-2007.html}}
@article{MR1071321,
Author = {van Lambalgen, Michiel},
Coden = {JSYLA6},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:59 -0400},
Fjournal = {The Journal of Symbolic Logic},
Issn = {0022-4812},
Journal = {J. Symbolic Logic},
Mrclass = {68Q30 (03B45 03C65 03C80 60A05)},
Mrnumber = {MR1071321 (92f:68075)},
Mrreviewer = {Xiang Li},
Number = {3},
Pages = {1143--1167},
Title = {The axiomatization of randomness},
Volume = {55},
Year = {1990}}
@article{marker1,
Author = {David Marker},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:14:59 -0400},
Journal = {Notre Dame J. Formal Logic},
Number = {1},
Pages = {93-97},
Title = {The Borel Complexity of Isomorphism for Theories with Many Types},
Volume = {48},
Year = {2007}}
@article{MR1120611,
Author = {Dougherty, Randall and Kechris, Alexander S.},
Coden = {ADMTA4},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:15:00 -0400},
Fjournal = {Advances in Mathematics},
Issn = {0001-8708},
Journal = {Adv. Math.},
Mrclass = {03E15 (03D15 26A36 26A39 28A99)},
Mrnumber = {MR1120611 (92h:03072)},
Mrreviewer = {Hisao Tanaka},
Number = {2},
Pages = {145--169},
Title = {The complexity of antidifferentiation},
Volume = {88},
Year = {1991}}
@article{MR1794714,
Author = {Fouch{\'e}, Willem},
Coden = {ADMTA4},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:15:00 -0400},
Fjournal = {Advances in Mathematics},
Issn = {0001-8708},
Journal = {Adv. Math.},
Mrclass = {68Q30 (60J65)},
Mrnumber = {MR1794714 (2002e:68044)},
Mrreviewer = {P. G{\'a}cs},
Number = {2},
Pages = {317--343},
Title = {The descriptive complexity of {B}rownian motion},
Volume = {155},
Year = {2000}}
@unpublished{V,
Author = {Vanden Boom, M.},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:15:01 -0400},
Note = {to appear in Fund. Math},
Title = {The effective Borel hierarchy}}
@article{dmm,
Author = {van den Dries, Lou and Macintyre, Angus and Marker, David},
Coden = {ANMAAH},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:15:01 -0400},
Fjournal = {Annals of Mathematics. Second Series},
Issn = {0003-486X},
Journal = {Ann. of Math. (2)},
Mrclass = {12L12 (03C10 03C62)},
Mrnumber = {MR1289495 (95k:12015)},
Mrreviewer = {Thanases Pheidas},
Number = {1},
Pages = {183--205},
Title = {The elementary theory of restricted analytic fields with exponentiation},
Volume = {140},
Year = {1994}}
@article{MR2017894,
Author = {Nabutovsky, Alexander and Weinberger, Shmuel},
Coden = {GEMDAT},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:15:01 -0400},
Fjournal = {Geometriae Dedicata},
Issn = {0046-5755},
Journal = {Geom. Dedicata},
Mrclass = {53C23 (03D25 03D40 53C20 57R50 58D17 68Q30)},
Mrnumber = {MR2017894 (2005d:53063)},
Mrreviewer = {Janko Latschev},
Pages = {1--54},
Title = {The fractal nature of {R}iem/{D}iff. {I}},
Volume = {101},
Year = {2003}}
@article{C1,
Author = {Calvert, Wesley},
Coden = {AMLOEH},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:15:01 -0400},
Fjournal = {Archive for Mathematical Logic},
Issn = {0933-5846},
Journal = {Arch. Math. Logic},
Mrclass = {03D45 (03C57 12L99)},
Mrnumber = {MR2052886 (2005b:03103)},
Mrreviewer = {Rodney G. Downey},
Number = {3},
Pages = {327--336},
Title = {The isomorphism problem for classes of computable fields},
Volume = {43},
Year = {2004}}
@article{C2,
Author = {Calvert, Wesley},
Coden = {JSYLA6},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:15:01 -0400},
Fjournal = {The Journal of Symbolic Logic},
Issn = {0022-4812},
Journal = {J. Symbolic Logic},
Mrclass = {03D45 (03C57 20K10)},
Mrnumber = {MR2119136 (2005j:03033)},
Mrreviewer = {Leon Harkleroad},
Number = {1},
Pages = {331--345},
Title = {The isomorphism problem for computable abelian {$p$}-groups of bounded length},
Volume = {70},
Year = {2005}}
@inproceedings{Axon2p,
Author = {Kjos-Hanssen, Bj{\o}rn and Anil Nerode},
Booktitle = {LFCS 2007: Symposium on Logical Foundations of Computer Science},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-09-27 11:07:25 -0400},
Note = {to appear},
Series = {Lecture Notes in Computer Science},
Title = {The Law of the Iterated Logarithm for Algorithmically Random Paths of {B}rownian Motion},
Year = {2007}}
@article{C,
Author = {Camerlo, Riccardo},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:15:02 -0400},
Journal = {J. Symbolic Logic},
Pages = {879-895},
Title = {The relation of recursive isomorphism for countable structures},
Volume = {67},
Year = {2002}}
@unpublished{edel,
Author = {Mario Edmundo and Pantelis Eleftheriou},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:15:02 -0400},
Note = {to appear in Mathematical Logic Quarterly},
Title = {The universal covering homomorphism in o-minimal expansions of groups},
Year = {2006}}
@book{Saks1964,
Address = {New York},
Author = {Saks, Stanislaw},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:15:02 -0400},
Note = {Second revised edition. English translation by L. C. Young. With two additional notes by Stefan Banach. \href{http://www.ams.org/mathscinet-getitem?mr=MR0167578}{MR0167578}. \href{http:/www.emis.de/MATH-item?63.0183.05}{JFM 63.0183.05}.},
Publisher = {Stechert},
Title = {Theory of the {I}ntegral},
Year = {1937}}
@unpublished{KMV,
Author = {J. Knight and S. Miller and Vanden Boom, M.},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:15:03 -0400},
Note = {to appear in J.\ Symb. Logic},
Title = {Turing computable embeddings}}
@unpublished{CHS,
Author = {W. Calvert and V. Harizanov and A. Shlapentokh},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:15:03 -0400},
Note = {to appear in J. of the London Mathematical Society},
Title = {Turing degrees of isomorphism types of algebraic objects}}
@article{ps3,
Author = {Peterzil, Ya'acov and Starchenko, Sergei},
Coden = {SMATF6},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:15:03 -0400},
Fjournal = {Selecta Mathematica. New Series},
Issn = {1022-1824},
Journal = {Selecta Math. (N.S.)},
Mrclass = {03C64 (03C98 03H05 14H52 30G06 33E05)},
Mrnumber = {MR2134454 (2006d:03063)},
Mrreviewer = {Ricardo Bianconi},
Number = {4},
Pages = {525--550},
Title = {Uniform definability of the {W}eierstrass {$\wp$} functions and generalized tori of dimension one},
Volume = {10},
Year = {2004}}
@unpublished{bu:vcfr,
Author = {Buechler, Steven},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-05-17 11:15:03 -0400},
Note = {to appear},
Title = {Vaught's conjecture for superstable theories of finite rank}}
@book{ndlectures,
Address = {South Bend, Ind.},
Date-Added = {2007-05-17 11:14:42 -0400},
Date-Modified = {2007-09-27 09:02:55 -0400},
Key = {Notre Dame},
Publisher = {University of Notre Dame Press},
Series = {Notre Dame Mathematical Lectures},
Url = {http://projecteuclid.org/ndml},
Year = {1942--1992}}
@article{MR1080236,
Author = {Yu, Xiaokang and Simpson, Stephen G.},
Coden = {AMLOEH},
Fjournal = {Archive for Mathematical Logic},
Issn = {0933-5846},
Journal = {Arch. Math. Logic},
Mrclass = {03F35 (28E15)},
Mrnumber = {MR1080236 (91i:03112)},
Mrreviewer = {Roman Murawski},
Number = {3},
Pages = {171--180},
Title = {Measure theory and weak {K}\"onig's lemma},
Volume = {30},
Year = {1990}}
@phdthesis{young:01,
Author = {Jessica Millar Young},
School = {MIT},
Title = {Decide prime models},
Year = {2001}}
@article{Yates:65,
Author = {Yates, C. E. M.},
Date-Modified = {2005-05-29 20:57:43 -0500},
Fjournal = {Duke Mathematical Journal},
Issn = {0012-7094},
Journal = {Duke Math. J.},
Mrclass = {02.70},
Mrnumber = {0180486},
Mrreviewer = {P. Young},
Pages = {461--468},
Title = {Three theorems on the degrees of recursively enumerable sets},
Volume = {32},
Year = {1965}}
@article{Wehner:98,
Author = {Wehner, Stephan},
Coden = {PAMYAR},
Fjournal = {Proceedings of the American Mathematical Society},
Issn = {0002-9939},
Journal = {Proc. Amer. Math. Soc.},
Mrclass = {03D45 (03C57)},
Mrnumber = {98h:03059},
Mrreviewer = {Rodney G. Downey},
Number = {7},
Pages = {2131--2139},
Title = {Enumerations, countable structures and {T}uring degrees},
Volume = {126},
Year = {1998}}
@phdthesis{Weber:04,
Author = {Rebecca Weber},
School = {University of Notre Dame},
Title = {A definable relation between c.e.\ sets and ideals},
Year = {2004}}
@incollection{Tennenbaum:63,
Author = {Tennenbaum, S.},
Booktitle = {Proc. Sympos. Math. Theory of Automata (New York, 1962)},
Mrclass = {02.70},
Mrnumber = {0167406},
Mrreviewer = {A. P. Ershov},
Pages = {71--73},
Publisher = {Polytechnic Press of Polytechnic Inst. of Brooklyn, Brooklyn, N.Y.},
Title = {Degree of unsolvability and the rate of growth of functions},
Year = {1963}}
@article{Soskov:96,
Author = {Soskov, Ivan N.},
Fjournal = {Mathematical Logic Quarterly},
Issn = {0942-5616},
Journal = {Math. Logic Quart.},
Mrclass = {03D45 (03D55 03D70 03D75)},
Mrnumber = {98a:03069},
Mrreviewer = {Peter G. Hinman},
Number = {4},
Pages = {469--480},
Title = {Intrinsically hyperarithmetical sets},
Volume = {42},
Year = {1996}}
@article{Slaman:98,
Author = {Slaman, Theodore A.},
Coden = {PAMYAR},
Fjournal = {Proceedings of the American Mathematical Society},
Issn = {0002-9939},
Journal = {Proc. Amer. Math. Soc.},
Mrclass = {03C57 (03D45)},
Mrnumber = {98h:03047},
Mrreviewer = {Cristian Calude},
Number = {7},
Pages = {2117--2122},
Title = {Relative to any nonrecursive set},
Volume = {126},
Year = {1998}}
@book{Simpson:98,
Address = {Berlin},
Author = {Simpson, Stephen G.},
Date-Modified = {2005-05-29 21:01:02 -0500},
Isbn = {3-540-64882-8},
Mrclass = {03F35 (03-02 03B30)},
Mrnumber = {2001i:03126},
Mrreviewer = {Michael M{\"o}llerfeld},
Pages = {xiv+445},
Publisher = {Springer-Verlag},
Series = {Perspectives in Mathematical Logic},
Title = {Subsystems of second order arithmetic},
Year = {1999}}
@article{MR0166090,
Author = {Sacks, Gerald E.},
Fjournal = {The Michigan Mathematical Journal},
Issn = {0026-2285},
Journal = {Michigan Math. J.},
Mrclass = {02.70},
Mrnumber = {MR0166090 (29 \#3368)},
Mrreviewer = {J. R. Shoenfield},
Pages = {193--205},
Title = {A maximal set which is not complete},
Volume = {11},
Year = {1964}}
@article{Sacks:64*2,
Author = {Gerald E. Sacks},
Journal = {Michigan Math. J.},
Pages = {193--205},
Title = {A Maximal Set Which is not Complete},
Volume = {11},
Year = {1964}}
@article{PosnerRobinson,
Author = {Posner, David B. and Robinson, Robert W.},
Coden = {JSYLA6},
Fjournal = {The Journal of Symbolic Logic},
Issn = {0022-4812},
Journal = {J. Symbolic Logic},
Mrclass = {03D30},
Mrnumber = {83c:03040},
Mrreviewer = {C. G. Jockusch, Jr.},
Number = {4},
Pages = {714--722},
Title = {Degrees joining to {${\bf 0}\sp{\prime} $}},
Volume = {46},
Year = {1981}}
@article{Morley:70,
Author = {Morley, Michael},
Journal = {J. Symbolic Logic},
Mrclass = {02.50},
Mrnumber = {44 \#5213},
Mrreviewer = {F. R. Drake},
Pages = {14--18},
Title = {The number of countable models},
Volume = {35},
Year = {1970}}
@incollection{Milner:85,
Address = {Dordrecht},
Author = {Milner, E. C.},
Booktitle = {Graphs and order (Banff, Alta., 1984)},
Mrclass = {04A20 (03E05 06A10)},
Mrnumber = {87h:04004},
Mrreviewer = {James Baumgartner},
Pages = {487--502},
Publisher = {Reidel},
Series = {NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci.},
Title = {Basic wqo- and bqo-theory},
Volume = {147},
Year = {1985}}
@article{Miller.Martin:68,
Author = {W. Miller and D. A. Martin},
Journal = {Z. Math. Logik Grundlag. Math.},
Pages = {159--166},
Title = {The degree of hyperimmune sets},
Volume = {14},
Year = {1968}}
@article{Martin:66*1,
Author = {Martin, D. A.},
Date-Modified = {2005-05-29 20:59:07 -0500},
Journal = {Z. Math. Logik Grundlag. Math.},
Mrnumber = {0309722},
Pages = {295--310},
Title = {Classes of recursively enumerable sets and degrees of unsolvability},
Volume = {12},
Year = {1966}}
@article{Lempp.Nies.ea:01,
Author = {Lempp, Steffen and Nies, Andr{\'e} and Solomon, D. Reed},
Coden = {AMLOEH},
Fjournal = {Archive for Mathematical Logic},
Issn = {0933-5846},
Journal = {Arch. Math. Logic},
Mrclass = {03D25},
Mrnumber = {2002h:03093},
Mrreviewer = {Peter Cholak},
Number = {6},
Pages = {415--423},
Title = {On the filter of computably enumerable supersets of an $r$-maximal set},
Volume = {40},
Year = {2001}}
@incollection{Kucera:85,
Address = {Berlin},
Author = {Ku{\v{c}}era, Anton{\'{\i}}n},
Booktitle = {Recursion theory week (Oberwolfach, 1984)},
Date-Modified = {2005-05-29 20:57:09 -0500},
Mrclass = {03D35 (03D30 03F30)},
Mrnumber = {87e:03102},
Mrreviewer = {A. M. Dawes},
Pages = {245--259},
Publisher = {Springer},
Series = {Lecture Notes in Math.},
Title = {Measure, {$\Pi\sp 0\sb 1$}-classes and complete extensions of {${\rm PA}$}},
Volume = {1141},
Year = {1985}}
@phdthesis{Kurtz:81,
Author = {Kurtz, Stuart},
Date-Added = {2005-05-16 08:43:46 -0500},
Date-Modified = {2005-05-16 08:45:32 -0500},
School = {University of {I}llinios at {U}rbana-{C}hampaign},
Title = {Randomness and Genericty in the degrees of unsolvability},
Year = {1981}}
@article{Kummer:01,
Author = {Kummer, Martin},
Fjournal = {The Journal of Symbolic Logic},
Journal = {J. Symbolic Logic},
Mrclass = {03D25},
Mrnumber = {93b:03071},
Mrreviewer = {John P. Helm},
Number = {3},
Pages = {1068--1074},
Title = {Diagonals and semihyperhypersimple sets},
Volume = {56},
Year = {1991}}
@unpublished{RKnight:02,
Author = {R. W. Knight},
Note = {2002},
Title = {The {V}aught Conjecture}}
@article{JockuschSoare:DegreesOfTheories,
Author = {Jockusch, Jr., Carl G. and Soare, Robert I.},
Fjournal = {Transactions of the American Mathematical Society},
Issn = {0002-9947},
Journal = {Trans. Amer. Math. Soc.},
Mrclass = {02F30 (02F35 02G05)},
Mrnumber = {0316227},
Mrreviewer = {S. Feferman},
Pages = {33--56},
Title = {{$\Pi \sp{0}\sb{1}$} classes and degrees of theories},
Volume = {173},
Year = {1972}}
@article{Jockusch.Soare:72*1,
Author = {Jockusch, Jr., Carl G. and Soare, Robert I.},
Date-Modified = {2005-05-29 20:55:57 -0500},
Journal = {Pacific J. Math.},
Mrnumber = {0309722},
Pages = {605--616},
Title = {Degrees of members of ${\Pi \sp{0}\sb{1}}$ classes},
Volume = {40},
Year = {1972}}
@incollection{Jockusch:NoFixedPoints,
Address = {Amsterdam},
Author = {Jockusch, Jr., Carl G.},
Booktitle = {Logic, methodology and philosophy of science, VIII (Moscow, 1987)},
Mrclass = {03D30},
Mrnumber = {91c:03036},
Mrreviewer = {Barry Cooper},
Pages = {191--201},
Publisher = {North-Holland},
Series = {Stud. Logic Found. Math.},
Title = {Degrees of functions with no fixed points},
Volume = {126},
Year = {1989}}
@article{Herrman.Kummer:94,
Author = {Herrmann, Eberhard and Kummer, Martin},
Fjournal = {The Journal of Symbolic Logic},
Journal = {J. Symbolic Logic},
Mrclass = {03D25},
Mrnumber = {95f:03066},
Mrreviewer = {Anne Leggett},
Number = {1},
Pages = {60--72},
Title = {Diagonals and $\mathcal{{D}}$-maximal sets},
Volume = {59},
Year = {1994}}
@article{Hausdorff:gap,
Author = {Hausdorff, Felix},
Journal = {Abh.\ d.\ K\"{o}nig.\ S\"{a}chs.\ Gesellschaft d.\ Wiss.\ (Math.\ -Phys.\ Kl.)},
Pages = {296-334},
Title = {Die Graduierung nach dem Endverlauf},
Volume = {31},
Year = 1909}
@article{GiustoSimpson,
Author = {Giusto, Mariagnese and Simpson, Stephen G.},
Coden = {JSYLA6},
Fjournal = {The Journal of Symbolic Logic},
Issn = {0022-4812},
Journal = {J. Symbolic Logic},
Mrclass = {03F35 (03F60 54E45 54E50)},
Mrnumber = {2003b:03085},
Mrreviewer = {Kazuyuki Tanaka},
Number = {3},
Pages = {1451--1480},
Title = {Located sets and reverse mathematics},
Volume = {65},
Year = {2000}}
@unpublished{Downey.Hirschfeldt.ea.nd,
Author = {Rod Downey and Denis Hirschfeldt and Steffen Lempp and Reed Solomon},
Note = {Submitted},
Title = {Computability-theoretic and proof-theoretic aspects of partial and linear orderings}}
@article{Downey.Jockusch:94,
Author = {Downey, Rod and Jockusch, Carl G.},
Coden = {PAMYAR},
Fjournal = {Proceedings of the American Mathematical Society},
Issn = {0002-9939},
Journal = {Proc. Amer. Math. Soc.},
Mrclass = {03C57 (03D30 03D45 06E99)},
Mrnumber = {95a:03044},
Mrreviewer = {Marat M. Arslanov},
Number = {3},
Pages = {871--880},
Title = {Every low {B}oolean algebra is isomorphic to a recursive one},
Volume = {122},
Year = {1994}}
@article{Coles.Downey.ea:00,
Author = {Coles, Richard J. and Downey, Rod G. and Slaman, Theodore A.},
Coden = {JLMSAK},
Fjournal = {Journal of the London Mathematical Society. Second Series},
Issn = {0024-6107},
Journal = {J. London Math. Soc. (2)},
Mrclass = {03D25 (03D28)},
Mrnumber = {2002a:03081},
Mrreviewer = {Hong Lu},
Number = {3},
Pages = {641--649},
Title = {Every set has a least jump enumeration},
Volume = {62},
Year = {2000}}
@article{Chisholm:90,
Author = {Chisholm, John},
Coden = {JSYLA6},
Fjournal = {The Journal of Symbolic Logic},
Issn = {0022-4812},
Journal = {J. Symbolic Logic},
Mrclass = {03C57 (03C25)},
Mrnumber = {91i:03072},
Mrreviewer = {Alexandre Ivanov},
Number = {3},
Pages = {1168--1191},
Title = {Effective model theory vs.\ recursive model theory},
Volume = {55},
Year = {1990}}
@article{Cenzer.Nies:01,
Author = {Cenzer, Douglas and Nies, Andre},
Coden = {JSYLA6},
Fjournal = {The Journal of Symbolic Logic},
Issn = {0022-4812},
Journal = {J. Symbolic Logic},
Mrclass = {03D55 (03D25 03D45)},
Mrnumber = {1 877 019},
Mrreviewer = {Rodney G. Downey},
Number = {4},
Pages = {1749--1765},
Title = {Initial segments of the lattice of {$\Pi\sp 0\sb 1$} classes},
Volume = {66},
Year = {2001}}
@article{Cenzer.Nies:04,
Author = {Cenzer, Douglas and Nies, Andre},
Journal = {Proceedings of the AMS},
Title = {Global properties of the lattice of {$\Pi^0_1$} classes},
Year = {2004}}
@article{Ash.Knight.ea:89,
Author = {Ash, Chris and Knight, Julia and Manasse, Mark and Slaman, Theodore},
Coden = {APALD7},
Fjournal = {Annals of Pure and Applied Logic},
Issn = {0168-0072},
Journal = {Ann. Pure Appl. Logic},
Mrclass = {03C57},
Mrnumber = {90d:03065},
Mrreviewer = {Andrey Morozov},
Number = {3},
Pages = {195--205},
Title = {Generic copies of countable structures},
Volume = {42},
Year = {1989}}
@article{Ash:86*1,
Author = {Ash, C. J.},
Coden = {TAMTAM},
Fjournal = {Transactions of the American Mathematical Society},
Issn = {0002-9947},
Journal = {Trans. Amer. Math. Soc.},
Mrclass = {03D30 (03C57 03C75 03D45)},
Mrnumber = {87j:03060},
Number = {2},
Pages = {497--514},
Title = {Recursive labelling systems and stability of recursive structures in hyperarithmetical degrees},
Volume = {298},
Year = {1986}}
@article{Ash:88,
Author = {Ash, C. J.},
Coden = {TAMTAM},
Fjournal = {Transactions of the American Mathematical Society},
Issn = {0002-9947},
Journal = {Trans. Amer. Math. Soc.},
Mrclass = {03D30 (03C57 03C75 03D45)},
Mrnumber = {89e:03069},
Number = {2},
Pages = {851},
Title = {Errata to: ``{R}ecursive labelling systems and stability of recursive structures in hyperarithmetical degrees'' [{T}rans.\ {A}mer.\ {M}ath.\ {S}oc.\ {\bf 298} (1986), no.\ 2, 497--514; {M}{R} 87j:03060]},
Volume = {310},
Year = {1988}}
@article{Ackermann,
Author = {Ackermann, W.},
Journal = {Math. Ann.},
Language = {German},
Pages = {118-133},
Reviewer = {{Skolem, Th.; Dr. (Oslo)}},
Title = {{Zum Hilbertschen Aufbau der reellen Zahlen.}},
Volume = {99},
Year = {1928}}
@article{Abramson.Sacks:76,
Author = {F. Abramson and Gerald E. Sacks},
Journal = {J. London Math. Soc.},
Pages = {387--392},
Title = {Uncountable {Gandy} Ordinals},
Volume = {14},
Year = {1976}}
@inproceedings{Addison:65,
Address = {Amsterdam},
Author = {J. W. Addison},
Booktitle = {Theory of Models},
Pages = {1--16},
Publisher = {North--Holland Publishing Co.},
Title = {The Method of Alternating Chains},
Year = {1965}}
@article{Adelman.Blum:91,
Author = {Adelman, D. and Blum, M.},
Journal = {J. Symbolic Logic},
Pages = {891--900},
Title = {Inductive inference and unsolvability},
Volume = {56},
Year = {1991}}
@article{Adian:57,
Author = {Adian, S.I.},
Journal = {Trudy Moskov. Mat. Obshch.},
Pages = {231-298},
Title = {Unsolvability of certain algorithmic problems in the theory of groups},
Volume = {6},
Year = {1957}}
@article{Adian:57*1,
Author = {Adian, S.I.},
Journal = {Akad. Nauk Armyan. SSR Dokl.},
Pages = {9-12},
Title = {Finitely presented groups and algorithms},
Volume = {117},
Year = {1957}}
@article{Aharoni.Magidor.ea:92,
Author = {Ron Aharoni and Menachem Magidor and Richard A. Shore},
Journal = {Journal of Combinatorial Theory (Series B)},
Number = {2},
Pages = {257--290},
Title = {On the strength of {K\"onig's} Duality Theorem},
Volume = {54},
Year = {1992}}
@article{Aharoni.Magidor.ea:93,
Author = {Aharoni, R. and Magidor, M. and Shore, R. A.},
Journal = {J. Combin. Theory Ser. B},
Pages = {257-290},
Title = {On the strength of K\"onig's duality theorem for infinite bipartite graphs},
Volume = {54},
Year = {1993}}
@article{Aharoni:83,
Author = {Ron Aharoni},
Journal = {J. London Math. Soc. (2)},
Pages = {385--392},
Title = {On a duality principle in infinite bipartite graphs},
Volume = {28},
Year = {1983}}
@article{Aharoni:84,
Author = {Ron Aharoni},
Journal = {J. London Math. Soc. (2)},
Pages = {1--12},
Title = {{K}{\"o}nig's duality theorem for infinite bipartite graphs},
Volume = {29},
Year = {1984}}
@article{Ahmad:91,
Author = {Ahmad, S.},
Journal = {J. Symbolic Logic},
Pages = {195--212},
Title = {Embedding the diamond in the {$\Sigma_2$} enumeration degrees},
Volume = {50},
Year = {1991}}
@unpublished{Ambos-Spies.Cooper.ea:86,
Author = {Ambos-Spies, K. and Cooper, S. Barry and Jockusch, Jr., Carl G.},
Note = {Unpublished notes},
Title = {Some Relationships Between {$\mathbf{T}$}- and wtt-degrees},
Year = {1986}}
@article{Ambos-Spies.Fejer.ea:96,
Author = {K. Ambos-Spies and P. A. Fejer and S. Lempp and M. Lerman},
Journal = {Journal of Symbolic Logic},
Number = {3},
Pages = {880--905},
Title = {Decidability of the Two-Quantifier Theory of the Recursively Enumerable Weak Truth-Table Degrees and Other Distributive Upper Semi-Lattices},
Volume = {61},
Year = {1996}}
@unpublished{Ambos-Spies.Fejer:02,
Author = {Ambos-Spies, K. and P. A. Fejer},
Note = {To appear},
Title = {Embedding of $N_5$ and the contiguous degrees},
Year = {2002}}
@article{Ambos-Spies.Fejer:88,
Author = {K. Ambos-Spies and P. A. Fejer},
Journal = {J. Symbolic Logic},
Pages = {1110--1137},
Title = {Degree Theoretic Splitting Properties of Recursively Enumerable Sets},
Volume = {53},
Year = {1988}}
@inproceedings{Ambos-Spies.Homer.ea:90,
Address = {Heidelberg},
Author = {Klaus Ambos-Spies and Steven Homer and Robert I. Soare},
Booktitle = {Sym. on Theoretical Aspects of Computer Science (in Rouen, France, 1990)},
Pages = {24--36},
Publisher = {Springer--Verlag},
Title = {Minimal Pairs and Complete Problems},
Year = {1990}}
@article{Ambos-Spies.Jockusch.ea:84,
Author = {Ambos-Spies, K. and Jockusch, Jr., Carl G. and Shore, Richard A. and Soare, Robert I.},
Journal = {Trans. Amer. Math. Soc.},
Pages = {109--128},
Title = {An algebraic decomposition of the recursively enumerable degrees and the coincidence of several degree classes with the promptly simple degrees},
Volume = {281},
Year = {1984}}
@article{Ambos-Spies.Lachlan.ea:93,
Author = {Ambos-Spies, K. and Lachlan, Alistair H. and Soare, Robert I.},
Journal = {Ann. Pure Appl. Logic},
Title = {The continuity of cupping to $\mbox{\bfseries 0}'$},
Year = {1993}}
@unpublished{Ambos-Spies.Lempp.ea:91,
Author = {Ambos-Spies, K. and Lempp, S. and Lerman, M.},
Note = {To appear in Proceedings of the 9th International Congress of Logic, Methodology and Philosophy of Science, Uppsala, 1991},
Title = {Lattice embeddings into the r. e. degrees preserving 1},
Year = {1991}}
@article{Ambos-Spies.Lempp.ea:94,
Author = {Ambos-Spies, K. and Lempp, S. and Lerman, M.},
Journal = {J. London Math. Soc.},
Pages = {1--15},
Title = {Lattice embeddings into the r. e. degrees preserving 0 and 1},
Volume = {49},
Year = {1994}}
@article{Ambos-Spies.Lerman:86,
Author = {Ambos-Spies, K. and Lerman, M.},
Journal = {J. Symbolic Logic},
Pages = {257--272},
Title = {Lattice embeddings into the recursively enumerable degrees},
Volume = {51},
Year = {1986}}
@article{Ambos-Spies.Lerman:89,
Author = {Ambos-Spies, K. and Lerman, M.},
Journal = {J. Symbolic Logic},
Pages = {735--759},
Title = {Lattice embeddings into the recursively enumerable degrees {II}},
Volume = {54},
Year = {1989}}
@proceedings{Ambos-Spies.Muller.ea:90,
Address = {Heidelberg},
Editor = {K. Ambos-Spies and G. H. Muller and Gerald E. Sacks},
Publisher = {Springer--Verlag},
Series = {Lecture Notes in Mathematics},
Title = {Recursion Theory Week, Oberwolfach 1989},
Volume = {1432},
Year = {1990}}
@article{Ambos-Spies.Nies.ea:92,
Author = {Klaus Ambos-Spies and Andre Nies and Richard A. Shore},
Journal = {J. Symbolic Logic},
Pages = {864--874},
Title = {The Theory of the Recursively Enumerable Weak Truth-Table Degrees is Undecidable},
Volume = {57},
Year = {1992}}
@inproceedings{Ambos-Spies.Nies:92,
Author = {Ambos-Spies, K. and Nies, A.},
Booktitle = {STACS 92},
Pages = {209-210},
Publisher = {Springer--Verlag},
Series = {Lecture notes in Computer Science},
Title = {The Theory of the Polynomial Many-0ne Degrees of Recursive Sets is Undecidable},
Year = {1992}}
@article{Ambos-Spies.Nies:92*1,
Author = {Ambos-Spies, K. and Nies, A},
Journal = {Arch. Math. Logic},
Pages = {51-56},
Title = {Cappable recursively enumerable degrees and Post's program},
Volume = {32},
Year = {1992}}
@inproceedings{Ambos-Spies.Nies:92*2,
Author = {Ambos--Spies, K. and Nies, A.},
Booktitle = {STACS 92},
Pages = {209--210},
Publisher = {Springer--Verlag},
Series = {Lecture Notes in Computer Science},
Title = {The theory of polynomial many-one degrees of recursive sets in undecidable},
Volume = {577},
Year = {1992}}
@article{Ambos-Spies.Shore:93,
Author = {Ambos-Spies, K and Shore, R. A.},
Journal = {Ann. Pure Appl. Logic},
Pages = {3-37},
Title = {Undecidability and 1-types in the r.\ e.\ degrees},
Volume = {63},
Year = {1993}}
@article{Ambos-Spies.Soare:89,
Author = {Ambos-Spies, Klaus and Soare, Robert I.},
Coden = {APALD7},
Fjournal = {Annals of Pure and Applied Logic},
Issn = {0168-0072},
Journal = {Ann. Pure Appl. Logic},
Mrclass = {03D25},
Mrnumber = {90k:03042},
Mrrevr = {Steffen Lempp},
Note = {Third Asian Conference on Mathematical Logic (Beijing, 1987)},
Number = {1-2},
Pages = {1--23},
Title = {The recursively enumerable degrees have infinitely many one-types},
Volume = {44},
Year = {1989}}
@phdthesis{Ambos-Spies:80,
Author = {K. Ambos-Spies},
School = {University of Munich},
Title = {On the Structure of the Recursively Enumerable Degrees},
Year = {1980}}
@article{Ambos-Spies:84,
Author = {K. Ambos-Spies},
Journal = {J. Symbolic Logic},
Pages = {586--607},
Title = {An Extension of the Nondiamond Thoerem in Classical and $\alpha$-recursion Theory},
Volume = {49},
Year = {1984}}
@article{Ambos-Spies:84*1,
Author = {K. Ambos-Spies},
Journal = {Trans. Amer. Math. Soc.},
Pages = {507--531},
Title = {On Pairs of Recursively Enumerable Degrees},
Volume = {283},
Year = {1984}}
@incollection{Ambos-Spies:84*2,
Address = {Berlin},
Author = {Ambos-Spies, Klaus},
Booktitle = {Computation and proof theory (Aachen, 1983)},
Mrclass = {03D25},
Mrnumber = {86f:03065},
Mrrevr = {Michael Stob},
Pages = {1--37},
Publisher = {Springer},
Title = {Contiguous r.e.\ degrees},
Year = {1984}}
@article{Ambos-Spies:85,
Author = {K. Ambos-Spies},
Journal = {Z. Math. Logik Grundlag. Math.},
Pages = {461--467},
Title = {Antimitotic Recursively Enumerable Sets},
Volume = {31},
Year = {1985}}
@article{Ambos-Spies:85*1,
Author = {Ambos-Spies, Klaus},
Coden = {AMLGAN},
Fjournal = {Archiv f\"ur Mathematische Logik und Grundlagenforschung},
Issn = {0003-9268},
Journal = {Arch. Math. Logik Grundlag.},
Mrclass = {03D25 (03D30)},
Mrnumber = {87j:03058},
Mrreviewer = {Anne Leggett},
Number = {3-4},
Pages = {109--126},
Title = {Cupping and noncapping in the r.e.\ weak truth table and {T}uring degrees},
Volume = {25},
Year = {1985}}
@article{Ambos-Spies:86,
Author = {Ambos-Spies, Klaus},
Coden = {IFPLAT},
Fjournal = {Information Processing Letters},
Issn = {0020-0190},
Journal = {Inform. Process. Lett.},
Mrclass = {68Q15},
Mrnumber = {88e:68036},
Mrreviewer = {Ronald V. Book},
Number = {3},
Pages = {113--117},
Title = {Inhomogeneities in the polynomial-time degrees: the degrees of super sparse sets},
Volume = {22},
Year = {1986}}
@article{Ambos-Spies:89,
Author = {Ambos-Spies, K. Soare, R.I.},
Journal = {Ann. Pure Appl. Logic},
Pages = {1-23},
Title = {The recursively enumerable degrees have infinitely many one types},
Volume = {44},
Year = {1989}}
@unpublished{Arslanov.LaForte.ea:95,
Author = {Marat M. Arslanov and Geoffrey L. LaForte and Theodore A. Slaman},
Note = {Preprint},
Title = {Relative Enumerability in the Difference Hierarchy},
Year = {1995}}
@unpublished{Arslanov.Lempp.ea:nd,
Author = {Arslanov, M. and Lempp, S. and Shore, R. A.},
Journal = {Ann. Pure Appl. Logic},
Note = {to appear},
Title = {Interpolating $d$-r.\ e.\ and REA degrees between r.\ e.\ degrees}}
@unpublished{Arslanov.Lempp.ea:nd*1,
Author = {Arslanov, M. and Lempp, S. and Shore, R. A.},
Journal = {Logic Year at Leeds},
Note = {to appear},
Title = {On isolating r.e. and isolated d-r.e. degrees}}
@article{Arslanov:85,
Author = {Arslanov, M. M.},
Journal = {Dokl. Nauk. SSSR},
Pages = {270--273},
Title = {Structural properties of the degrees below $0'$},
Year = {1985}}
@article{Ash.Jockusch.ea:90,
Author = {Ash, C. J. and Jockusch, Jr., Carl G. and Knight, J. F.},
Journal = {Trans. Amer. Math. Soc.},
Pages = {573--599},
Title = {Jumps of Orders},
Volume = {319},
Year = {1990}}
@article{Ash.Knight.ea:93,
Author = {Ash, C. J. and Knight, Julia F. and Slaman, Theodore A.},
Journal = {Fund. Math.},
Pages = {147--161},
Title = {Relatively recursive expansions {I}{I}},
Volume = {142},
Year = {1993}}
@article{Ash:86,
Author = {Ash, C.J.},
Journal = {Ann. Pure Appl. Logic},
Pages = {113-135},
Title = {Stability of recursive structures in arithmetical degrees},
Volume = {32},
Year = {1986}}
@article{Ash:90,
Author = {Ash, C. J.},
Journal = {Ann. Pure Appl. Logic},
Pages = {99-119},
Title = {Labelling systems and r.e. structures},
Volume = {47},
Year = {1990}}
@article{Avigad:96,
Author = {Avigad, Jeremy},
Coden = {APALD7},
Fjournal = {Annals of Pure and Applied Logic},
Issn = {0168-0072},
Journal = {Ann. Pure Appl. Logic},
Number = {2},
Pages = {165--191},
Title = {Formalizing forcing arguments in subsystems of second-order arithmetic},
Volume = {82},
Year = {1996}}
@article{Baker.Gill.ea:75,
Author = {T. Baker and J. Gill and R. Solovay},
Journal = {SIAM Journal on Computing},
Number = {4},
Pages = {431--442},
Title = {Relativizations of the {$\mathcal{P} \mathrel{=?} \mathcal{NP}$} Question},
Volume = {4},
Year = {1975}}
@book{Balcazar.Daz.ea:88,
Address = {Heidelberg},
Author = {J. L. {Balc{\'a}zar} and J. {D\'{\i}az} and J. {Gabarr{\'o}}},
Publisher = {Springer--Verlag},
Series = {EATCS Monographs on Theoretical Computer Science},
Title = {Structural Complexity {I}},
Volume = {11},
Year = {1988}}
@book{Barwise.Etchemendy:93,
Author = {Jon Barwise and John Etchemendy},
Publisher = {Center for the study of Language and Information},
Title = {The language of first-order logic},
Year = {1993}}
@book{Barwise.Etchemendy:95,
Author = {Jon Barwise and John Etchemendy},
Publisher = {Center for the study of Language and Information},
Title = {Turing's World 3.0},
Year = {1995}}
@article{Barwise:73,
Author = {Barwise, Jon},
Booktitle = {Studies in model theory},
Mrclass = {02B25 (02H10)},
Mrnumber = {49 #7116},
Mrrevr = {Nigel J. Cutland},
Pages = {5--34. MAA Studies in Math., Vol. 8},
Publisher = {Math. Assoc. Amer., Buffalo, N.Y.},
Title = {Back and forth through infinitary logic},
Year = {1973}}
@book{Barwise:75,
Address = {Heidelberg},
Author = {Barwise, J.},
Publisher = {Springer--Verlag},
Title = {Admissible Sets and Structures},
Year = {1975}}
@article{Bean:76,
Author = {D. R. Bean},
Journal = {J. Symbolic Logic},
Pages = {496--480},
Title = {Effective Coloration},
Volume = {41},
Year = {1976}}
@article{Bean:76*1,
Author = {Dwight Bean},
Journal = {Proc. Amer. Math. Soc.},
Pages = {385--394},
Title = {Recursive {E}ulerian and {H}amiltonian Paths},
Volume = {55},
Year = {1976}}
@article{Beigel.Gasarch.ea:89,
Author = {Richard Beigel and William I. Gasarch and Louise Hay},
Journal = {Arch. Math. Logic},
Number = {1},
Pages = {69--84},
Title = {Bounded Query Classes and The Difference Hierarchy},
Volume = {29},
Year = {1989}}
@article{Bendixson:83,
Author = {Ivar Bendixson},
Journal = {Acta Math.},
Pages = {415--429},
Title = {Quelques theor{\`e}mes de la th{\'e}orie des ensembles de points},
Volume = {2},
Year = {1883}}
@unpublished{Bickford.Mills:nd,
Author = {M. Bickford and C.F. Mills},
Note = {To appear in the JSL (supposedly but no way by this time)},
Title = {Lowness properties of r.e.\ sets}}
@article{Birkhoff:48,
Address = {New York},
Author = {Birkhoff, G.},
Journal = {Amer. Math. Soc.},
Title = {Lattice Theory},
Volume = {Colloquium Publications},
Year = {1948}}
@inproceedings{Blass.Hirst.ea:87,
Author = {Andreas R. Blass and Jeffry L. Hirst and Stephen G. Simpson},
Booktitle = {Logic and Combinatorics},
Pages = {89--124},
Publisher = {American Mathematical Society},
Series = {Contemporary Mathematics},
Title = {Logical Analysis of Some Theorems of Combinatorics and Topological Dynamics},
Volume = {65},
Year = {1987}}
@article{Blum.Marques:73,
Author = {M. Blum and I. Marques},
Journal = {J. Symbolic Logic},
Pages = {579--593},
Title = {On Computational Complexity of Recursively Enumerable Sets},
Volume = {38},
Year = {1973}}
@book{Bollobas:98,
Address = {New York},
Author = {Bollob{\'a}s, B{\'e}la},
Isbn = {0-387-98488-7},
Mrclass = {05-01 (05-02 05Cxx)},
Mrnumber = {99h:05001},
Mrrevr = {Jerrold W. Grossman},
Pages = {xiv+394},
Publisher = {Springer-Verlag},
Title = {Modern graph theory},
Year = {1998}}
@incollection{Bonnet.Pouzet:82,
Address = {Dordrecht},
Author = {Bonnet, R. and Pouzet, M.},
Booktitle = {Ordered sets (Banff, Alta., 1981)},
Mrclass = {06A10 (04A10 06A05)},
Mrnumber = {83h:06004},
Mrrevr = {Tadashi Ohkuma},
Pages = {125--170},
Publisher = {Reidel},
Title = {Linear extensions of ordered sets},
Year = {1982}}
@article{Boolos.Putnam:68,
Author = {Boolos, George and Putnam, Hillary},
Journal = {J. Symbolic Logic},
Pages = {497--513},
Title = {Degrees of unsolvability of constructible sets of integers},
Volume = {33},
Year = {1968}}
@article{Boone.Rogers:66,
Author = {Boone, W. W. and Rogers, Jr. H.},
Journal = {Math. Scand.},
Pages = {185-192},
Title = {On a problem of J.H. C. Whitehead and a problem of Alonzo Church,},
Volume = {19},
Year = {1966}}
@article{Boone:66,
Author = {Boone, W.W.},
Journal = {Ann. of Math. (2)},
Pages = {49-84},
Title = {Word problems and recursively enumerable degrees of unsolvability, a sequel on finitely presented groups},
Volume = {84},
Year = {1966}}
@inproceedings{Brackin:87,
Author = {S. H. Brackin},
Booktitle = {Logic and Combinatorics},
Pages = {169--178},
Publisher = {American Mathematical Society},
Series = {Contemporary Mathematics},
Title = {A Summary of {R}amsey-type Theorems and their Provability in Weak Formal Systems},
Volume = {65},
Year = {1987}}
@article{Brown.Simpson:93,
Author = {Brown, D. K. and Simpson, Stephen G.},
Journal = {J. Symbolic Logic},
Key = {Brown-Simpson:BCT},
Number = {2},
Pages = {557--578},
Title = {The {B}aire category theorem in weak subsystems of second-order arithmetic},
Volume = {58},
Year = {1993}}
@phdthesis{Brown:87,
Address = {University Park, PA, USA},
Author = {Brown, D. K.},
School = {The Pennsylvania State University},
Title = {Functional analysis in weak subsystems of second order arithmetic},
Year = {1987}}
@article{Buchi:60,
Author = {J. R. B{\"u}chi},
Journal = {Z. Math. Logik Grundlag. Math.},
Pages = {66--92},
Title = {Weak Second Order Arithmetic and Finite Automata},
Volume = {6},
Year = {1960}}
@inproceedings{Buchi:62,
Author = {J. R. B{\"u}chi},
Booktitle = {Proc. of the International Congress on logic, Math, and Philosophy of Science (1960)},
Publisher = {Standford University Press},
Title = {On a decision method in restricted second-order arithmetic},
Year = {1962}}
@article{Burr:84,
Author = {Stefan A. Burr},
Journal = {Discrete Math.},
Pages = {171--177},
Title = {Some undecidable problems involving the edge-coloring and vertex-coloring of graphs},
Volume = {50},
Year = {1984}}
@article{Burris.Sankappanavar:75,
Author = {Burris, S. and Sankappanavar, H. P.},
Journal = {Algebra Universalis},
Pages = {163-177},
Title = {Lattice theoretic decision problems in universal algebra},
Volume = {5},
Year = {1975}}
@book{Burris.Sankappanavar:81,
Address = {Berlin},
Author = {Burris, S. and Sankappanavar, H. P.},
Publisher = {Springer--Verlag},
Title = {A course in universal algebra},
Year = {1981}}
@article{Calhoun.Slaman:nd,
Author = {Calhoun, William C. and Slaman, Theodore A.},
Journal = {J. Symbolic Logic},
Note = {To appear},
Title = {The {$\Pi^0_2$} $e$-Degrees are not Dense}}
@article{Calude.Nies:98,
Author = {C. Calude and A. Nies},
Journal = {J. Univ. Comp. Sc.},
Note = {to appear},
Title = {Chaitin $\Omega$ Numbers and Strong Reducibilities},
Year = {1998}}
@article{Carlson.Simpson:84,
Author = {Timothy J. Carlson and Stephen G. Simpson},
Journal = {Adv. in Math.},
Pages = {265--290},
Title = {A Dual Form of {R}amsey's {T}heorem},
Volume = {53},
Year = {1984}}
@article{Carstens.Pappinghaus:83,
Author = {Hans-Georg Carstens and Peter Pappinghaus},
Journal = {Ann. Pure Appl. Logic},
Pages = {19--45},
Title = {Recursive Coloration of Countable Graphs},
Volume = {25},
Year = {1983}}
@inproceedings{Carstens.Pappinghaus:84,
Address = {Heidelberg},
Author = {Hans-Georg Carstens and Peter Pappinghaus},
Booktitle = {Computation and Proof Theory},
Pages = {39--62},
Publisher = {Springer--Verlag},
Series = {Lecture Notes in Mathematics},
Title = {Abstract Constructions of Counterexamples in Recursive Graph Theory},
Volume = {1104},
Year = {1984}}
@incollection{Carstens.Pappinghaus:84*1,
Address = {Heidelberg},
Author = {Hans-Georg Carstens and Peter Pappinghaus},
Booktitle = {Decision Problems and Complexity},
Editor = {Borger and Hasenjaeger and Rodding},
Pages = {162--182},
Publisher = {Springer--Verlag},
Series = {Lecture Notes in Computer Science},
Title = {Extensible Algorithms},
Volume = {171},
Year = {1984}}
@article{Case.Smith:83,
Annote = {Was in STOC78},
Author = {J. Case and C. Smith},
Journal = {Theoret. Comput. Sci.},
Pages = {193--220},
Title = {Comparison of Identification Criteria for Machine Inductive Inference},
Volume = {25},
Year = {1983}}
@article{Case:71,
Author = {J. Case},
Journal = {Ann. Math. Logic},
Pages = {419--439},
Title = {Enumeration Reducibility and Partial Degrees},
Volume = {2},
Year = {1971}}
@article{Cenzer.Downey.ea:93,
Author = {D. Cenzer and R. Downey and Jockusch, Jr., Carl G. and R. A. Shore},
Journal = {Ann. Pure Appl. Logic},
Pages = {79-139},
Title = {Countable thin $\Pi ^0_1$ clases},
Volume = {597},
Year = {1993}}
@book{Chang.Keisler:73,
Address = {Amsterdam},
Author = {Chang, C. C. and Keisler, H. J.},
Publisher = {North--Holland Publishing Co.},
Title = {Model Theory},
Year = {1973}}
@article{Chong.Mourad:90,
Author = {Chong, C.T. and Mourad, K. J.},
Journal = {Ann. Pure Appl. Logic},
Pages = {227-235},
Title = {The degree of a $\sum_n$-cut},
Volume = {48},
Year = {1990}}
@article{Chong.Mourad:92,
Author = {Chong, C. T. and Mourad, K. J.},
Journal = {Trans. Amer. Math. Soc.},
Pages = {349--363},
Title = {${\Sigma}_n$ definability without ${\Sigma}_n$ induction},
Volume = {334},
Year = {1992}}
@proceedings{Chong:89,
Author = {Chong, C. T.},
Editor = {J. Shinoda, T. A. Slaman and T. Tugu\'{e}},
Number = {1388},
Pages = {1-16},
Publisher = {Springer--Verlag},
Series = {Mathematical Logic and Applications (Proceedings, Kyoto 1987)},
Title = {Recursively enumerable sets in models of $\sum_2$-collection},
Year = {1989}}
@article{Church:36,
Author = {Church, Alonzo},
Journal = {J. Symbolic Logic},
Pages = {40--41},
Title = {A note on the {E}ntscheidungsproblem},
Volume = {1},
Year = {1936}}
@article{Church:36*1,
Author = {Church, Alonzo},
Journal = {Amer. J. Math.},
Pages = {345--363},
Title = {An unsolvable problem of elementary number theory},
Volume = {58},
Year = {1936}}
@article{Clapham:64,
Author = {Clapham, C. R., J.},
Journal = {Proc. London Math. Soc. (3)},
Pages = {633-676},
Title = {Finitely presented groups with word problems of arbitrary degrees of insolubility},
Volume = {14},
Year = {1964}}
@inproceedings{Clote:84,
Address = {Heidelberg},
Author = {Peter Clote},
Booktitle = {Model Theory of Algebra and Arithmetic},
Pages = {92--107},
Publisher = {Springer--Verlag},
Series = {Lecture Notes in Mathematics},
Title = {Weak partition relations, finite games, and independence results in Peano arithmetic},
Volume = {834},
Year = {1984}}
@article{Clote:84*1,
Author = {Peter Clote},
Journal = {J. Symbolic Logic},
Pages = {376--400},
Title = {A recursion-theoretic analysis of the clopen {R}amsey {T}heorem},
Volume = {49},
Year = {1984}}
@book{Cohen:66,
Author = {Cohen, Paul J.},
Publisher = {W. A. Benjamin},
Title = {Set Theory and the Continuum Hypothesis},
Year = {1966}}
@inproceedings{Cook:71,
Author = {Cook, S. A.},
Booktitle = {Proc. Third Annual ACM Sympos. on Theory of Compt.},
Pages = {151--158},
Title = {The Complexity of Theorem Proving Procedures},
Year = {1971}}
@article{Cooper.Copestake:88,
Author = {Cooper, S. Barry and Copestake, C. S.},
Journal = {Z. Math. Logik Grundlag. Math.},
Pages = {491--522},
Title = {Properly ${\Sigma}_2$ enumeration degrees},
Volume = {34},
Year = {1988}}
@article{Cooper.Harrington.ea:91,
Author = {Cooper, S. Barry and Harrington, Leo A. and Lachlan, Alistair H. and Lempp, Steffen and Soare, Robert I.},
Journal = {Ann. Pure Appl. Logic},
Pages = {125--151},
Title = {The d.r.e. degrees are not dense},
Volume = {55},
Year = {1991}}
@article{Cooper.Lempp.ea:89,
Author = {Cooper, S. B. and Lempp, S. and Watson, P.},
Journal = {Israel J. Math.},
Number = {2},
Pages = {137-152},
Title = {Weak density and cupping in the d-r.e. degrees},
Volume = {67},
Year = {1989}}
@article{Cooper.McEnvoy:85,
Author = {S. Barry Cooper and K. McEnvoy},
Journal = {J. Symbolic Logic},
Pages = {839--848},
Title = {On Minimal Pairs of Enumeration Degrees},
Volume = {50},
Year = {1985}}
@unpublished{Cooper.Sorbi:95,
Author = {S. Barry Cooper and Andrea Sorbi},
Note = {Preprint},
Title = {Noncappable Enumeration Degrees Below $\mathbf{0}'_e$},
Year = {1995}}
@unpublished{Cooper.Sui.ea:94,
Author = {Cooper, S. Barry and Sui, Y. and Yi, X.},
Note = {Unpublished},
Title = {Minimal pairs and the {Slaman--Soare} phenomenon},
Year = {1994}}
@unpublished{Cooper.Yi:nd,
Author = {Cooper, Barry and Yi, Xiaoding},
Note = {In preparation},
Title = {Non-splitting and the high/low hierarchy}}
@phdthesis{Cooper:71,
Author = {S. Barry Cooper},
School = {Leicester University},
Title = {Degrees of Unsolvability},
Year = {1971}}
@article{Cooper:73,
Author = {Cooper, S. B.},
Journal = {J. Symbolic Logic},
Pages = {249-271},
Title = {Minimal degrees and the jump operator},
Volume = {38},
Year = {1973}}
@article{Cooper:74,
Author = {Cooper, S. Barry},
Journal = {J. Symbolic Logic},
Pages = {655--660},
Title = {Minimal Pairs and High Recursively Enumerable Degrees},
Volume = {39},
Year = {1974}}
@unpublished{Cooper:74*1,
Author = {S. Barry Cooper},
Note = {Handwritten notes},
Title = {On a Theorem of C.~E.~M.~Yates},
Year = {1974}}
@article{Cooper:82,
Author = {Cooper, S. B.},
Journal = {J. Symbolic Logic},
Pages = {854--859},
Title = {Partial degrees and the density problem},
Volume = {47},
Year = {1982}}
@article{Cooper:87,
Author = {S. Barry Cooper},
Journal = {Z. Math. Logik Grundlag. Math.},
Pages = {537--560},
Title = {Enumeration reducibility using bounded information: counting minimal covers},
Volume = {33},
Year = {1987}}
@article{Cooper:89,
Author = {S. Barry Cooper},
Journal = {J. Symbolic Logic},
Pages = {324--353},
Title = {A Jump Class of Noncappable Degrees},
Volume = {54},
Year = {1989}}
@article{Cooper:90,
Author = {Cooper, S. B.},
Journal = {Bull. Amer. Math. Soc.},
Pages = {151-158},
Title = {The jump is definable in the structure of the degrees of unsolvability},
Volume = {23},
Year = {1990}}
@inproceedings{Cooper:90*1,
Address = {Heidelberg},
Author = {Cooper, S. B.},
Booktitle = {Recursion Theory Week, Oberwolfach 1989},
Editor = {K. Ambos-Spies and G. M{\"u}ller and Gerald E. Sacks},
Pages = {57--110},
Publisher = {Springer--Verlag},
Series = {Lecture Notes in Mathematics},
Title = {Enumeration reducibility, nondeterministic computations and relative computability of partial functions},
Volume = {1432},
Year = {1990}}
@inproceedings{Cooper:91,
Author = {Cooper, S. B.},
Booktitle = {Logic Colloquium '90},
Editor = {J. Oikkonen and J. V\"a\"an\"anen},
Pages = {25--45},
Series = {Lecture Notes in Logic},
Title = {Definability and Global Degree Theory},
Volume = {2},
Year = {1991}}
@article{Cooper:92,
Author = {S. Barry Cooper},
Journal = {Proc. Amer. Math. Soc.},
Pages = {461--472},
Title = {A Splitting Theorem for the $n$-Recursively Enumerable Degrees},
Volume = {115},
Year = {1992}}
@proceedings{Cooper:94,
Author = {Cooper, S. B.},
Editors = {Prawitz, D. and Westerst\aahl, D},
Publisher = {Kluwer Academic Publishers},
Series = {Proceedings of the International Congress for Logic, Methodology and the Philosophy of Science (Uppsala, 1991)},
Title = {Rigidity and definability in the noncomputable universe},
Year = {1994}}
@incollection{Cooper:96,
Address = {Berlin},
Author = {Cooper, S. Barry},
Booktitle = {Algebra and analysis (Kazan, 1994)},
Mrclass = {03D25 (03D30 03D35)},
Mrnumber = {98i:03056},
Mrrevr = {Peter Cholak},
Pages = {41--55},
Publisher = {de Gruyter},
Title = {Discontinuous phenomena and {T}uring definability},
Year = {1996}}
@incollection{Cooper:99,
Author = {S.B. Cooper},
Booktitle = {Handbook of computability theory},
Chapter = {4},
Editor = {Edward R. Griffor},
Pages = {121--154},
Publisher = {North--Holland Publishing Co.},
Series = {Studies in Logic},
Title = {Local degree theory},
Volume = {140},
Year = {1999}}
@unpublished{Cooper:nd,
Author = {S. Barry Cooper},
Note = {To appear},
Title = {The Density of the Low$_2$ $n$-Recursively Enumerable Degrees}}
@book{Crossley.Remmel.ea:93,
Address = {Boston Mass.},
Editor = {J.N.C. Crossley and J. Remmel and Shore, R.A. and M. Sweedler},
Publisher = {Birk\" auser},
Title = {Logical Methods: In Honor of Anil Nerode's Sixtieth Birthday},
Year = {1993}}
@article{Daley:86,
Author = {R. P. Daley},
Journal = {Lecture Notes in Computer Science},
Pages = {73--82},
Title = {Inductive Inference Hierarchies: Probabilistic vs Pluralistic},
Volume = {215},
Year = {1986}}
@article{Davis.Putnam.ea:61,
Author = {Martin Davis and Hillary Putnam and Julia Robinson},
Journal = {Ann. of Math. (2)},
Pages = {425--436},
Title = {The decision problem for exponential {D}iophantine equations},
Volume = {74},
Year = {1961}}
@book{Davis:65,
Author = {Davis, M.},
Publisher = {Raven Press, Hewlett, N.Y.},
Title = {The undecidable. Basic papers on undecidable propositions, unsolvable problems and computable functions},
Year = {1965}}
@article{Dawar.Lindell.ea:nd,
Author = {Anuj Dawar and Steven Lindell and Scott Weinstein},
Journal = {Inform. and Control},
Title = {Infinitary Logic and Inductive Definability over Finite Structures}}
@incollection{Degtev:81,
Author = {A. Degtev},
Booktitle = {Algebraic Systems},
Editor = {D. I. Moldavanskii},
Note = {(in Russian)},
Pages = {88--99},
Publisher = {Wadsworth International},
Title = {$(m,n)$-computable sets},
Year = {1981}}
@article{Dehn:12,
Author = {Dehn, M.},
Journal = {Math. Ann.},
Pages = {116-144},
Title = {\"{U}ber unendliche diskontinuierliche Gruppen},
Volume = {71},
Year = {1912}}
@article{Dekker.Myhill:58,
Author = {Dekker, J. and Myhill, J.},
Journal = {Canad. J. Math.},
Pages = {357--373},
Title = {Retraceable sets},
Volume = {10},
Year = {1958}}
@article{Dekker:54,
Author = {J. C. E. Dekker},
Journal = {Proc. Amer. Math. Soc.},
Pages = {791--796},
Title = {A Theorem on Hypersimple Sets},
Volume = {5},
Year = {1954}}
@article{Dekker:81,
Author = {J. C. E. Dekker},
Journal = {J. Symbolic Logic},
Pages = {539--571},
Title = {Twilight Graphs},
Volume = {46},
Year = {1981}}
@article{Denisov:72,
Author = {S. D. Denisov},
Journal = {Algebra and Logic},
Pages = {418--443},
Title = {The structure of the uppersemilattice of recursively enumerable $m$-degrees and related questions, {I}},
Volume = {17},
Year = {1972}}
@book{Diestel:97,
Address = {New York},
Author = {Diestel, Reinhard},
Isbn = {0-387-98210-8},
Mrclass = {05-01},
Mrnumber = {1 448 665},
Note = {Translated from the 1996 German original},
Pages = {xiv+289},
Publisher = {Springer-Verlag},
Title = {Graph theory},
Year = {1997}}
@unpublished{Downey.Fellows:nd,
Author = {R. G. Downey and M. Fellows},
Note = {In preparation},
Title = {Fixed Parameter Tractability and Intractability: A Survey}}
@article{Downey.Harrington:96,
Author = {Downey, Rod and Harrington, Leo},
Coden = {APALD7},
Fjournal = {Annals of Pure and Applied Logic},
Issn = {0168-0072},
Journal = {Ann. Pure Appl. Logic},
Number = {3},
Pages = {277--289},
Title = {There is no fat orbit},
Volume = {80},
Year = {1996}}
@inproceedings{Downey.Jockusch.ea:90,
Address = {Heidelberg},
Author = {R. G. Downey and Jockusch, Jr., Carl G. and M. Stob},
Booktitle = {Recursion Theory Week, Oberwolfach 1989},
Editor = {K. Ambos-Spies and G. H. Muller and Gerald E. Sacks},
Pages = {141--174},
Publisher = {Springer--Verlag},
Series = {Lecture Notes in Mathematics},
Title = {Array Nonrecursive Sets and Multiple Permitting Arguments},
Volume = {1432},
Year = {1990}}
@article{Downey.Jockusch:87,
Author = {R. G. Downey and Jockusch, Jr., Carl G.},
Journal = {Trans. Amer. Math. Soc.},
Pages = {103--137},
Title = {{$\mathbf{T}$}-degrees, Jump Classes, and Strong Reducibilities},
Volume = {30},
Year = {1987}}
@article{Downey.Knight:92,
Author = {Downey, R. G. and Knight, J.},
Journal = {Proc. Amer. Math. Soc.},
Pages = {545-552},
Title = {Orderings with $\alpha$th jump degree $\mathbf{0}^{(\alpha)}$},
Volume = {114},
Year = {1992}}
@unpublished{Downey.Lempp.ea:nd,
Author = {Rodney G. Downey and Steffen Lempp and Richard A. Shore},
Note = {To appear},
Title = {Highness and Bounding Minimal Pairs}}
@article{Downey.Lempp:97,
Author = {Downey, Rodney G. and Lempp, Steffen},
Coden = {JSYLA6},
Fjournal = {The Journal of Symbolic Logic},
Issn = {0022-4812},
Journal = {J. Symbolic Logic},
Number = {4},
Pages = {1215--1240},
Title = {Contiguity and distributivity in the enumerable {T}uring degrees},
Volume = {62},
Year = {1997}}
@article{Downey.Lempp:nd,
Author = {R. G. Downey and Steffen Lempp},
Journal = {J. Symbolic Logic},
Note = {To appear},
Title = {Contiguity and Distributivity in the Computably Enumerable Turing Degrees}}
@article{Downey.Moses:89,
Author = {Rodney Downey and Michael Moses},
Journal = {Z. Math. Logik Grundlag. Math.},
Pages = {237--246},
Title = {On choice sets and strongly non-trivial self-embeddings of recursive linear orders},
Volume = {35},
Year = {1989}}
@article{Downey.Remmel.ea:87,
Author = {R. G. Downey and J. B. Remmel and L. V. Welch},
Journal = {Trans. Amer. Math. Soc.},
Pages = {683--714},
Title = {Degrees of Splittings and Bases of Recursively Enumerable Subspaces},
Volume = {302},
Year = {1987}}
@article{Downey.Remmel:89,
Author = {R. G. Downey and J. B. Remmel},
Journal = {Ann. Pure Appl. Logic},
Pages = {105--125},
Title = {Classification of Degree Classes Associated with Recursively Enumerable Subspaces},
Volume = {42},
Year = {1989}}
@article{Downey.Shore:95,
Author = {R. G. Downey and Richard A. Shore},
Journal = {J. Symbolic Logic},
Number = {3},
Pages = {727--756},
Title = {Degree Theoretic Definitions of Low$_2$ Recursively Enumerable Sets},
Volume = {60},
Year = {1995}}
@article{Downey.Shore:96,
Author = {R. G. Downey and Richard A. Shore},
Journal = {Israel J. Math.},
Pages = {221-246},
Title = {Lattice Embedding below a NonLow$_2$ Recursively Enumerable Degree},
Volume = {94},
Year = {1996}}
@unpublished{Downey.Shore:nd,
Author = {R. G. Downey and Richard A. Shore},
Note = {To appear},
Title = {Decomposition and Infima in the Recursively Enumerable Degrees}}
@unpublished{Downey.Shore:nd*2,
Author = {Downey, R. and Shore, R. A.},
Journal = {Israel J. Math.},
Note = {to appear},
Title = {Lattice embeddings below a nonlow$_2$ recursively enumerable degree}}
@article{Downey.Slaman:89,
Author = {Downey, R. G. and Slaman, Theodore A.},
Journal = {Ann. Pure Appl. Logic},
Pages = {119--152},
Title = {Completely mitotic r. e. degrees},
Volume = {41},
Year = {1989}}
@article{Downey.Slaman:92,
Author = {Downey, R. G. and Slaman, Theodore A.},
Journal = {Ann. Pure Appl. Logic},
Pages = {221--237},
Title = {On co-simple isols and their intersection types},
Volume = {56},
Year = {1992}}
@article{Downey.Stob:86,
Author = {R. G. Downey and M. Stob},
Journal = {Ann. Pure Appl. Logic},
Pages = {205--236},
Title = {Structural Interactions of the {$\mathbf{T}$}- and W-Degrees},
Volume = {31},
Year = {1986}}
@inproceedings{Downey.Stob:90,
Author = {R. G. Downey and M. Stob},
Booktitle = {Proceedings of the Fourth Asian Logic Conference},
Pages = {75--87},
Publisher = {CSSK Centre},
Title = {Automorphisms and Splittings of Recursively Enumerable Sets},
Year = {1990}}
@article{Downey.Stob:91,
Author = {R. G. Downey and M. Stob},
Journal = {Z. Math. Logik Grundlag. Math.},
Pages = {113--120},
Title = {Jumps of Hemimaximal Sets},
Volume = {37},
Year = {1991}}
@article{Downey.Stob:92,
Author = {R. G. Downey and M. Stob},
Journal = {Adv. in Math.},
Pages = {237--265},
Title = {Automorphisms of the Lattice of Recursively Enumerable Sets: Orbits},
Volume = {92},
Year = {1992}}
@article{Downey.Stob:93,
Author = {Downey, Rod and Stob, Michael},
Coden = {APALD7},
Fjournal = {Annals of Pure and Applied Logic},
Issn = {0168-0072},
Journal = {Ann. Pure Appl. Logic},
Mrclass = {03D25},
Mrnumber = {95c:03099},
Mrrevr = {E. Herrmann},
Number = {1},
Pages = {106 pp},
Title = {Splitting theorems in recursion theory},
Volume = {65},
Year = {1993}}
@article{Downey.Stob:93*1,
Author = {Downey, Rod and Stob, Michael},
Coden = {APALD7},
Fjournal = {Annals of Pure and Applied Logic},
Issn = {0168-0072},
Journal = {Ann. Pure Appl. Logic},
Mrclass = {03D25},
Mrnumber = {94d:03082},
Mrreviewer = {Xi Zhong Zheng},
Note = {Fourth Asian Logic Conference (Tokyo, 1990)},
Number = {3},
Pages = {175--199},
Title = {Friedberg splittings of recursively enumerable sets},
Volume = {59},
Year = {1993}}
@unpublished{Downey.Stob:nd,
Author = {R. G. Downey and M. Stob},
Note = {To appear},
Title = {Minimal Pairs in Lower Cones}}
@article{Downey.Welch:86,
Author = {R. G. Downey and L. V. Welch},
Journal = {J. Symbolic Logic},
Pages = {88--109},
Title = {Splitting Properties of Recursively Enumerable Sets and Degrees},
Volume = {51},
Year = {1986}}
@article{Downey:85,
Author = {R. G. Downey},
Journal = {Trans. Amer. Math. Soc.},
Pages = {337--351},
Title = {The Degrees of R. E. Sets Without the Universal Splitting Property},
Volume = {291},
Year = {1985}}
@article{Downey:87,
Author = {R. G. Downey},
Journal = {Pacific J. Math.},
Pages = {299--319},
Title = {Subsets of Hypersimple Sets},
Volume = {127},
Year = {1987}}
@article{Downey:87*1,
Author = {R. G. Downey},
Journal = {Illinois J. Math.},
Pages = {419--427},
Title = {{$\Delta^0_2$} Degrees and Transfer Theorems},
Volume = {31},
Year = {1987}}
@article{Downey:87*2,
Author = {Downey, R. G.},
Coden = {AMLGAN},
Fjournal = {Archiv f\"ur Mathematische Logik und Grundlagenforschung},
Issn = {0003-9268},
Journal = {Arch. Math. Logik Grundlag.},
Mrclass = {03D25 (03D30)},
Mrnumber = {88h:03058},
Mrrevr = {C. G. Jockusch, Jr.},
Number = {3-4},
Pages = {127--136},
Title = {Localization of a theorem of {A}mbos-{S}pies and the strong antisplitting property},
Volume = {26},
Year = {1987}}
@article{Downey:89,
Author = {R. G. Downey},
Journal = {Ann. Pure Appl. Logic},
Pages = {1--27},
Title = {Intervals and Sublattices of the Recursively Enumerable {$\mathbf{T}$}- and W-Degrees, Part {I}: Density},
Volume = {49},
Year = {1989}}
@article{Downey:89*1,
Author = {R. G. Downey},
Journal = {Bull. London Math. Soc.},
Pages = {43--50},
Title = {$D$-Recursively Enumerable Degrees and the Nondiamond Theorem},
Volume = {21},
Year = {1989}}
@article{Downey:90,
Author = {R. G. Downey},
Journal = {Ann. Pure Appl. Logic},
Pages = {97--119},
Title = {Lattice Nonembedding and Intial Segments of the R. E. Degrees},
Volume = {49},
Year = {1990}}
@inproceedings{Downey:90*1,
Address = {Heidelberg},
Author = {R. G. Downey},
Booktitle = {Recursion Theory Week, Oberwolfach 1989},
Editor = {K. Ambos-Spies and G. H. Muller and Gerald E. Sacks},
Pages = {1--22},
Publisher = {Springer--Verlag},
Series = {Lecture Notes in Mathematics},
Title = {Notes on the $\mathbf{0}'''$ Priority Method with Special Attention to Density Results},
Volume = {1432},
Year = {1990}}
@article{Downey:93,
Author = {R. G. Downey},
Journal = {Illinois J. Math.},
Note = {To appear},
Title = {Array Nonrecursive Degrees and Lattice Embeddings of the Diamond},
Year = {1993}}
@incollection{Downey:nd,
Author = {Rodney Downey},
Booktitle = {Handbook of Recursive Algebra},
Editor = {Ershov and Goncharov and Nerode and Remmel},
Publisher = {North--Holland Publishing Co.},
Title = {Recursion Theory and Linear Orderings}}
@book{Ebbinghaus.Flum:95,
Address = {Heidelberg},
Author = {H. Ebbinghaus and J. Flum},
Publisher = {Springer--Verlag},
Series = {Perspectives in Mathematical Logic, Omega Series},
Title = {Finite Model Thoery},
Year = {1995}}
@proceedings{Ebbinghaus.Muller.ea:85,
Address = {Heidelberg},
Editor = {H.-D. Ebbinghaus and G.~H. Muller and Gerald E. Sacks},
Note = {418 pp.},
Publisher = {Springer--Verlag},
Series = {Lecture Notes in Mathematics},
Title = {Recursion Theory Week},
Volume = {1141},
Year = {1985}}
@article{Ehrenfeucht:69,
Author = {A. Ehrenfeucht},
Journal = {Fund. Math.},
Pages = {129--141},
Title = {An Appliation of Games to the Completeness Theorem for Formalized Theories},
Volume = {49},
Year = {1969}}
@article{Elgot.Rabin:66,
Author = {Calvin C. Elgot and Michael O. Rabin},
Journal = {J. Symbolic Logic},
Number = {2},
Pages = {169--181},
Title = {Decidability and undecidability of extensions of second (first) order theory of (generalized) successor},
Volume = {31},
Year = {1966}}
@article{Elgot:61,
Author = {C. C. Elgot},
Journal = {Trans. Amer. Math. Soc.},
Pages = {21--51},
Title = {Decision problems of finite automata design and related arithmetics},
Volume = {{98}},
Year = {1961}}
@article{Ellentuck:74,
Author = {E. Ellentuck},
Journal = {J. Symbolic Logic},
Pages = {163--165},
Title = {A new proof that analytic sets are {R}amsey},
Volume = {39},
Year = {1974}}
@inproceedings{Epstein.Haas.ea:81,
Address = {Heidelberg},
Author = {Richard L. Epstein and Richard Haas and Richard L. Kramer},
Booktitle = {Logic Year 1979--80},
Pages = {32--48},
Publisher = {Springer--Verlag},
Series = {Lecture Notes in Mathematics},
Title = {Hierarchies of Sets and Degrees Below {${\bf 0}'$}},
Volume = {859},
Year = {1981}}
@article{Epstein:75,
Author = {Epstein, R. L.},
Journal = {Mem. Amer. Math. Soc.},
Title = {Minimal degrees of unsolvability and the full approximation construction},
Volume = {162},
Year = {1975}}
@book{Epstein:79,
Address = {Heidelberg},
Author = {Epstein, R.},
Publisher = {Springer--Verlag},
Series = {Lecture Notes in Mathematics},
Title = {Degrees of Unsolvability: Structure and Theory},
Volume = {759},
Year = {1979}}
@article{Ershov.Lavrov.ea:65,
Author = {Ershov and Lavrov and Taimonv and Taitslin},
Journal = {Russian Math. Surveys},
Title = {The undecidability of certain theories},
Volume = {20},
Year = {1965}}
@article{Ershov.Lavrov.ea:65*1,
Author = {Y. Ershov and I. Lavrov and A. Taimanov and M. Taitslin},
Journal = {Russian Math Surveys},
Pages = {35--105},
Title = {Elementary theories},
Volume = {20},
Year = {1965}}
@article{Ershov.Taitslin:63,
Author = {Yu. Ershov and M. Taitslin},
Journal = {Algebra i Logika},
Pages = {37--41},
Title = {The undecidability of certain theories},
Volume = {2},
Year = {1963}}
@article{Ershov:68,
Author = {Yu. L. Ershov},
Journal = {Algebra i Logika},
Month = {January--February},
Note = {English Translation, Consultants Bureau, NY, pp.~25--43},
Number = {1},
Pages = {47--74},
Title = {A Hierarchy of Sets, {I}},
Volume = {7},
Year = {1968}}
@article{Ershov:68*1,
Author = {Yu. L. Ershov},
Journal = {Algebra i Logika},
Month = {July--August},
Note = {English Translation, Consultants Bureau, NY, pp.~212--232},
Number = {4},
Pages = {15--47},
Title = {A Hierarchy of Sets, {II}},
Volume = {7},
Year = {1968}}
@article{Ershov:70,
Author = {Yu. L. Ershov},
Journal = {Algebra i Logika},
Month = {January--February},
Note = {English Translation, Consultants Bureau, NY, pp.~20--31},
Number = {1},
Pages = {34--51},
Title = {A Hierarchy of Sets, {III}},
Volume = {9},
Year = {1970}}
@article{Ershov:75,
Author = {Ershov, Yu. L.},
Journal = {Algebra i Logika},
Note = {Russian},
Pages = {258-284, 368},
Title = {The upper semilattice of numerations of a finite set},
Volume = {14},
Year = {1975}}
@book{Fagin.Halpern.ea:95,
Address = {Cambridge},
Author = {R. Fagin and J. Y. Halpern and Y. Moses and M. Y. Vardi},
Descriptor = {Wissensbasierter Entwurf, Wissensbasiert, Knowledge-based, Knowledge-Base, Knowledge},
Isbn = {0-262-06162-7},
Publisher = {MIT-Press},
Title = {Reasoning About Knowledge},
Year = {1995}}
@article{Feferman.Vaught:59,
Author = {Feferman and Vaught},
Journal = {Fund. Math.},
Pages = {57--103},
Title = {The first-order properties of algebraic systems},
Volume = {47},
Year = {1959}}
@inproceedings{Feferman:65,
Address = {Amsterdam},
Author = {Feferman, S.},
Booktitle = {The Theory of Models, Proceedings of the 1963 International Symposium at Berkeley},
Editor = {J. W. Addison and L. Henkin and A. Tarski},
Pages = {89--95},
Publisher = {North--Holland Publishing Co.},
Series = {Studies in Logic and the Foundations of Mathematics},
Title = {Some applications of the notions of forcing and generic sets},
Year = {1965}}
@article{Feiner:74,
Author = {L. Feiner},
Journal = {J. Symbolic Logic},
Pages = {365-74},
Title = {Hierarchies of Boolean algebras},
Volume = {35},
Year = {1974}}
@inproceedings{Fejer.Shore:85,
Address = {Heidelberg},
Author = {Fejer, P. A. and Shore, Richard A.},
Booktitle = {Recursion Theory Week},
Editor = {H.-D. Ebbinghaus and G. H. Muller and Gerald E. Sacks},
Pages = {121--140},
Publisher = {Springer--Verlag},
Title = {Embeddings and extensions of embeddings in the r. e. tt- and wtt-degrees},
Year = {1985}}
@inproceedings{Fejer.Soare:81,
Author = {P. A. Fejer and Robert I. Soare},
Booktitle = {Logic Year 1979--80: University of {C}onnecticut},
Pages = {49--62},
Title = {The Plus-Cupping Theorem for the Recursively Enumerable Degrees},
Year = {1981}}
@article{Fejer:82,
Author = {P. A. Fejer},
Journal = {Trans. Amer. Math. Soc.},
Pages = {157--180},
Title = {Branching Degrees Above Low Degrees},
Volume = {273},
Year = {1982}}
@article{Fejer:83,
Author = {P. A. Fejer},
Journal = {Ann. Pure Appl. Logic},
Pages = {113--130},
Title = {The Density of the Nonbranching Degrees},
Volume = {24},
Year = {1983}}
@article{Fejer:89,
Author = {Fejer, P. A.},
Journal = {Z. Math. Logik Grundlag. Math.},
Pages = {3-14},
Title = {Embedding lattices with top preserved below non-GL$_2$ degrees},
Volume = {35},
Year = {1989}}
@proceedings{Fenstad.Gandy.ea:78,
Address = {Amsterdam},
Editor = {Jens Erik Fenstad and R. O. Gandy and Gerald E. Sacks},
Title = {Generalized Recursion Theory {II}},
Year = {1978}}
@proceedings{Fenstad.Gandy.ea:78*1,
Address = {Amsterdam},
Editor = {J. Fenstad and Robin O. Gandy and Gerald E. Sacks},
Note = {417 pp.},
Publisher = {North--Holland Publishing Co.},
Title = {Generalized Recursion Theory},
Year = {1978}}
@article{Fortnow.Gasarch.ea:94,
Annote = {Subsumes the COLT paper by Gasarch and Pleszkoch entitled{\newline} {\it Learning via Queries to an Oracle}},
Author = {L. Fortnow and W. Gasarch and S. Jain and E. Kinber and M. Kummer and S. Kurtz and M. Pleszkoch and T. Slaman and R. Solovay and F. Stephan},
Journal = {Ann. Pure Appl. Logic},
Pages = {21--276},
Title = {Extremes in the Degrees of Inferability},
Volume = {66},
Year = {1994}}
@article{Friedberg.Rogers:59,
Author = {Friedberg, R. M. and Rogers, Jr., H.},
Journal = {Z. Math. Logik Grundlag. Math.},
Pages = {117--125},
Title = {Reducibility and Completeness for Sets of Integers},
Volume = {5},
Year = {1959}}
@article{Friedberg:57,
Author = {Friedberg, R. M.},
Journal = {J. Symbolic Logic},
Pages = {159--160},
Title = {A criterion for completeness of degrees of unsolvability},
Volume = {22},
Year = {1957}}
@article{Friedberg:57*1,
Author = {Friedberg, R. M.},
Journal = {Proc. Nat. Acad. Sci. U.S.A.},
Pages = {236--238},
Title = {Two recursively enumerable sets of incomparable degrees of unsolvability (solution to Post's problem, 1944)},
Volume = {43},
Year = {1957}}
@article{Friedberg:58,
Author = {Friedberg, R. M.},
Journal = {J. Symbolic Logic},
Pages = {309--316},
Title = {Three theorems on recursive enumeration. {I}. Decomposition. {II.} Maximal set. {III.} Enumeration without duplication.},
Volume = {23},
Year = {1958}}
@inproceedings{Friedberg:60,
Author = {Friedberg, R. M.},
Booktitle = {Summaries of talks presented at the summer institute for symbolic logic, 1957, Cornell University},
Note = {second edition},
Organization = {{I}nstitute for {D}efence {A}nalyses},
Pages = {404--406},
Title = {The fine structure of the degrees of unsolvability of recursively enumerable sets},
Year = {1960}}
@inproceedings{Friedman.Robertson.ea:87,
Author = {Harvey Friedman and Neil Robertson and Paul Seymour},
Booktitle = {Logic and Combinatorics},
Publisher = {American Mathematical Society},
Series = {Contemporary Mathematics},
Title = {The metamathatics of the Graph Minor Theorem},
Volume = {65},
Year = {1987}}
@article{Friedman.Sacks:77,
Author = {Sy D. Friedman and Gerald E. Sacks},
Journal = {Bull. Amer. Math. Soc.},
Pages = {255--256},
Title = {Inadmissible Recursion Theory},
Volume = {83},
Year = {1977}}
@incollection{Friedman.Simpson:00,
Address = {Providence, RI},
Author = {Friedman, Harvey and Simpson, Stephen G.},
Booktitle = {Computability theory and its applications (Boulder, CO, 1999)},
Mrclass = {03F35 (03B30 05D10 26E40 46Bxx)},
Mrnumber = {1 770 738},
Pages = {127--144},
Publisher = {Amer. Math. Soc.},
Title = {Issues and problems in reverse mathematics},
Year = {2000}}
@article{Friedman:75,
Author = {Friedman, Harvey},
Booktitle = {Proceedings of the International Congress of Mathematicians (Vancouver, B. C., 1974), Vol. 1},
Pages = {235--242},
Publisher = {Canad. Math. Congress, Montreal, Que.},
Title = {Some systems of second order arithmetic and their use},
Year = {1975}}
@article{Friedman:75*1,
Author = {Friedman, Harvey},
Journal = {J. Symbolic Logic},
Pages = {113--129},
Title = {102 Problems in Mathematical Logic},
Volume = {40},
Year = {1975}}
@article{Friedman:76,
Author = {Harvey Friedman},
Journal = {Journal of Symbolic Logic},
Pages = {557--559},
Title = {Systems of second order arithmetic with restricted induction, {I}, {II} {$($}abstracts{$)$}},
Volume = {41},
Year = {1976}}
@article{Froehlich.Shepherdson:55,
Author = {A. Froehlich and J. C. Shepherdson},
Journal = {Phil. Transactions of the Royal Society of London (Series A)},
Pages = {407--432},
Title = {Effective Procedures in Field Theory},
Volume = {248},
Year = {1955}}
@article{Gaifman:64,
Author = {Haim Gaifman},
Journal = {Notices Amer. Math. Soc.},
Pages = {771},
Title = {Measureable cardinals and constructible sets},
Volume = {11},
Year = {1964}}
@article{Galvin.Prikry:73,
Author = {F. Galvin and K. Prikry},
Journal = {J. Symbolic Logic},
Pages = {193--198},
Title = {{B}orel Sets and {R}amsey's Theorem},
Volume = {38},
Year = {1973}}
@article{Gandy.Sacks:67,
Author = {Robin O. Gandy and Gerald E. Sacks},
Journal = {Fund. Math.},
Pages = {215--223},
Title = {A Minimal Hyperdegree},
Volume = {61},
Year = {1967}}
@book{Garey.Johnson:79,
Address = {New York},
Author = {Michael R. Garey and David S. Johnson},
Publisher = {W. H. Freeman and Company},
Title = {Computers and Intractability},
Year = {1979}}
@inproceedings{Gasarch.Guimaraes:92,
Address = {Heidelberg},
Author = {William Gasarch and Katia Guimaraes},
Booktitle = {First Latin American Sym. on Theoretical Informatics (LATIN 92)},
Pages = {177--190},
Publisher = {Springer--Verlag},
Series = {Lecture notes in Computer Science},
Title = {On the number of components of a recursive graph},
Volume = {583},
Year = {1992}}
@article{Gasarch.Kueker.ea:89,
Author = {William Ian Gasarch and Dave Kueker and Dave Mount},
Journal = {Congressus Numerantium},
Pages = {97--102},
Title = {Recursive Categoricity of Highly Recursive Graphs},
Year = {1989}}
@article{Gasarch.Pleszkoch.ea:92,
Annote = {Earlier version in COLT90},
Author = {W. Gasarch and M. Pleszkoch and R. Solovay},
Journal = {J. Symbolic Logic},
Number = {1},
Pages = {53--81},
Title = {Learning via Queries to $[+,<]$},
Volume = {57},
Year = {1992}}
@article{Gasarch.Smith:92,
Author = {W. Gasarch and C. H. Smith},
Journal = {J. Assoc. Comput. Mach.},
Note = {A shorter version is in 29th FOCS conference, 1988, pp. 130-137},
Number = {3},
Pages = {649--675},
Title = {Learning via Queries},
Volume = {39},
Year = {1992}}
@incollection{Gasarch:nd,
Author = {William I. Gasarch},
Booktitle = {Handbook of Recursive Algebra},
Editor = {Ershov and Goncharov and Nerode and Remmel},
Publisher = {North--Holland Publishing Co.},
Title = {A Survey of Recursive Combinatorics}}
@article{Godel:31,
Author = {G{\"o}del, Kurt},
Journal = {Monatsh. Math. Phys.},
Pages = {349--360},
Title = {{\"U}ber formal unentscheidbare S{\"a}tze der Principia Mathematica und verwandter Systeme {I}},
Volume = {38},
Year = {1931}}
@article{Godel:38,
Author = {Kurt G{\"o}del},
Journal = {Proc. Nat. Acad. Sci. U.S.A.},
Pages = {556--557},
Title = {The consistency of the axiom of choice and of the generalized continuum hypothesis},
Volume = {24},
Year = {1938}}
@inproceedings{Godel:65,
Address = {New York},
Author = {G{\"o}del, Kurt},
Booktitle = {The Undecidable. Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions},
Editor = {Martin Davis},
Pages = {39--71},
Publisher = {Raven Press, Hewlitt},
Title = {On undecidable propositions of formal mathematical systems},
Year = {1965}}
@incollection{Godel:86,
Address = {Oxford},
Author = {G{\"o}del, Kurt},
Booktitle = {Kurt G{\"o}del: Collected Works},
Editor = {Feferman, Solomon and Dawson, Jr., John W. and Kleene, Stephen C. and Moore, Gregory H. and Solovay, Robert M. and {Van Heijenoort}, Jean},
Pages = {235--237},
Publisher = {Oxford University Press},
Title = {On completeness and consistency},
Volume = {1},
Year = {1986}}
@article{Gold:65,
Author = {E. Mark Gold},
Journal = {J. Symbolic Logic},
Number = {1},
Pages = {28--48},
Title = {Limiting Recursion},
Volume = {30},
Year = {1965}}
@book{Graham.Rothschild.ea:80,
Address = {New York},
Author = {Graham, Ronald L. and Rothschild, Bruce L. and Spencer, Joel H.},
Note = {A Wiley-Interscience Publication},
Publisher = {John Wiley \& Sons, Inc.},
Series = {Wiley-Interscience Series in Discrete Mathematics},
Title = {Ramsey theory},
Year = {1980}}
@book{Gratzer:71,
Address = {San Francisco},
Author = {Gr\"{a}tzer, G.},
Publisher = {W.H. Freeman},
Series = {A series of Books in Mathematices},
Title = {Lattice Theory: First Concepts and Distributive Lattices},
Year = {1971}}
@article{Groszek.Mytilinaios.ea:nd,
Author = {Groszek, Marcia J. and Mytilinaios, M. E. and Slaman, Theodore A.},
Journal = {J. Symbolic Logic},
Note = {To appear},
Title = {The {S}acks density theorem and ${\Sigma}_2$-bounding}}
@inproceedings{Groszek.Mytilinaios:90,
Address = {Heidelberg},
Author = {Groszek, Marcia J. and Mytilinaios, M. E.},
Booktitle = {Recursion Theory Week, Oberwolfach 1989},
Editor = {K. Ambos-Spies and G. H. Muller and Gerald E. Sacks},
Pages = {205--223},
Publisher = {Springer--Verlag},
Series = {Lecture Notes in Mathematics},
Title = {${\Sigma}_2$-Induction and the construction of a high degree},
Volume = {1432},
Year = {1990}}
@article{Groszek.Slaman:83,
Author = {Groszek, Marcia J. and Slaman, Theodore A.},
Journal = {Trans. Amer. Math. Soc.},
Pages = {579--587},
Title = {Independence results on the global structure of the {T}uring degrees},
Volume = {277},
Year = {1983}}
@unpublished{Groszek.Slaman:94,
Author = {Groszek, Marcia J. and Slaman, Theodore A.},
Note = {Preprint},
Title = {On {T}uring Reducibility},
Year = {1994}}
@unpublished{Groszek.Slaman:96,
Author = {Marcia J. Groszek and Theodore A. Slaman},
Note = {preprint},
Title = {${\Pi}_1^0$ Classes and Minimal Degrees},
Year = {1996}}
@article{Gurevich:83,
Author = {Y. Gurevich},
Journal = {J. Symbolic Logic},
Pages = {193-6},
Title = {Decision problem for separated distributive lattices},
Volume = {48},
Year = {1983}}
@phdthesis{Gutteridge:71,
Author = {Gutteridge, L.},
School = {Simon Fraser University},
Title = {Some Results on Enumeration Reducibility},
Year = {1971}}
@book{Hajek.Pudlak:93,
Address = {Berlin},
Author = {H{\'a}jek, Petr and Pudl{\'a}k, Pavel},
Isbn = {3-540-50632-2},
Pages = {xiv+460},
Publisher = {Springer-Verlag},
Series = {Perspectives in Mathematical Logic},
Title = {Metamathematics of first-order arithmetic},
Year = {1993}}
@incollection{Hajek:93,
Author = {H{\'a}jek, Petr},
Booktitle = {Arithmetic, proof theory, and computational complexity (Prague, 1991)},
Pages = {185--196},
Publisher = {Oxford Univ. Press, New York},
Title = {Interpretability and fragments of arithmetic},
Year = {1993}}
@phdthesis{Hammond:90,
Author = {T. Hammond},
School = {University of California},
Title = {The Lattice of Recursively Enumerable Sets Recursive in a Low Oracle},
Year = {1990}}
@article{Harel.Hirst:nd,
Author = {Harel, David and Hirst, Tirza},
Journal = {J. Comput. System Sci.},
Note = {To appear},
Title = {Taking it to the limit: On infinite variants of NP-complete problems}}
@article{Harel:91,
Author = {David Harel},
Journal = {Israel J. Math.},
Note = {Shorter version appeared in STOC 1991},
Pages = {317--336},
Title = {Hamiltonian Paths in Infinite Graphs},
Volume = {76},
Year = {1991}}
@article{Harizanov.Kummer.ea:92,
Author = {Valentina Harizanov and Martin Kummer and James Owings},
Journal = {J. Symbolic Logic},
Number = {2},
Pages = {682--687},
Title = {Frequency Computations and the Cardinality Theorem},
Volume = {57},
Year = {1992}}
@article{Harrington.Nies:98,
Author = {Harrington, Leo A. and Nies, Andr{\'e}},
Coden = {ADMTA4},
Fjournal = {Advances in Mathematics},
Issn = {0001-8708},
Journal = {Adv. Math.},
Number = {1},
Pages = {133--162},
Title = {Coding in the partial order of enumerable sets},
Volume = {133},
Year = {1998}}
@article{Harrington.Nies:98*1,
Author = {L. A. Harrington and A. Nies},
Journal = {Adv. in Math.},
Pages = {133-162},
Title = {Coding in the lattice of enumerable sets},
Volume = {133},
Year = {1998}}
@article{Harrington.Shelah:82,
Author = {Harrington, Leo A. and Shelah, S.},
Journal = {Bull. Amer. Math. Soc.},
Pages = {79--80},
Title = {The undecidability of the recursively enumerable degrees},
Volume = {6},
Year = {1982}}
@article{Harrington.Shore:81,
Author = {Harrington, Leo A. and Shore, Richard A.},
Journal = {Bull. Amer. Math. Soc.},
Pages = {97--100},
Title = {Definable degrees and automorphisms of $\cal D$},
Volume = {4},
Year = {1981}}
@article{Harrington.Soare:91,
Author = {Harrington, Leo A. and Soare, Robert I.},
Journal = {Proc. Nat. Acad. Sci. U.S.A.},
Pages = {10242--10246},
Title = {{P}ost's program and incomplete recursively enumerable sets},
Volume = {88},
Year = {1991}}
@inproceedings{Harrington.Soare:92,
Address = {Heidelberg},
Author = {Harrington, Leo A. and Soare, Robert I.},
Booktitle = {Set Theory and the Continuum},
Editor = {H. Judah and W. Just and W. H. Woodin},
Pages = {39--62},
Publisher = {Springer--Verlag},
Title = {Games in recursion theory and continuity properties of capping degrees},
Year = {1992}}
@article{Harrington.Soare:96,
Author = {Harrington, Leo A. and Soare, Robert I.},
Fjournal = {Journal of the American Mathematical Society},
Issn = {0894-0347},
Journal = {J. Amer. Math. Soc.},
Number = {3},
Pages = {617--666},
Title = {The ${\Delta}\sp 0\sb 3$-automorphism method and noninvariant classes of degrees},
Volume = {9},
Year = {1996}}
@article{Harrington.Soare:96*1,
Author = {Harrington, Leo A. and Soare, Robert I.},
Fjournal = {The Bulletin of Symbolic Logic},
Issn = {1079-8986},
Journal = {Bull. Symbolic Logic},
Number = {2},
Pages = {199--213},
Title = {Definability, automorphisms, and dynamic properties of computably enumerable sets},
Volume = {2},
Year = {1996}}
@article{Harrington.Soare:98,
Author = {Harrington, Leo and Soare, Robert I.},
Coden = {JSYLA6},
Fjournal = {The Journal of Symbolic Logic},
Issn = {0022-4812},
Journal = {J. Symbolic Logic},
Mrclass = {03D25},
Mrnumber = {99j:03031},
Mrrevr = {C. G. Jockusch, Jr.},
Number = {1},
Pages = {1--28},
Title = {Codable sets and orbits of computably enumerable sets},
Volume = {63},
Year = {1998}}
@unpublished{Harrington.Soare:nd,
Author = {Harrington, Leo A. and Soare, Robert I.},
Note = {To appear},
Title = {Noninvariance and low computably enumerable sets}}
@article{Harrington:78,
Author = {Leo A. Harrington},
Journal = {J. Symbolic Logic},
Pages = {685--693},
Title = {Analytic Determinacy and $0^\#$},
Volume = {20},
Year = {1978}}
@unpublished{Harrington:83,
Author = {Leo A. Harrington},
Note = {Handwritten Notes},
Title = {The undecidability of the lattice of recursively enumerable sets},
Year = {1983}}
@unpublished{Harrington:nd,
Author = {L. Harrington},
Note = {notes},
Title = {Understanding {L}achlan's Monster Paper}}
@unpublished{Harrington:nd*1,
Author = {L. Harrington},
Note = {notes},
Title = {Plus-Cupping in the Recursively Enumerable Degrees}}
@unpublished{Harrington:nd*2,
Author = {L. Harrington},
Note = {notes},
Title = {On {C}ooper's Proof of a Theorem of {Y}ates}}
@article{Hartmanis.Stearns:65,
Author = {J. Hartmanis and R. E. Stearns},
Journal = {Trans. Amer. Math. Soc.},
Pages = {285--306},
Title = {On the Computational Complexity of Algorithms},
Volume = {117},
Year = {1965}}
@article{Haught.Shore:90,
Author = {Haught, C. and Shore, R. A.},
Journal = {J. Symbolic Logic},
Pages = {987-1006},
Title = {Undecidability and initial segments of the (r.e.) tt-degrees},
Volume = {55},
Year = {1990}}
@inproceedings{Haught.Shore:90*1,
Author = {Haught, C. and Shore, R. A.},
Booktitle = {Recursion Theory Week, Proceedings Oberwolfach 1989},
Editor = {K. Ambos-Spies and G. H. Muller and G.E. Sacks},
Number = {1432},
Pages = {223-244},
Publisher = {Springer--Verlag},
Series = {Lecture Notes in Mathematics},
Title = {Undecidability and initial segments of the wtt-degrees below ${\bf 0}^{\prime }$},
Year = {1990}}
@article{Haught.Slaman:nd,
Author = {Haught, Christine A. and Slaman, Theodore A.},
Journal = {Ann. Pure Appl. Logic},
Note = {To appear},
Title = {Automorphisms in the \emph{{P}{T}{I}{M}{E}} {T}uring degrees of the recursive sets}}
@article{Haught:86,
Author = {Haught, Christine A.},
Journal = {J. Symbolic Logic},
Pages = {770--777},
Title = {The degrees below a 1-generic degree and less than $0'$},
Volume = {51},
Year = {1986}}
@article{Hay:78,
Author = {Louise Hay},
Journal = {Discrete Math.},
Number = {1},
Pages = {31--46},
Title = {Convex Subsets of {$2^n$} and Bounded Truth-Table Reducibility},
Volume = {21},
Year = {1978}}
@article{Heller:84,
Author = {H. Heller},
Journal = {Mathematical Systems Theory},
Number = {2},
Pages = {71--84},
Title = {Relativized Polynomial Hierarchies Extending Two Levels},
Volume = {17},
Year = {1984}}
@unpublished{Herrmann.Kummer:nd,
Author = {E. Herrmann and M. Kummer},
Note = {To appear},
Title = {Diagonals and {\cal D}-maximal Sets}}
@incollection{Herrmann:84,
Address = {Berlin},
Author = {Herrmann, E.},
Booktitle = {Frege conference, 1984 (Schwerin, 1984)},
Pages = {66--72},
Publisher = {Akademie-Verlag},
Title = {The undecidability of the elementary theory of the lattice of recursively enumerable sets},
Year = {1984}}
@article{Herrmann:84*1,
Author = {E. Herrmann},
Editor = {G. Wechsung},
Journal = {Proceedings of the 2nd Frege Conference at Schwerin, GDR},
Pages = {66--72},
Title = {The undecidability of the elementary theory of the lattice of recursively enumerable sets (abstract)},
Volume = {20},
Year = {1984}}
@incollection{Herrmann:89,
Address = {Amsterdam},
Author = {Herrmann, Eberhard},
Booktitle = {Logic, methodology and philosophy of science, VIII (Moscow, 1987)},
Pages = {179--190},
Publisher = {North-Holland},
Title = {Automorphisms of the lattice of recursively enumerable sets and hyperhypersimple sets},
Year = {1989}}
@unpublished{Herrmann:nd,
Author = {Herrmann, E.},
Note = {To Appear},
Title = {Infinite chains and antichains in recursive partial orderings}}
@article{Hilbert:01,
Author = {Hilbert, David},
Journal = {Bull. Amer. Math. Soc.},
Pages = {437--479},
Title = {Mathematical Problems},
Volume = {8},
Year = {1901--1902}}
@article{Hinman.Slaman:91,
Author = {Hinman, Peter G. and Slaman, Theodore A.},
Journal = {J. Symbolic Logic},
Pages = {563--591},
Title = {Jump embeddings into the {T}uring degrees},
Volume = {56},
Year = {1991}}
@inproceedings{Hirst:90,
Author = {Jeffry Hirst},
Booktitle = {Logic and Computation},
Note = {Proc. of a Workshop held at Carnegie Mellon University June 30-July 2 1987},
Publisher = {American Mathematical Society},
Series = {Contemporary Mathematics},
Title = {Marriage Theorems and Reverse Mathematics},
Volume = {106},
Year = {1990}}
@article{Hirst:92,
Author = {Jeffry L. Hirst},
Journal = {Arch. Math. Logic},
Number = {1},
Pages = {1--10},
Title = {Connected Components of Graphs and Reverse Mathematics},
Volume = {31},
Year = {1992}}
@article{Hodes:80,
Author = {Hodes, Harold T.},
Journal = {J. Symbolic Logic},
Pages = {204--220},
Title = {Jumping through the transfinite: the master code hierarchy of {T}uring degrees},
Volume = {45},
Year = {1980}}
@inproceedings{Hodges.Nies:97,
Author = {W. Hodges and A. Nies},
Booktitle = {Logic Colloquium '95},
Editor = {J.A. Makowsky and E.V. Ravve},
Pages = {247--251},
Series = {Lecture Notes in Logic},
Title = {Interpreting infinite linear orders},
Volume = {11},
Year = {1997}}
@inproceedings{Homer.Ambos-Spies.ea:90,
Address = {Heidelberg},
Author = {Steven Homer and Klaus Ambos-Spies and Dong Yang},
Booktitle = {Recursion Theory Week, Oberwolfach 1989},
Editor = {K. Ambos-Spies and G. H. Muller and Gerald E. Sacks},
Pages = {1--22},
Publisher = {Springer--Verlag},
Series = {Lecture Notes in Mathematics},
Title = {Honest Polynomial Reductions and Exptally Sets},
Volume = {1432},
Year = {1990}}
@article{Homer.Sacks:83,
Author = {Steven Homer and Gerald E. Sacks},
Journal = {Trans. Amer. Math. Soc.},
Pages = {317--331},
Title = {Inverting the Half-Jump},
Volume = {278},
Year = {1983}}
@inproceedings{Homer:85,
Address = {Heidelberg},
Author = {Steven Homer},
Booktitle = {Recursion Theory Week at Oberwolfach},
Pages = {193--202},
Publisher = {Springer--Verlag},
Series = {Lecture Notes in Mathematics},
Title = {Minimal Polynomial Degrees of Nonrecursive Sets},
Volume = {1141},
Year = {1985}}
@book{Hopcroft.Ullman:79,
Address = {Reading, Massachusetts},
Author = {John E. Hopcroft and Jeffrey D. Ullman},
Publisher = {Addison--Wesley Publishing Co.},
Title = {Introduction to Automata Theory, Languages, and Computation},
Year = {1979}}
@unpublished{Hummel.Jockusch:nd,
Author = {Hummel, Tamara Lankins and Jockusch, Jr., Carl G.},
Note = {To Appear in J. Symbolic Logic},
Title = {Generalized Cohesiveness}}
@article{Hummel:94,
Author = {Hummel, Tamara Lankins},
Journal = {J. Symbolic Logic},
Pages = {1301--1325},
Title = {Effective Versions of {R}amsey's Theorem: Avoiding the Cone Above $\mbox{\bfseries{0}}'$},
Volume = {59},
Year = {1994}}
@article{Ingrassia.Lempp:90,
Author = {Ingrassia, M. and Lempp, S.},
Journal = {Z. Math. Logik Grundlag. Math.},
Pages = {285-292},
Title = {Jumps of splittings of r.e. sets},
Volume = {36},
Year = {1990}}
@phdthesis{Ingrassia:81,
Author = {M. Ingrassia},
School = {University of Illinois},
Title = {P-Genericity for Recursively Enumerable Degrees},
Year = {1981}}
@unpublished{Ingrassia:nd,
Author = {M. Ingrassia},
Note = {notes},
Title = {There is no Complete Atomic Set}}
@incollection{Jensen.Solovay:70,
Author = {Ronald B. Jensen and Robert M. Solovay},
Booktitle = {Mathematical Logic and Foundations of Set Theory},
Editor = {Y. Bar-Hillel},
Pages = {84--104},
Publisher = {North--Holland Publishing Co.},
Title = {Some applications of almost disjoint sets},
Year = {1970}}
@article{Jockusch.Kalantari:84,
Author = {Jockusch, Jr., Carl G. and Iraj Kalantari},
Journal = {Pacific J. Math.},
Number = {1},
Pages = {143--153},
Title = {Recursively enumerable sets and van der {W}aerden's {T}heorem on arithmetic progressions},
Volume = {115},
Year = {1984}}
@article{Jockusch.Paterson:76,
Author = {Jockusch, Jr., Carl G. and M. Paterson},
Journal = {Z. Math. Logik Grundlag. Math.},
Pages = {571--575},
Title = {Completely Autoreducible Degrees},
Volume = {22},
Year = {1976}}
@article{Jockusch.Posner:81,
Author = {Jockusch, Jr., Carl G. and Posner, D.},
Journal = {Israel J. Math.},
Pages = {150--164},
Title = {Automorphism bases for degrees of unsolvability},
Volume = {40},
Year = {1981}}
@article{Jockusch.Shore:83,
Author = {Jockusch, Jr., Carl G. and Shore, Richard A.},
Journal = {Trans. Amer. Math. Soc.},
Pages = {599--609},
Title = {Pseudo-jump operators {I}: the r.e. case},
Volume = {275},
Year = {1983}}
@article{Jockusch.Shore:84,
Author = {Jockusch, Jr., Carl G. and Richard A. Shore},
Journal = {J. Symbolic Logic},
Pages = {1205--1236},
Title = {Pseudo-jump Operators {I}{I}: Transfinite Iterations, Hierarchies, and Minimal Covers},
Volume = {49},
Year = {1984}}
@article{Jockusch.Simpson:80,
Author = {Jockusch, Jr., Carl G. and Simpson, Stephen G.},
Journal = {Abstracts of papers presented to the AMS},
Pages = {546},
Title = {Minimal degrees, hyperimmune degrees, complete extensions of arithmetic, Abstract No. 781-{E}10},
Volume = {1},
Year = {1980}}
@article{Jockusch.Slaman:93,
Author = {Jockusch, Jr., Carl G. and Slaman, Theodore A.},
Journal = {J. Symbolic Logic},
Pages = {193--204},
Title = {On the {$\Sigma_2$}-theory of the upper-semi-lattice of the {T}uring degrees},
Volume = {58},
Year = {1993}}
@article{Jockusch.Soare:72,
Author = {Jockusch, Jr., Carl G. and Robert I. Soare},
Journal = {Trans. Amer. Math. Soc.},
Pages = {33--56},
Title = {{$\Pi_1^0$} Classes and Degrees of Theories},
Volume = {173},
Year = {1972}}
@article{Jockusch.Soare:nd,
Author = {Jockusch, Jr., Carl G. and Soare, Robert I.},
Journal = {J. Symbolic Logic},
Note = {To appear},
Title = {{B}oolean algebras, {S}tone spaces and the iterated {T}uring jump}}
@article{Jockusch.Stephan:93,
Author = {Jockusch, Jr., Carl G. and Frank Stephan},
Journal = {Math. Log. Quart.},
Pages = {515--530},
Title = {A cohesive set which is not high},
Volume = {39},
Year = {1993}}
@article{Jockusch.Stephan:97,
Author = {Jockusch, Jr., Carl G. and Frank Stephan},
Journal = {Math. Log. Quart.},
Pages = {569},
Title = {Correction to ``A cohesive set which is not high''},
Volume = {43},
Year = {1997}}
@article{Jockusch:68,
Author = {Jockusch, Jr., Carl G.},
Journal = {Trans. Amer. Math. Soc.},
Pages = {420--436},
Title = {Semirecursive sets and positive reducibility},
Volume = {131},
Year = {1968}}
@article{Jockusch:69,
Author = {Jockusch, Jr., Carl G.},
Journal = {Trans. Amer. Math. Soc.},
Pages = {229--237},
Title = {Relationships Between Reducibilities},
Volume = {142},
Year = {1969}}
@article{Jockusch:72*1,
Author = {Jockusch, Jr., Carl G.},
Journal = {Canad. J. Math.},
Pages = {1092--1099},
Title = {Degrees in which the Recursive Sets are Uniformly Recursive},
Volume = {24},
Year = {1972}}
@article{Jockusch:73,
Author = {Jockusch, Jr., Carl G.},
Journal = {Israel J. Math.},
Pages = {332--335},
Title = {Upward closure and cohesive degrees},
Volume = {15},
Year = {1973}}
@inproceedings{Jockusch:80,
Address = {Cambridge, U. K.},
Author = {Jockusch, Jr., Carl G.},
Booktitle = {Recursion Theory: Its Generalizations and Applications, Proceedings of Logic Colloquium '79, Leeds, August 1979},
Editor = {F. R. Drake and S. S. Wainer},
Pages = {110--139},
Publisher = {Cambridge University Press},
Title = {Degrees of generic sets},
Year = {1980}}
@article{Kaufman:84,
Author = {R. Kaufman},
Journal = {Mathematika},
Pages = {336--339},
Title = {Fourier Transforms and descriptive set theory},
Volume = {31},
Year = {1984}}
@book{Kaye:91,
Address = {New York},
Author = {Kaye, Richard},
Isbn = {0-19-853213-X},
Note = {Oxford Science Publications},
Pages = {x+292},
Publisher = {The Clarendon Press Oxford University Press},
Series = {Oxford Logic Guides},
Title = {Models of {P}eano arithmetic},
Volume = {15},
Year = {1991}}
@unpublished{Kaye:94,
Author = {Kaye, R.},
Month = {December},
Note = {The University of Birmingham, Preprint 94/35},
Title = {Constructing $\kappa$-like models of arithmetic},
Year = {1994}}
@unpublished{Kaye:94*1,
Author = {Kaye, R.},
Month = {December},
Note = {The University of Birmingham, Preprint 94/35},
Title = {The theory of $\kappa$-like models of arithmetic},
Year = {1994}}
@book{Kechris.Louveau:87,
Address = {Cambridge},
Author = {Kechris, Alexander S. and Louveau, Alain},
Publisher = {Cambridge University Press},
Series = {London Mathematical Society Lecture Note Series},
Title = {Descriptive Set Theory and the Structure of Sets of Uniqueness},
Volume = {128},
Year = {1987}}
@incollection{Kechris.Moschovakis:78,
Address = {Heidelberg},
Author = {Alexander S. Kechris and Yiannis N. Moschovakis},
Booktitle = {Cabal Seminar 76-77},
Editor = {Alexander S. Kechris and Yiannis N. Moschovakis},
Pages = {279--282},
Publisher = {Springer--Verlag},
Series = {Lecture Notes in Mathematics},
Title = {The {V}ictoria {D}elfino Problems},
Volume = {689},
Year = {1978}}
@article{Kechris.Woodin:86,
Author = {Alexander S. Kechris and W. Hugh Woodin},
Journal = {Mathematika},
Pages = {252--278},
Title = {Ranks of Differentiable Functions},
Volume = {33},
Year = {1986}}
@article{Kechris:91,
Author = {Kechris, Alexander S.},
Journal = {J. Symbolic Logic},
Pages = {182--194},
Title = {Amenable equivalence relations and the {T}uring degrees},
Volume = {56},
Year = {1991}}
@book{Kechris:95,
Address = {Heidelberg},
Author = {Alexander S. Kechris},
Publisher = {Springer--Verlag},
Series = {Graduate Texts in Mathematics},
Title = {Classical Descriptive Set Theory},
Volume = {156},
Year = {1995}}
@unpublished{Khoussainov.Nies.ea:nd,
Author = {Khoussainov, B. and Nies, A. and Shore, R. A.},
Note = {to appear},
Title = {Recursive models of theories with few models}}
@inproceedings{Kirby.Paris:77,
Address = {Heidelberg},
Author = {Kirby, L. A. and Paris, J. B.},
Booktitle = {Set Theory and Hierarchy Theory {V} (Bierutowice, Poland, 1976)},
Pages = {211--226},
Publisher = {Springer--Verlag},
Series = {Lecture Notes in Mathematics},
Title = {Initial segments of models of {P}eano's axioms},
Volume = {619},
Year = {1977}}
@inproceedings{Kirby.Paris:78,
Address = {Amsterdam},
Author = {Kirby, L. A. and Paris, J. B.},
Booktitle = {Logic Colloquium '77},
Pages = {199--209},
Publisher = {North--Holland Publishing Co.},
Title = {${\Sigma}_n$-collection schemas in arithmetic},
Year = {1978}}
@article{Kleene.Post:54,
Author = {Kleene, Stephen C. and Post, Emil L.},
Journal = {Ann. of Math. (2)},
Pages = {379--407},
Title = {The upper semi-lattice of degrees of recursive unsolvability},
Volume = {59},
Year = {1954}}
@article{Kleene.Rosser:35,
Author = {Kleene, S. C. and Rosser, J. B.},
Journal = {Ann. of Math. (2)},
Pages = {630--636},
Title = {The inconsistency of certain formal logics},
Volume = {36},
Year = {1935}}
@article{Kleene:35,
Author = {Kleene, S. C.},
Journal = {Amer. J. Math.},
Pages = {153-173, 219-244},
Title = {A theory of positive integers in formal logic},
Volume = {57},
Year = {1935}}
@article{Kleene:36,
Author = {Kleene, Stephen C.},
Journal = {Math. Ann.},
Pages = {727--742},
Title = {General recursive functions of natural numbers},
Volume = {112},
Year = {1936}}
@article{Kleene:36*1,
Author = {Kleene, S. C.},
Journal = {Duke Math. J.},
Pages = {340--353},
Title = {Lambda definability and recursiveness},
Volume = {2},
Year = {1936}}
@article{Kleene:45,
Author = {Kleene, S. C.},
Journal = {J. Symbolic Logic},
Pages = {109--124},
Title = {On the interpretation of intuitionistic number theory},
Volume = {10},
Year = {1945}}
@book{Kleene:52,
Address = {Princeton},
Author = {Kleene, S. C.},
Publisher = {Van Nostrand},
Title = {Introduction to Metamathematics},
Year = {1952}}
@article{Kleene:55,
Author = {Stephen C. Kleene},
Journal = {Bull. Amer. Math. Soc.},
Pages = {193--213},
Title = {Hierarchies of number-theoretic predicates},
Volume = {61},
Year = {1955}}
@incollection{Kleene:71,
Address = {Berlin},
Author = {Kleene, S. C.},
Booktitle = {Cambridge Summer School in Mathematical Logic},
Pages = {95--112},
Publisher = {Springer--Verlag, Lecture Notes in Mathematics, vol. 337},
Title = {Realizability: {A} retrospective survey},
Year = {1971}}
@article{Kleene:87,
Author = {Kleene, Stehpen C.},
Journal = {Biographical Memoirs},
Pages = {135--178},
Title = {{K}urt {G{\"o}del}: 1906--1978},
Volume = {56},
Year = {1987}}
@article{Knight:86,
Author = {Knight, J.F.},
Journal = {J. Symbolic Logic},
Pages = {1034-1042},
Title = {Degrees coded in jumps of orderings},
Volume = {51},
Year = {1986}}
@article{Knight:90,
Author = {Knight, J.},
Journal = {J. Symbolic Logic},
Pages = {787-804},
Title = {A metatheorem for constructions by finitely many workers},
Volume = {55},
Year = {1990}}
@unpublished{Knight:98,
Author = {Julia Knight},
Note = {Preprint},
Title = {Computable Structures and the Hyperarithmetical Hierarchy},
Year = {1998}}
@article{Kolmogorov:68,
Author = {A. N. Kolmogorov},
Journal = {IEEE Transactions on Information Theory},
Pages = {662--664},
Title = {Logical Basis for Information Theory and Probability Theory},
Volume = {14},
Year = {1968}}
@article{Kontostathis:91,
Author = {Kontostathis, K.},
Journal = {Z. Math. Logik Grundlag. Math.},
Pages = {495-500},
Title = {Topological framework for non-priority},
Volume = {37},
Year = {1991}}
@article{Kontostathis:92,
Author = {Kontostathis, K.},
Journal = {Z. Math. Logik Grundlag. Math.},
Pages = {189-195},
Title = {Topological framework for finite injury},
Volume = {38},
Year = {1992}}
@article{Kreisel.Sacks:65,
Author = {Georg Kreisel and Gerald E. Sacks},
Journal = {J. Symbolic Logic},
Pages = {318--338},
Title = {Metarecursive Sets},
Volume = {30},
Year = {1965}}
@article{Kreisel:50,
Author = {Kreisel, G.},
Journal = {Fund. Math.},
Pages = {265--285},
Title = {Notes on arithmetical models for consistent formulae of the predicate calculus},
Volume = {37},
Year = {1950}}
@inproceedings{Kreisel:69,
Address = {Amsterdam},
Author = {Georg Kreisel},
Booktitle = {Logic Colloquium '69},
Pages = {139--198},
Publisher = {North--Holland Publishing Co.},
Title = {Some reasons for generalizing recursion theory},
Year = {1969}}
@article{Kucera.Terwijn:99,
Author = {Ku{\v{c}}era, A. and Terwijn, S. A.},
Journal = {J. Symbolic Logic},
Number = {4},
Pages = {1396--1402},
Title = {Lowness for the class of random sets},
Volume = {64},
Year = {1999}}
@article{Kummer:91,
Author = {Martin Kummer},
Journal = {J. Symbolic Logic},
Pages = {1068--1074},
Title = {Diagonal and Semihyperhypersimple Sets},
Volume = {56},
Year = {1991}}
@article{Kummer:92,
Author = {Martin Kummer},
Journal = {J. Symbolic Logic},
Number = {2},
Pages = {677--681},
Title = {A proof of {B}eigel's Cardinality Conjecture},
Volume = {57},
Year = {1992}}
@article{Kurtz:83,
Author = {S. A. Kurtz},
Journal = {J. Symbolic Logic},
Pages = {764--770},
Title = {Notions of Weak Genericity},
Volume = {48},
Year = {1983}}
@article{Lachlan.Lebeuf:76,
Author = {Lachlan, Alistair H. and Lebeuf, R.},
Journal = {J. Symbolic Logic},
Pages = {289--300},
Title = {Countable initial segments of the degrees},
Volume = {41},
Year = {1976}}
@article{Lachlan.Shore:92,
Author = {Lachlan, Alistair H. and Shore, Richard A.},
Journal = {Arch. Math. Logic},
Pages = {277--285},
Title = {The $n$-rea enumeration degrees are dense},
Volume = {31},
Year = {1992}}
@article{Lachlan.Shore:92*1,
Author = {Lachlan, A. and Shore, R. A.},
Journal = {Arch. Math. Logic},
Pages = {227-285},
Title = {The $n$-r.e.a.\ enumeration degrees are dense},
Volume = {31},
Year = {1992}}
@article{Lachlan.Soare:80,
Author = {Lachlan, Alistair H. and Soare, Robert I.},
Journal = {Adv. in Math.},
Pages = {74--82},
Title = {Not every finite lattice is embeddable in the recursively enumerable degrees},
Volume = {37},
Year = {1980}}
@article{Lachlan.Soare:94,
Author = {Lachlan, Alistair H. and Soare, Robert I.},
Journal = {J. Symbolic Logic},
Pages = {977--983},
Title = {Models of arithmetic and upper bounds for arithmetic sets},
Volume = {59},
Year = {1994}}
@article{Lachlan:66,
Author = {Lachlan, Alistair H.},
Journal = {Proc. London Math. Soc. (3)},
Pages = {537--569},
Title = {Lower bounds for pairs of recursively enumerable degrees},
Volume = {16},
Year = {1966}}
@article{Lachlan:67,
Author = {Lachlan, Alistair H.},
Journal = {Z. Math. Logik Grundlag. Math.},
Pages = {1--10},
Title = {The Priority Method {I}},
Volume = {13},
Year = {1967}}
@article{Lachlan:68,
Author = {Lachlan, A. H.},
Journal = {J. Symbolic Logic},
Pages = {431-443},
Title = {Degrees of recursively enumerable sets which have no maximal supersets},
Volume = {33},
Year = {1968}}
@article{Lachlan:68*1,
Author = {Lachlan, Alistair H.},
Journal = {Z. Math. Logik Grundlag. Math.},
Pages = {457--472},
Title = {Distributive Initial Segments of the Degrees of Unsolvability},
Volume = {14},
Year = {1968}}
@article{Lachlan:68*2,
Author = {Lachlan, Alistair H.},
Journal = {Duke Math. J.},
Pages = {123--146},
Title = {The Elementary Theory of the Lattice of Recursively Enumerable Sets},
Volume = {35},
Year = {1968}}
@article{Lachlan:68*3,
Author = {Lachlan, Alistair H.},
Journal = {Trans. Amer. Math. Soc.},
Pages = {1--37},
Title = {On the Lattice of Recursively Enumerable Sets},
Volume = {130},
Year = {1968}}
@article{Lachlan:68*4,
Author = {Lachlan, A. H.},
Journal = {J. Symbolic Logic},
Pages = {431--443},
Title = {Degrees of recursively enumerable sets which have no maximal supersets.},
Volume = {33},
Year = {1968}}
@article{Lachlan:70,
Author = {Lachlan, A. H.},
Journal = {Ann. of Math. (2)},
Pages = {291-310},
Title = {On some games which are relevant to the theory of recursively enumerable sets},
Volume = {91},
Year = {1970}}
@article{Lachlan:70*1,
Author = {Alistair H. Lachlan},
Journal = {Canad. J. Math.},
Pages = {75--85},
Title = {Initial segments of many-one degrees},
Volume = {22},
Year = {1970}}
@article{Lachlan:71,
Author = {Lachlan, Alistair H.},
Journal = {Canad. J. Math.},
Pages = {247--256},
Title = {Solution to a problem of {S}pector},
Volume = {23},
Year = {1971}}
@inproceedings{Lachlan:72,
Address = {Heidelberg},
Author = {Lachlan, Alistair H.},
Booktitle = {Conference in Mathematical Logic, London, 1970},
Editor = {W. Hodges},
Pages = {149--177},
Publisher = {Springer--Verlag},
Series = {Lecture Notes in Mathematics},
Title = {Embedding nondistributive lattices in the recursively enumerable degress},
Volume = {255},
Year = {1972}}
@article{Lachlan:72*1,
Author = {Alistair H. Lachlan},
Journal = {Algebra and Logic},
Pages = {127--132},
Title = {Two Theorems on many-one degrees of recursively enumerable sets},
Volume = {11},
Year = {1972}}
@article{Lachlan:72*2,
Author = {Alistair H. Lachlan},
Journal = {Algebra and Logic},
Pages = {127--132},
Title = {Recursively Enumerable many-one degree},
Volume = {11},
Year = {1972}}
@inproceedings{Lachlan:73,
Address = {Berlin},
Author = {Lachlan, A. H.},
Booktitle = {Cambridge Summer School in Mathematical Logic},
Editor = {A. R. D. Mathias and H. Rogers, Jr.},
Pages = {299-310},
Publisher = {Springer--Verlag},
Title = {The priority method for the construction of recursively enumerable sets},
Volume = {Lecture Notes in Mathematics No. 337},
Year = {1973}}
@article{Lachlan:75,
Author = {Lachlan, Alistair H.},
Journal = {Ann. Math. Logic},
Pages = {307--365},
Title = {A recursively enumerable degree which will not split over all lesser ones},
Volume = {9},
Year = {1975}}
@article{Lachlan:79,
Author = {Lachlan, Alistair H.},
Journal = {J. Symbolic Logic},
Pages = {626--642},
Title = {Bounding Minimal Pairs},
Volume = {44},
Year = {1979}}
@article{Lachlan:80,
Author = {Lachlan, Alistair H.},
Journal = {Proc. Amer. Math. Soc.},
Pages = {629--634},
Title = {Decomposition of Recursively Enumerable Degrees},
Volume = {79},
Year = {1980}}
@article{Ladner.Sasso:75,
Author = {R. Ladner and L. Sasso},
Journal = {Arch. Math. Logik Grundlag.},
Pages = {429--448},
Title = {The Weak Truth-Table Degrees of the Recursively Enumerable Sets},
Volume = {8},
Year = {1975}}
@article{Ladner:73,
Author = {Richard Ladner},
Journal = {J. Symbolic Logic},
Pages = {199--211},
Title = {Mitotic Recursively Enumerable Sets},
Volume = {38},
Year = {1973}}
@article{Ladner:73*1,
Author = {Richard Ladner},
Journal = {Trans. Amer. Math. Soc.},
Pages = {497--507},
Title = {A Complete Mitotic Recursively Enumerable Degree},
Volume = {184},
Year = {1973}}
@article{Ladner:75,
Author = {Richard Ladner},
Journal = {J. Assoc. Comput. Mach.},
Number = {1},
Pages = {155--171},
Title = {On the Structure of Polynomial Time Reducibility},
Volume = {22},
Year = {1975}}
@phdthesis{Lagemann:72,
Author = {J. Lagemann},
School = {M. I. T.},
Title = {Embedding Theorems in the Reducibility Ordering of the Partial Degrees},
Year = {1972}}
@article{Landweber.Lipton.ea:81,
Author = {Landweber, L. and Lipton,R. and Robertson, E.},
Journal = {J. Theoretical Comp. Sc.},
Pages = {181--200},
Title = {On the structure of {NP} and other complexity classes},
Volume = {15},
Year = {1981}}
@article{Lavrov:63,
Author = {Lavrov},
Journal = {Algebra i Logika},
Pages = {5--18},
Title = {Effective inseparability of the sets of identically true formulae and finitely refutable formulae for certain theories},
Volume = {2},
Year = {1963}}
@book{Lemmon:78,
Author = {E.J. Lemmon},
Publisher = {Hackett Publishing Company},
Title = {Beginning Logic},
Year = {1978}}
@article{Lempp.Downey.ea:93,
Author = {Lempp, S. and Downey, R. and Shore, R. A.},
Journal = {Mathematical Logic Quarterly},
Pages = {475-491},
Title = {Highness and bounding minimal pairs},
Volume = {39},
Year = {1993}}
@unpublished{Lempp.Downey.ea:nd,
Author = {Lempp, S. and Downey, R. and Shore, R. A.},
Journal = {Journal of the London Mathematical Society},
Note = {to appear},
Title = {Jumps of minimal degrees below $0^\prime$}}
@inproceedings{Lempp.Lerman.ea:nd,
Address = {Boston},
Author = {Lempp, S. and Lerman, M. and Weber, F.},
Booktitle = {Logic Methods},
Editor = {J. Crossley and J. Remmel and R. Shore and M. Sweedler},
Note = {To appear},
Publisher = {Birkh\"{a}user},
Title = {Minimal pair constructions and iterated trees of strategies}}
@inproceedings{Lempp.Lerman:90,
Author = {Lempp, S. and Lerman, M.},
Booktitle = {Recursion Theory Week, Oberwolfach, 1989},
Editor = {K. Ambos-Spies and G. H. M\"{u}ller and G.E. Sacks},
Pages = {277-296},
Publisher = {Springer--Verlag},
Seriese = {Springer Lecture Notes Mathematics},
Title = {Priority arguments using iterated trees},
Volume = {1432},
Year = {1990}}
@inproceedings{Lempp.Lerman:90*1,
Address = {Heidelberg},
Author = {Lempp, S. and Lerman, M.},
Booktitle = {Recursion Theory Week, 1989},
Note = {Lecture Notes in Mathematics 1482},
Pages = {277--296},
Publisher = {Springer--Verlag},
Title = {Priority arguments using iterated trees of strategies},
Year = {1990}}
@article{Lempp.Lerman:92,
Author = {Lempp, S. and Lerman, M.},
Journal = {J. Symbolic Logic},
Pages = {1120--1130},
Title = {The existential theory of the poset of r. e. degrees with a predicate for single jump reducibility},
Volume = {57},
Year = {1992}}
@article{Lempp.Lerman:96,
Author = {Lempp, Steffen and Lerman, Manuel},
Coden = {ADMTA4},
Fjournal = {Advances in Mathematics},
Issn = {0001-8708},
Journal = {Adv. Math.},
Number = {1},
Pages = {1--142},
Title = {The decidability of the existential theory of the poset of recursively enumerable degrees with jump relations},
Volume = {120},
Year = {1996}}
@article{Lempp.Lerman:nd,
Author = {Steffen Lempp and Manuel Lerman},
Journal = {Ann. Pure Appl. Logic},
Note = {To appear},
Title = {A finite lattice without a critical triple that cannot be embedded into the enumerable Turing degree}}
@inproceedings{Lempp.Lerman:nd*1,
Author = {Lempp, S. and Lerman, M.},
Booktitle = {Proceedings of the Sacks Symposium, 1993 Logic Notes},
Editor = {T. Slaman et al},
Note = {To appear},
Publisher = {Springer--Verlag},
Series = {Lecture Notes in Logic},
Title = {Iterated trees of strategies and priority arguments}}
@article{Lempp.Nies.ea:98,
Author = {Lempp, Steffen and Nies, Andr{\'e} and Slaman, Theodore A.},
Coden = {TAMTAM},
Fjournal = {Transactions of the American Mathematical Society},
Issn = {0002-9947},
Journal = {Trans. Amer. Math. Soc.},
Mrclass = {03D25 (03D35)},
Mrnumber = {98j:03056},
Mrrevr = {Peter Cholak},
Number = {7},
Pages = {2719--2736},
Title = {The $\Pi\sb 3$-theory of the computably enumerable {T}uring degrees is undecidable},
Volume = {350},
Year = {1998}}
@article{Lempp.Nies:95,
Author = {Lempp, Steffen and Nies, Andr{\'e}},
Coden = {JSYLA6},
Fjournal = {The Journal of Symbolic Logic},
Issn = {0022-4812},
Journal = {J. Symbolic Logic},
Mrclass = {03D35 (03D25 03D30)},
Mrnumber = {97f:03062},
Mrrevr = {C. G. Jockusch, Jr.},
Number = {4},
Pages = {1118--1136},
Title = {The undecidability of the $\Pi\sb 4$-theory for the r.e.\ wtt and {T}uring degrees},
Volume = {60},
Year = {1995}}
@article{Lempp.Nies:nd,
Author = {Lempp, S. and Nies, A},
Journal = {J. Symbolic Logic},
Title = {Undecidability of the 4-quantifier theory for the recursively enumerable Turing and wtt degrees}}
@article{Lempp.Slaman:89,
Author = {Lempp, Steffen and Slaman, Theodore A.},
Journal = {J. Symbolic Logic},
Pages = {376--395},
Title = {A limit on relative genericity in the recursively enumerable sets},
Volume = {54},
Year = {1989}}
@phdthesis{Lempp:86,
Author = {Lempp, S.},
School = {University of Chicago},
Title = {Topics in recursively enumerable sets and degrees},
Year = {1986}}
@article{Lempp:87,
Author = {Lempp, S.},
Journal = {Trans. Amer. Math. Soc.},
Pages = {559-583},
Title = {Hyperarithmetical index sets in recursion theory},
Volume = {303},
Year = {1987}}
@article{Lempp:88,
Author = {Lempp, S.},
Journal = {J. Symbolic Logic},
Pages = {174-187},
Title = {A high strongly noncappable degree},
Volume = {53},
Year = {1988}}
@phdthesis{Leonhardi:94,
Author = {Steven Leonhardi},
School = {Unversity of Wisconsin},
Title = {Generalized Nonsplitting in the Recursively Enumerable Degrees},
Year = {1994}}
@inproceedings{Lerman.Remmel:82,
Author = {M. Lerman and J. B. Remmel},
Booktitle = {Logic Colloquium '80},
Editor = {Van Dalen and Smiley and Lascar},
Pages = {181--208},
Publisher = {North--Holland Publishing Co.},
Title = {The Universal Splitting Property, {I}},
Year = {1982}}
@article{Lerman.Remmel:84,
Author = {M. Lerman and J. B. Remmel},
Journal = {J. Symbolic Logic},
Pages = {137--150},
Title = {The Universal Splitting Property, {I}{I}},
Volume = {49},
Year = {1984}}
@inproceedings{Lerman.Rosenstein:81,
Author = {Manuel Lerman and Joseph G. Rosenstein},
Booktitle = {Logic Sym. at Patras 1980},
Note = {Math Reviews 84j:03092},
Pages = {123--126},
Title = {Recursive Linear Orderings},
Year = {1981}}
@article{Lerman.Sacks:72,
Author = {Manuel Lerman and Gerald E. Sacks},
Journal = {Ann. Math. Logic},
Pages = {415--442},
Title = {Some Minimal Pairs of $\alpha$-recursively enumerable degrees},
Volume = {4},
Year = {1972}}
@proceedings{Lerman.Schmerl.ea:81,
Address = {Heidelberg},
Editor = {M. Lerman and J. H. Schmerl and Robert I. Soare},
Note = {LNMS 859},
Publisher = {Springer--Verlag},
Title = {Logic Year 1979--80: University of {C}onnecticut},
Year = {1981}}
@article{Lerman.Shore.ea:78,
Author = {Lerman, Manuel and Shore, Richard A. and Soare, Robert I.},
Coden = {ISJMAP},
Fjournal = {Israel Journal of Mathematics},
Issn = {0021-2172},
Journal = {Israel J. Math.},
Mrclass = {03D25},
Mrnumber = {81g:03049},
Number = {1},
Pages = {1--18},
Title = {$r$-maximal major subsets},
Volume = {31},
Year = {1978}}
@article{Lerman.Shore.ea:84,
Author = {Lerman, M. and Shore, R. A. and Soare, R.I.},
Journal = {Adv. in Math.},
Pages = {301-320},
Title = {The elementary theory of the recursively enumerable degrees is not $\aleph_{0}$-categorical},
Volume = {53},
Year = {1984}}
@article{Lerman.Shore:88,
Annote = {Gives a decision procedure for the $\Sigma_2$ theory of{\newline} the degrees below $0'$},
Author = {Lerman, M. and Shore, Richard A.},
Journal = {Trans. Amer. Math. Soc.},
Pages = {669--692},
Title = {Decidability and Invariant Classes for Degree Structures},
Volume = {310},
Year = {1988}}
@article{Lerman.Soare:80,
Author = {Lerman, M. and Soare, R. I.},
Coden = {TAMTAM},
Fjournal = {Transactions of the American Mathematical Society},
Issn = {0002-9947},
Journal = {Trans. Amer. Math. Soc.},
Number = {1},
Pages = {1--37},
Title = {A decidable fragment of the elementary theory of the lattice of recursively enumerable sets},
Volume = {257},
Year = {1980}}
@article{Lerman.Soare:80*1,
Author = {Lerman, Manuel and Soare, Robert I.},
Coden = {PJMAAI},
Fjournal = {Pacific Journal of Mathematics},
Issn = {0030-8730},
Journal = {Pacific J. Math.},
Number = {1},
Pages = {135--155},
Title = {$d$-simple sets, small sets, and degree classes},
Volume = {87},
Year = {1980}}
@article{Lerman:71,
Author = {Lerman, M.},
Journal = {Ann. of Math. (2)},
Pages = {311--389},
Title = {Initial Segments of the degrees of unsolvability},
Volume = {93},
Year = {1971}}
@inproceedings{Lerman:73,
Address = {New York},
Author = {Lerman, M.},
Booktitle = {Cambridge Summer School in Mathematical Logic},
Editor = {A. R.D. Mathias and H. Rogers, Jr.},
Pages = {311-344},
Publisher = {Springer--Verlag},
Title = {Admissible ordinals and priority arguments},
Volume = {Lecture Notes in Mathematic No. 337},
Year = {1973}}
@inproceedings{Lerman:81,
Author = {Manuel Lerman},
Booktitle = {Logic Year 1979-1980},
Note = {Math Reviews 84j:03059},
Pages = {132--142},
Title = {On Recursive Linear Orderings},
Year = {1981}}
@book{Lerman:83,
Address = {Heidelberg},
Author = {Lerman, M.},
Note = {307 pages},
Publisher = {Springer--Verlag},
Series = {Perspectives in Mathematical Logic},
Title = {Degrees of Unsolvability},
Year = {1983}}
@inproceedings{Lerman:85,
Author = {M. Lerman},
Booktitle = {Recursion Theory, Proceedings of Symposia in Pure Mathematics, Vol. 42},
Pages = {13--20},
Title = {The Embedding Problem for the Recursively Enumerable Degrees},
Year = {1985}}
@unpublished{Lerman:93,
Author = {Lerman, M.},
Note = {Handwritten manuscript},
Title = {Notes on the {$\Sigma_2$} theory of the recursively enumerable degrees},
Year = {1993}}
@article{Levin:73,
Author = {Levin, L. A.},
Journal = {Soviet Math. Dokl.},
Pages = {1464--1466},
Title = {On storage capacity for algorithms},
Volume = {14},
Year = {1973}}
@article{Lewis:85,
Author = {A. Lewis},
Journal = {Mathematics of Social Science},
Pages = {43--80},
Title = {On effectively computable realizations of choice functions},
Volume = {10},
Year = {1985}}
@inproceedings{Loebl.Matou-sek:87,
Author = {Martin Loebl and Ji{\v r\'\i} Matou{\v s}ek},
Booktitle = {Logic and Combinatorics},
Publisher = {American Mathematical Society},
Series = {Contemporary Mathematics},
Title = {On undecidability of the weakened {K}ruskal's {T}heorem},
Volume = {65},
Year = {1987}}
@article{Maass.Shore.ea:81,
Author = {W. Maass and Richard A. Shore and M. Stob},
Journal = {Israel J. Math.},
Pages = {210--224},
Title = {Splitting Properties and Jump Classes},
Volume = {39},
Year = {1981}}
@article{Maass.Slaman:89,
Author = {Maass, W. and Slaman, Theodore A.},
Journal = {Fundamentals (or Foundations) of Computation Theory},
Title = {Extensional Properties of Sets of Time Bounded Complexity},
Volume = {7},
Year = {1989}}
@inproceedings{Maass.Slaman:89*1,
Author = {Maass, W. and Slaman, Theodore A.},
Booktitle = {Annual Conference on Structure in Complexity Theory},
Title = {The Complexity Types of Computable Sets},
Year = {1989}}
@inproceedings{Maass.Slaman:89*2,
Author = {Maass, W. and Slaman, Theodore A.},
Booktitle = {Logic Colloquium},
Title = {Some Problems and Results in the Theory of Actually Computable Functions},
Year = {1989}}
@inproceedings{Maass.Slaman:90,
Address = {Heidelberg},
Author = {Maass, W. and Slaman, Theodore A.},
Booktitle = {Recursion Theory Week, Oberwolfach, 1989},
Editor = {K. Ambos-Spies and G. H. Muller and Gerald E. Sacks},
Publisher = {Springer--Verlag},
Series = {Lecture Notes in Mathematics},
Title = {On the relationship between the complexity, the degree and the extension of a computable set},
Volume = {1432},
Year = {1990}}
@article{Maass.Slaman:92,
Author = {Maass, W. and Slaman, Theodore A.},
Journal = {J. Comput. System Sci.},
Pages = {168--192},
Title = {The complexity types of computable sets},
Volume = {44},
Year = {1992}}
@incollection{Maass.Slaman:92*1,
Address = {Heidelberg},
Author = {Maass, W. and Slaman, Theodore A.},
Booktitle = {Logic from Computer Science: Proceedings of a Workshop held November 13-17, 1989},
Editor = {Y.~N.~Moschovakis},
Pages = {359--372},
Publisher = {Springer--Verlag},
Title = {Splitting and Density for the Recursive Sets of a Fixed Time Complexity},
Year = {1992}}
@article{Maass.Stob:83,
Author = {W. Maass and M. Stob},
Journal = {Ann. Pure Appl. Logic},
Pages = {189--212},
Title = {The Intervals of the Lattice of Recursively Enumerable Sets Determined By Major Subsets},
Volume = {24},
Year = {1983}}
@article{Maass:82,
Author = {W. Maass},
Journal = {J. Symbolic Logic},
Pages = {809--823},
Title = {Recursively Enumerable Generic Sets},
Volume = {47},
Year = {1982}}
@article{Maass:83,
Author = {W. Maass},
Journal = {Trans. Amer. Math. Soc.},
Pages = {311--336},
Title = {Characterization of Recursively Enumerable Sets with Supersets Effectively Isomorphic to All Recursively Enumerable Sets},
Volume = {279},
Year = {1983}}
@article{Maass:84,
Author = {Maass, W.},
Journal = {J. Symbolic Logic},
Pages = {51--62},
Title = {On the orbit of hyperhypersimple sets},
Volume = {49},
Year = {1984}}
@article{Marchenkov:76,
Author = {S. S. Marchenkov},
Journal = {Math. Z.},
Pages = {473--487},
Title = {A Class of Incomplete Sets},
Volume = {20},
Year = {1976}}
@phdthesis{Marcone:93,
Author = {Alberto Marcone},
School = {Pennsylvania State University},
Title = {Foundations of bqo theory and subsystems of second order arithmetic},
Year = {1993}}
@article{Markov:47,
Author = {Markov, A.A.},
Journal = {Dokl. Akad. Nauk SSSR},
Note = {Russian},
Pages = {1891-1892},
Title = {On the representation of recursive functions},
Volume = {58},
Year = {1947}}
@article{Martin-Lof:66,
Author = {P. Martin-L{\"o}f},
Journal = {Inform. and Control},
Pages = {602--619},
Title = {The Definition of Random Sequences},
Volume = {9},
Year = {1966}}
@article{Martin.Pour-El:70,
Author = {Martin, D. A. and Pour-El, M. B.},
Journal = {J. Symbolic Logic},
Pages = {205-209},
Title = {Axiomatizable theories with few axiomatizable extensions},
Volume = {35},
Year = {1970}}
@article{Martin.Steel:89,
Author = {Martin, Donald A. and Steel, John R.},
Journal = {J. Amer. Math. Soc.},
Pages = {71--125},
Title = {A Proof of Projective Determinacy},
Volume = {2},
Year = {1989}}
@article{Martin:66,
Author = {Donald A. Martin},
Journal = {Proc. Amer. Math. Soc.},
Pages = {838--842},
Title = {Completeness, the recursion theorem, and effectively simple sets},
Volume = {17},
Year = {1966}}
@article{Martin:75,
Author = {Martin, D. A.},
Journal = {Ann. of Math. (2)},
Pages = {363-371},
Title = {Borel Determinacy},
Volume = {102},
Year = {1975}}
@incollection{Martin:85,
Author = {Martin, Donald A.},
Booktitle = {Proceedings of Symposia in Pure Mathematics},
Pages = {303--308},
Publisher = {American Mathematical Society},
Title = {A Purely Inductive Proof of {B}orel Determinacy},
Volume = {42},
Year = {1985}}
@article{Mathias:68,
Author = {A. R. D. Mathias},
Journal = {Notices Amer. Math. Soc.},
Note = {Abstract 68T-E19},
Title = {On a generalization of {R}amsey's Theorem},
Volume = {15},
Year = {1968}}
@article{Matijasevic:70,
Author = {Matijasevic, Y.},
Journal = {Dokl. Akad. Nauk SSSR},
Note = {Translation in Soviet Math Doklady, Vol 11, 1970},
Pages = {279--282},
Title = {Enumerable Sets are Diophantine ({R}ussian)},
Volume = {191},
Year = {1970}}
@book{Matijasevic:93,
Address = {Cambridge},
Author = {Matijasevic, Y.},
Publisher = {MIT press},
Title = {Hilbert's Tenth Problem},
Year = {1993}}
@inproceedings{McAloon:78,
Author = {Ken McAloon},
Booktitle = {Logic Colloquium; 1978},
Pages = {171--181},
Title = {Diagonal methods and strong cuts in models of arithmetic},
Year = {1978}}
@article{McEvoy:58,
Author = {McEvoy, K.},
Journal = {J. Symbolic Logic},
Pages = {839--848},
Title = {Jumps of Quasi--minimal Enumeration Degrees},
Volume = {50},
Year = {1958}}
@article{Medevdev:55,
Author = {Medevdev, Y. T.},
Journal = {Dokl. Akad. Nauk SSSR},
Pages = {501--504},
Title = {Degrees of difficulty of the mass problems},
Volume = {104},
Year = {1955}}
@article{Metakides.Nerode:77,
Author = {George Metakides and Anil Nerode},
Journal = {Ann. Math. Logic},
Pages = {147--171},
Title = {Recursively Enumerable Vector Spaces},
Volume = {11},
Year = {1977}}
@article{Metakides.Nerode:79,
Author = {George Metakides and Anil Nerode},
Journal = {Ann. Math. Logic},
Pages = {289--320},
Title = {Effective content of field theory},
Volume = {17},
Year = {1979}}
@article{Meyer.Ritchie:72,
Author = {Albert Meyer and Dennis Ritchie},
Journal = {Z. Math. Logik Grundlag. Math.},
Pages = {71--82},
Title = {A Classification of the Recursive Functions},
Volume = {18},
Year = {1972}}
@article{Meyer.Winklmann:79,
Author = {Meyer, A. R. and Winklmann, K.},
Journal = {Math. Centre Tracts},
Pages = {97--112},
Title = {The fundamental theorem of complexity theory},
Volume = {108},
Year = {1979}}
@incollection{Millar:85,
Address = {Providence, R.I.},
Author = {Millar, T.},
Booktitle = {Recursion theory (Ithaca, N.Y., 1982)},
Mrclass = {03C57 (03C15 03D45)},
Mrnumber = {87b:03072},
Mrrevr = {S. S. Goncharov},
Pages = {311--321},
Publisher = {Amer. Math. Soc.},
Title = {Decidable {E}hrenfeucht theories},
Year = {1985}}
@article{Miller.Remmel:84,
Author = {D. Miller and J. B. Remmel},
Journal = {J. Symbolic Logic},
Pages = {129--136},
Title = {Effectively Nowhere Simple Sets},
Volume = {49},
Year = {1984}}
@inproceedings{Miller:81,
Author = {D. Miller},
Booktitle = {Logic Year 1979--80: University of {C}onnecticut},
Pages = {230--245},
Title = {High Recursively Enumerable Degrees and the Anticupping Property},
Year = {1981}}
@phdthesis{Miller:81*1,
Author = {D. Miller},
School = {The University of Chicago},
Title = {The Relationship Between Structure and Degrees of Recursively Enumerable Sets},
Year = {1981}}
@inbook{Miller:92,
Author = {Miller, III, C. F.},
Editors = {G. Baumslag and C. F. Miller, III},
Note = {Algorithms and classification in combinatorial group theory},
Pages = {1-59},
Publisher = {Springer--Verlag},
Title = {Decision problems for groups - survey and reflections},
Year = {1992}}
@article{Mints:73,
Author = {Mints, G. E.},
Journal = {J. of Soviet Math.},
Pages = {71--84},
Title = {Quantifer-free and one quantifer systems},
Volume = {1},
Year = {1973}}
@phdthesis{Mohrherr:82,
Author = {Mohrherr, J.},
School = {University of Illinois at Chicago Circle},
Title = {Index Sets and Truth-Table Degrees},
Year = {1982}}
@article{Montagna.Sorbi:85,
Author = {Montagna, Franco and Sorbi, Andrea},
Coden = {JSYLA6},
Fjournal = {The Journal of Symbolic Logic},
Issn = {0022-4812},
Journal = {J. Symbolic Logic},
Mrclass = {03D45},
Mrnumber = {87k:03046},
Number = {2},
Pages = {397--406},
Title = {Universal recursion-theoretic properties of r.e.\ preordered structures},
Volume = {50},
Year = {1985}}
@article{Morley.Soare:75,
Author = {M. Morley and Robert I. Soare},
Journal = {Fund. Math.},
Pages = {45--52},
Title = {Splitting Theorems and $\Delta_2^0$ Sets},
Volume = {90},
Year = {1975}}
@phdthesis{Moses:83,
Author = {Michael Moses},
School = {Monash University, Clayton, Victoria, Australia},
Title = {Recursive properties of isomophism types},
Year = {1983}}
@article{Moses:86,
Author = {Michael Moses},
Journal = {Z. Math. Logik Grundlag. Math.},
Pages = {467--472},
Title = {Relations intrinsically recursive in linear orders},
Volume = {32},
Year = {1986}}
@article{Moses:88,
Author = {Michael Moses},
Journal = {J. Symbolic Logic},
Number = {2},
Pages = {531--539},
Title = {Decidable Discrete Linear Orders},
Volume = {53},
Year = {1988}}
@incollection{Moses:nd,
Author = {Michael Moses},
Booktitle = {Handbook of Recursive Algebra},
Editor = {Ershov and Goncharov and Nerode and Remmel},
Publisher = {North--Holland Publishing Co.},
Title = {A Survey of Recursive Categoricity}}
@article{Muchnik:56,
Author = {Muchnik, A. A.},
Journal = {Dokl. Akad. Nauk SSSR},
Pages = {194--197},
Title = {On the unsolvability of the problem of reducibility in the theory of algorithms},
Volume = {N. S. 108},
Year = {1956}}
@unpublished{Mytilinaios.Slaman:94,
Author = {Mytilinaios, M. E. and Slaman, Theodore A.},
Note = {Preprint},
Title = {On a Question of {B}rown and {S}impson},
Year = {1994}}
@article{Mytilinaios:89,
Author = {Mytilinaios, M. E.},
Journal = {J. Symbolic Logic},
Pages = {38--49},
Title = {Finite Injury and ${\Sigma}_1$-Induction},
Volume = {54},
Year = {1989}}
@inproceedings{Nerode.Remmel:85,
Author = {A. Nerode and J. B. Remmel},
Booktitle = {Recursion Theory, Proceedings of Symposia in Pure Mathematics, Vol. 42},
Pages = {322--375},
Title = {A Survey of Lattices of Recursively Enumerable Substructures},
Year = {1985}}
@article{Nerode.Shore:80,
Author = {Nerode, Anil and Shore, Richard A.},
Journal = {Ann. Math. Logic},
Pages = {61--89},
Title = {Reducibility orderings: theories, definability and automorphisms},
Volume = {18},
Year = {1980}}
@inproceedings{Nerode.Shore:80*1,
Address = {Amsterdam},
Author = {Nerode, Anil and Shore, Richard A.},
Booktitle = {The Kleene Symposium},
Editor = {J. Barwise, H. J. Keisler and K. Kunen},
Pages = {181--200},
Publisher = {North--Holland Publishing Co.},
Title = {Second order logic and first order theories of reducibility orderings},
Year = {1980}}
@proceedings{Nerode.Shore:85,
Editor = {Anil Nerode and Richard A. Shore},
Publisher = {American Mathematical Society},
Title = {Recursion Theory, Proceedings of Symposia in Pure Mathematics, Vol. 42},
Year = {1985}}
@book{Nerode.Shore:93,
Address = {New York},
Author = {Nerode, A. and Shore, R. I.},
Publisher = {Springer--Verlag},
Title = {Logic for Applications, Texts and Monographs in Computer Science},
Year = {1993}}
@inproceedings{Nerode:57,
Author = {Anil Nerode},
Booktitle = {Cornell Summer Institute in Symbolic Logic},
Pages = {247--251},
Title = {General topology and partial recursive functionals},
Year = {1957}}
@article{Nies.Shore.ea:98,
Author = {Nies, Andr{\'e} and Shore, Richard A. and Slaman, Theodore A.},
Coden = {PLMTAL},
Fjournal = {Proceedings of the London Mathematical Society. Third Series},
Issn = {0024-6115},
Journal = {Proc. London Math. Soc. (3)},
Number = {2},
Pages = {241--291},
Title = {Interpretability and definability in the recursively enumerable degrees},
Volume = {77},
Year = {1998}}
@unpublished{Nies.Shore.ea:nd,
Author = {Nies, Andre and Shore, Richard A. and Slaman, Theodore A.},
Note = {In preparation},
Title = {Definability in the recursively enumerable degrees}}
@article{Nies.Shore:95,
Author = {Nies, A. and Shore, R. A.},
Journal = {Ann. Pure Appl. Logic},
Pages = {269-311},
Title = {Interpreting true arithmetic in the theory of the r.\ e.\ truth table degrees},
Volume = {75},
Year = {1995}}
@article{Nies:00,
Author = {Nies, Andr{\'e}},
Coden = {TAMTAM},
Fjournal = {Transactions of the American Mathematical Society},
Issn = {0002-9947},
Journal = {Trans. Amer. Math. Soc.},
Mrclass = {03C40 (03C57 03D25 03D45)},
Mrnumber = {1 776 883},
Mrreviewer = {Andrey Morozov},
Number = {11},
Pages = {4989--5012 (electronic)},
Title = {Effectively dense {B}oolean algebras and their applications},
Volume = {352},
Year = {2000}}
@incollection{Nies:02,
Author = {Nies, Andr{\'e}},
Booktitle = {Computability Theory and Its Applications: Current Trends and Open Problems},
Editor = {Peter Cholak and Steffen Lempp and Manny Lerman and Richard Shore},
Publisher = {American Mathematical Society},
Title = {Global properties of degree structures},
Year = {2002}}
@phdthesis{Nies:92,
Author = {Nies, A.},
School = {Universit\"{a}t Heidelberg},
Title = {Definability and undecidability in recursion theoretic semilattices},
Year = {1992}}
@inproceedings{Nies:93,
Author = {Nies, A},
Booktitle = {Kurt G{\"o}del Kolloqium 1993},
Pages = {255-263},
Publisher = {Springer--Verlag},
Series = {Lecture Notes in Computer Science},
Title = {Interpreting true arithmetic in degree structures},
Volume = {713},
Year = {1993}}
@article{Nies:94,
Author = {Nies, A},
Journal = {Math. Logic Quarterly},
Pages = {490-518},
Title = {Recursively enumerable equivalence relations modulo finite differences},
Volume = {5},
Year = {1994}}
@article{Nies:95,
Author = {Nies, A},
Journal = {Algebra i Logika},
Note = {English Translation, Consultants Bureau, NY, July 1995},
Number = {5},
Pages = {550-563},
Title = {The last question on recursively enumerable many-one degrees},
Volume = {33},
Year = {1995}}
@incollection{Nies:96,
Author = {A. Nies},
Booktitle = {Proceedings of the Leeds logic year},
Publisher = {Springer--Verlag},
Series = {Lecture Notes in Logic},
Title = {Relativizations of structures from recursion theory},
Year = {1996}}
@article{Nies:96*1,
Author = {Nies, A},
Journal = {Algebra Universalis},
Pages = {8-33},
Title = {Undeciadable fragments of elementary theories},
Volume = {35},
Year = {1996}}
@article{Nies:97,
Author = {A. Nies},
Journal = {Bull. Lond. Math. Soc.},
Pages = {683-92},
Title = {Intervals of the lattice of computably enumerable sets and effective {B}oolean algebras},
Volume = {29},
Year = {1997}}
@misc{Nies:98,
Author = {Nies, Andr{\'e}},
Note = {Habilitationsschrift, Universit\"at Heidelberg},
Pages = {108},
School = {Universit\"at Heidelberg},
Title = {Coding Methods in Computability Theory and Complexity Theory},
Year = {1998}}
@unpublished{Nies:nd,
Author = {Nies, A.},
Note = {To appear},
Title = {On the complexity of the theories of two distributive degree structures}}
@inproceedings{Nies:nd*1,
Author = {Nies, A},
Booktitle = {Proceedings of the European network in recursion theory, complexity theory and logic},
Note = {to appear},
Title = {On an uniformity in degree structures}}
@unpublished{Nies:nd*2,
Author = {A. Nies},
Note = {In preparation},
Title = {Effectively dense boolean algebras and their applications}}
@unpublished{Odifreddi.Shore:89,
Author = {Odifreddi, P. and Shore, Richard A.},
Note = {Preprint},
Title = {Global Properties of Local Structures of Degrees},
Year = {1989}}
@article{Odifreddi.Shore:91,
Author = {Odifreddi, P. and Shore, R. A.},
Journal = {Bul. U. Mat. Ital.},
Pages = {97-120},
Title = {Global properties of local structures of degrees},
Volume = {7},
Year = {1991}}
@article{Odifreddi:81,
Author = {Odifreddi, Piergiorgio},
Journal = {Bull. Amer. Math. Soc.},
Number = {1},
Pages = {37--86},
Title = {Strong Reducibilities},
Volume = {4},
Year = {1981}}
@inproceedings{Odifreddi:85,
Address = {Heidelberg},
Author = {Piergiorgio Odifreddi},
Booktitle = {Recursion Theory Week at Oberwolfach},
Pages = {315--332},
Publisher = {Springer--Verlag},
Series = {Lecture Notes in Mathematics},
Title = {The Structure of the $m$-degrees},
Volume = {1141},
Year = {1985}}
@book{Odifreddi:89,
Address = {Amsterdam},
Author = {Piergiorgio Odifreddi},
Publisher = {North--Holland Publishing Co.},
Title = {Classical Recursion Theory (Volume {I})},
Year = {1989}}
@book{Odifreddi:99,
Address = {Amsterdam},
Author = {Odifreddi, P. G.},
Isbn = {0-444-50205-X},
Mrclass = {03Dxx (03-02 03D15 03D25 03D30 68Q05 68Q15)},
Mrnumber = {1 718 169},
Pages = {xvi+949},
Publisher = {North-Holland Publishing Co.},
Title = {Classical recursion theory. {V}ol. {I}{I}},
Year = {1999}}
@misc{Otto:95,
Author = {Martin Otto},
Note = {Habilitationsschrift RWTH Aachen},
Title = {Bounded variable logics and counting --- A study in finite models},
Year = {1995}}
@article{Owings:67,
Author = {James C. Owings},
Journal = {J. Symbolic Logic},
Pages = {173--178},
Title = {Recursion, Metarecursion, and Inclusion},
Volume = {32},
Year = {1967}}
@article{Owings:89,
Author = {James C. Owings},
Journal = {J. Symbolic Logic},
Number = {3},
Pages = {761--767},
Title = {A Cardinality Version of {B}eigel's {N}onspeedup {T}heorem},
Volume = {54},
Year = {1989}}
@book{Papadimitriou.Lewis:81,
Author = {C. H. Papadimitriou and H. R. Lewis},
Publisher = {Prentice-Hall, Inc.},
Title = {Elements of the Theory of Computation},
Year = {1981}}
@incollection{Paris.Harrington:77,
Address = {Amsterdam},
Author = {J. Paris and Leo A. Harrington},
Booktitle = {Handbook of Mathematical Logic},
Editor = {Jon Barwise},
Pages = {1133--1142},
Publisher = {North--Holland Publishing Co.},
Title = {A mathematical incompleteness in {P}eano Arithmetic},
Year = {1977}}
@article{Paris:78,
Author = {J. Paris},
Journal = {J. Symbolic Logic},
Pages = {725--731},
Title = {Independence results for {P}eano Arithmetic},
Volume = {43},
Year = {1978}}
@incollection{Parsons:70,
Address = {Amsterdam},
Author = {Parsons, Charles},
Booktitle = {Intuitionism and Proof Theory (Proc. Conf., Buffalo, N.Y., 1968)},
Pages = {459--473},
Publisher = {North-Holland},
Title = {On a number theoretic choice schema and its relation to induction},
Year = {1970}}
@book{Peano:89,
Address = {Turin},
Author = {Peano, G.},
Publisher = {Fratres Bocca},
Title = {Arithmetices Principia, Novo Methodo Exposita},
Year = {1889}}
@article{Poljakov.Rozinas:79,
Author = {E. A. Poljakov and M. G. Rozinas},
Journal = {Mathematics of the USSR--Sbornik},
Number = {3},
Pages = {425--436},
Title = {Relationships between different forms of relative computability},
Volume = {35},
Year = {1979}}
@article{Polyakov.Rozinas:77,
Author = {E. A. Polyakov and M. G. Rozinas},
Journal = {Siberian Math. J.},
Number = {4},
Pages = {594--599},
Title = {Enumeration reducibilities},
Volume = {18},
Year = {1977}}
@article{Posner.Robinson:81,
Author = {Posner, David B. and Robinson, Robert W.},
Journal = {J. Symbolic Logic},
Number = {4},
Pages = {714--722},
Title = {Degrees joining to ${\bf 0'}$},
Volume = {46},
Year = {1981}}
@article{Posner:81,
Author = {Posner, David},
Journal = {J. Symbolic Logic},
Pages = {705--713},
Title = {The Upper Semilattice of Degrees Below $\mathbf{0}'$ is Complemented},
Volume = {46},
Year = {1981}}
@article{Post:36,
Author = {Post, Emil L.},
Journal = {J. Symbolic Logic},
Pages = {103--105},
Title = {Finite combinatory processes. {F}ormulation {I}},
Volume = {1},
Year = {1936}}
@article{Post:44,
Author = {Post, Emil L.},
Journal = {Bull. Amer. Math. Soc.},
Pages = {284--316},
Title = {Recursively enumerable sets of positive integers and their decision problems},
Volume = {50},
Year = {1944}}
@article{Post:47,
Author = {Post, E. L.},
Journal = {J. Symbolic Logic},
Pages = {1-11},
Title = {Recursive unsolvability of a problem of Thue},
Volume = {12},
Year = {1947}}
@article{Putnam:65,
Author = {Hillary Putnam},
Journal = {J. Symbolic Logic},
Number = {1},
Pages = {49--57},
Title = {Trial and Error Predicates and the Solution to a Problem of {M}ostowski},
Volume = {30},
Year = {1965}}
@article{Rabin:58,
Author = {Rabin, M.O.},
Journal = {Ann. of Math. (2)},
Pages = {172-194},
Title = {Recursive unsolvability of group theoretic problems},
Volume = {67},
Year = {1958}}
@article{Rabin:60,
Author = {Michael O. Rabin},
Journal = {Trans. Amer. Math. Soc.},
Pages = {341--360},
Title = {Computable algebra, general theory and theory of computable fields},
Volume = {{95}},
Year = {1960}}
@incollection{Rabin:77,
Author = {Michael O. Rabin},
Booktitle = {Handbook of Mathematical Logic},
Editor = {Jon Barwise},
Publisher = {North--Holland Publishing Co.},
Title = {Decidable Theories},
Year = {1977}}
@article{Ramsey:30,
Author = {Ramsey, F. P.},
Journal = {Proc. London Math. Soc. (3)},
Pages = {264--286},
Title = {On a problem in formal logic},
Volume = {30},
Year = {1930}}
@article{Remmel:80,
Author = {J. B. Remmel},
Journal = {J. Symbolic Logic},
Pages = {20--34},
Title = {On Recursively Enumerable and Co-Recursively Enumerable Vector Spaces with Nonextendible Bases},
Volume = {45},
Year = {1980}}
@article{Remmel:81,
Author = {Jeff Remmel},
Journal = {Proc. Amer. Math. Soc.},
Pages = {383--391},
Title = {Recursive Categorical Linear Orderings},
Volume = {83},
Year = {1981}}
@article{Remmel:81*1,
Author = {Jeff Remmel},
Journal = {Proc. Amer. Math. Soc.},
Pages = {379--386},
Title = {On the effectiveness of the {S}chroder-{B}ernstein Theorem},
Volume = {83},
Year = {1981}}
@incollection{Remmel:89,
Address = {Amsterdam},
Author = {Remmel, J. B.},
Booktitle = {Handbook of Boolean algebras, Vol.\ 3},
Pages = {1097--1165},
Publisher = {North-Holland},
Title = {Recursive {B}oolean algebras},
Year = {1989}}
@proceedings{Richter.Borger.ea:84,
Address = {Heidelberg},
Editor = {M. M. Richter and E. B\"orger and W. Oberschelp and B. Schinzel and W. Thomas},
Publisher = {Springer--Verlag},
Series = {Lecture Notes in Mathematics},
Title = {Computation and Proof Theory, Proceedings of the Logic Colloquium held in {A}achen, {J}uly 8--13, 1983},
Volume = {1104},
Year = {1984}}
@article{Richter:81,
Author = {Richter, L. J.},
Journal = {J. Symbolic Logic},
Pages = {723--731},
Title = {Degrees of structures},
Volume = {46},
Year = {1981}}
@article{Robinson:67,
Author = {Robinson, R. W.},
Journal = {J. Symbolic Logic},
Pages = {162-72},
Title = {Simplicity of the recursively enumerable sets},
Volume = {32},
Year = {1967}}
@article{Robinson:68,
Author = {Robinson, R. W.},
Journal = {Z. Math. Logik Grundlag. Math.},
Pages = {339-356},
Title = {A dichotomy of the recursively enumerable sets},
Volume = {14},
Year = {1968}}
@article{Robinson:71,
Author = {Robinson, R. W.},
Journal = {Ann. of Math. (2)},
Pages = {285--314},
Title = {Interpolation and embedding in the recursively enumerable degrees},
Volume = {93},
Year = {1971}}
@article{Robinson:71*1,
Author = {Robinson, R. W.},
Journal = {Ann. of Math. (2)},
Pages = {586--596},
Title = {Jump restricted interpolation in the recursively enumerable degrees},
Volume = {93},
Year = {1971}}
@book{Rogers:67,
Address = {New York},
Author = {Rogers, Jr., H.},
Publisher = {McGraw-Hill},
Title = {Theory of Recursive Functions and Effective Computability},
Year = {1967}}
@incollection{Rogers:67*1,
Author = {Rogers, Jr., H.},
Booktitle = {Sets Models and Recursion Theory, Proc. Summer School in Mathematical Logic and Tenth Logic Colloquium, Lercester, August-September 1965},
Editor = {J.~N.~Crossley},
Publisher = {North--Holland Publishing Co.},
Title = {Some problems of definability in recursive function theory},
Year = {1967}}
@book{Rosenstein:81,
Address = {New York},
Author = {Joseph G. Rosenstein},
Note = {{P}ure and {A}pplied Math {S}eries 98},
Publisher = {Academic Press},
Title = {Linear Orderings},
Year = {1981}}
@unpublished{Rutkowski:95,
Author = {Aleksander Rutkowski},
Note = {Preprint},
Title = {Which Ordered Sets Have a Dense Linear Extension?},
Year = {1995}}
@article{Sacks.Simpson:72,
Author = {Sacks, Gerald E. and Simpson, Stephen G.},
Journal = {Ann. Math. Logic},
Pages = {343--367},
Title = {The $\alpha$-finite injury method},
Volume = {4},
Year = {1972}}
@article{Sacks.Slaman:87,
Author = {Sacks, Gerald E. and Slaman, Theodore A.},
Journal = {Adv. in Math.},
Pages = {1--30},
Title = {Inadmissible forcing},
Volume = {66},
Year = {1987}}
@article{Sacks.Slaman:90,
Author = {Sacks, Gerald E. and Slaman, Theodore A.},
Journal = {Proc. London Math. Soc. (3)},
Pages = {417--443},
Title = {Generalized Hyperarithmetic Theory},
Volume = {60},
Year = {1990}}
@article{Sacks:58,
Author = {Gerald E. Sacks},
Journal = {I.R.E. Trans. on Info. Theory},
Pages = {145--147},
Title = {Multiple Error Correction by Means of Parity Checks},
Volume = {4},
Year = {1958}}
@article{Sacks:61,
Author = {Sacks, Gerald E.},
Journal = {Bull. Amer. Math. Soc.},
Pages = {416--419},
Title = {A Minimal Degree Below $\mathbf{0}'$},
Volume = {67},
Year = {1961}}
@article{Sacks:61*1,
Author = {Sacks, Gerald E.},
Journal = {Z. Math. Logik Grundlag. Math.},
Pages = {46--56},
Title = {On suborderings of degrees of recursive unsolvability},
Volume = {17},
Year = {1961}}
@article{Sacks:61*3,
Author = {Gerald E. Sacks},
Journal = {Bull. Amer. Math. Soc.},
Pages = {416--419},
Title = {A Minimal Degree Below $\mbox{\bfseries 0}'$},
Volume = {67},
Year = {1961}}
@book{Sacks:63,
Author = {Sacks, Gerald E.},
Publisher = {Princeton University Press},
Series = {Annals of Mathematical Studies},
Title = {Degrees of Unsolvability},
Volume = {55},
Year = {1963}}
@article{Sacks:63*1,
Author = {Sacks, G.E.},
Journal = {Trans. Amer. Math. Soc.},
Pages = {223-239},
Title = {Recursive enumerability and the jump operator},
Volume = {108},
Year = {1963}}
@article{Sacks:63*3,
Author = {Gerald E. Sacks},
Journal = {Ann. of Math. (2)},
Pages = {211--231},
Title = {On the degrees less than $\mbox{\bfseries 0}'$},
Volume = {77},
Year = {1963}}
@article{Sacks:64,
Author = {Sacks, Gerald E.},
Journal = {Ann. of Math. (2)},
Pages = {300--312},
Title = {The recursively enumerable degrees are dense},
Volume = {80},
Year = {1964}}
@article{Sacks:64*1,
Author = {Sacks, Gerald E.},
Journal = {Proc. Amer. Math. Soc.},
Pages = {51--55},
Title = {A Simple Set Which is not Effectively Simple},
Volume = {15},
Year = {1964}}
@book{Sacks:66,
Author = {Sacks, Gerald E.},
Publisher = {Princeton University Press},
Series = {Annals of Mathematical Studies},
Title = {Degrees of Unsolvability, 2nd Edition},
Volume = {55},
Year = {1966}}
@article{Sacks:66*1,
Author = {Gerald E. Sacks},
Journal = {Trans. Amer. Math. Soc.},
Pages = {1-23},
Title = {Post's Problem, Admissible Ordinals and Regularity},
Volume = {124},
Year = {1966}}
@article{Sacks:66*3,
Author = {Gerald E. Sacks},
Journal = {Bull. Amer. Math. Soc.},
Pages = {59--64},
Title = {Metarecursively enumerable sets and admissible ordinals},
Volume = {72},
Year = {1966}}
@article{Sacks:67,
Author = {Sacks, Gerald E.},
Journal = {Proc. Amer. Math. Soc.},
Pages = {140--141},
Title = {On a theorem of {L}achlan and {M}artin},
Volume = {18},
Year = {1967}}
@inproceedings{Sacks:67*1,
Address = {Amsterdam},
Author = {Gerald E. Sacks},
Booktitle = {Sets, Models and Recursion Theory (Proceedings of the Summer School in Mathematical Logic and 10th Logic Colloquium, Leicester, 1965)},
Pages = {243--263},
Publisher = {North--Holland Publishing Co.},
Title = {Metarecursion Theory},
Year = {1967}}
@article{Sacks:67*2,
Author = {Gerald E. Sacks},
Journal = {Bull. Amer. Math. Soc.},
Pages = {169--174},
Title = {Measure-theoretic Uniformity},
Volume = {73},
Year = {1967}}
@article{Sacks:69,
Author = {Gerald E. Sacks},
Journal = {Trans. Amer. Math. Soc.},
Pages = {381-420},
Title = {Measure-theoretic Uniformity in Recursion Theory and Set Theory},
Volume = {42},
Year = {1969}}
@inproceedings{Sacks:71,
Address = {Providence, R. I.},
Author = {Sacks, Gerald E.},
Booktitle = {Axiomatic Set Theory I},
Editor = {D. Scott},
Pages = {331--355},
Publisher = {American Mathematical Society},
Series = {Proc. Symp. Pure Math.},
Title = {Forcing with perfect closed sets},
Volume = {13},
Year = {1971}}
@inproceedings{Sacks:71*1,
Address = {Paris},
Author = {Gerald E. Sacks},
Booktitle = {Actes du Congress International des Mathematicians (Nice, 1970)},
Pages = {251--254},
Publisher = {Gauthier--Villars},
Title = {Recursion in Objects of Finite Type},
Year = {1971}}
@article{Sacks:71*2,
Author = {Gerald E. Sacks},
Journal = {Adv. in Math.},
Pages = {57--82},
Title = {On the Reducibility of ${\Pi}^1_1$ Sets},
Volume = {7},
Year = {1971}}
@inproceedings{Sacks:71*4,
Address = {Amsterdam},
Author = {Gerald E. Sacks},
Booktitle = {Logic Colloquium '69 (Proceedings of the Summer School and Colloquium in Mathematical Logic, Manchester, 1969)},
Editor = {Robin O. Gandy and C. E.M. Yates},
Pages = {289--303},
Publisher = {North--Holland Publishing Co.},
Title = {${F}$-recursiveness},
Year = {1971}}
@book{Sacks:72,
Address = {Reading},
Author = {Sacks, Gerald E.},
Publisher = {W. A. Benjamin},
Title = {Saturated Model Theory},
Year = {1972}}
@article{Sacks:72*1,
Author = {Gerald E. Sacks},
Journal = {Bull. Amer. Math. Soc.},
Pages = {629--634},
Title = {The Differential Closure of a Differential Field},
Volume = {78},
Year = {1972}}
@inproceedings{Sacks:75,
Address = {Rome},
Author = {Gerald E. Sacks},
Booktitle = {Model Theory and Applications},
Organization = {Centro Internazionale Matematico Estivo},
Pages = {5--53},
Publisher = {Edizioni Cremonese},
Title = {Theories of Algebraic Type},
Year = {1975}}
@article{Sacks:75*1,
Author = {Gerald E. Sacks},
Journal = {Historia Math.},
Pages = {523--528},
Title = {Remarks Against Foundational Activity},
Volume = {2},
Year = {1975}}
@article{Sacks:75*2,
Author = {Gerald E. Sacks},
Journal = {Beloit Poetry Jour.},
Number = {2},
Pages = {34},
Title = {Archaic Words Descend},
Volume = {26},
Year = {1975}}
@article{Sacks:76,
Author = {Gerald E. Sacks},
Journal = {Adv. in Math.},
Pages = {213--262},
Title = {Countable Admissible Ordinals and Hyperdegrees},
Volume = {30},
Year = {1976}}
@incollection{Sacks:77,
Address = {Holland},
Author = {Gerald E. Sacks},
Booktitle = {Logic, Foundations of Mathematics and Computability Theory (Proceedings of the Fifth International Congrees on Logic, Methodology and Philosophy of Science, University of Western Ontario, London, Ontario, 1975)},
Pages = {173--194},
Publisher = {Reidel, Dordrecht},
Title = {{R}. {E}. Sets Higher Up},
Year = {1977}}
@article{Sacks:77*1,
Author = {Gerald E. Sacks},
Journal = {Amer. J. Math.},
Pages = {901--917},
Title = {The $k$-Section of a Type $n$ Object},
Volume = {99},
Year = {1977}}
@inproceedings{Sacks:78,
Address = {Amsterdam},
Author = {Gerald E. Sacks},
Booktitle = {Generalized Recursion Theory},
Editor = {J. Fenstad and Robin O. Gandy and Gerald E. Sacks},
Pages = {81--93},
Publisher = {North--Holland Publishing Co.},
Title = {The 1-Section of a Type $n$ Object},
Year = {1978}}
@article{Sacks:79,
Author = {Gerald E. Sacks},
Journal = {Fund. Math.},
Pages = {111--121},
Title = {Effective Bounds on {M}orley Rank},
Volume = {53},
Year = {1979}}
@incollection{Sacks:80,
Address = {Cambridge},
Author = {Gerald E. Sacks},
Booktitle = {Recursion Theory: Its Generalizations and Applications},
Editor = {F. R. Drake and S. S. Wainer},
Pages = {184--214},
Publisher = {Cambridge University Press},
Title = {Three Aspects of Recursive Enumerability in Higher Types},
Year = {1980}}
@inproceedings{Sacks:80*1,
Address = {Amsterdam},
Author = {Gerald E. Sacks},
Booktitle = {The Kleene Symposium},
Editor = {J. Barwise, H. J. Keisler and K. Kunen},
Pages = {201--222},
Publisher = {North--Holland Publishing Co.},
Title = {Post's Problem, Absoluteness and Recursion in Finite Types},
Year = {1980}}
@article{Sacks:81,
Author = {Gerald E. Sacks},
Journal = {Liguori Editore, Naples},
Pages = {109--168},
Title = {Priority Arguments in Higher Recursion Theory},
Year = {1981}}
@inproceedings{Sacks:83,
Address = {Amsterdam},
Author = {Gerald E. Sacks},
Booktitle = {Southeast Asian Conference on Logic (Singapore, 1981)},
Pages = {185--195},
Publisher = {North--Holland Publishing Co.},
Title = {On the Number of Countable Models},
Year = {1983}}
@inproceedings{Sacks:85,
Author = {Gerald E. Sacks},
Booktitle = {Proceedings of Symposia in Pure Mathematics},
Editor = {Anil Nerode and Richard A. Shore},
Publisher = {American Mathematical Society},
Title = {Post's Problem in ${E}$-Recursion},
Volume = {42},
Year = {1985}}
@inproceedings{Sacks:85*1,
Address = {Heidelberg},
Author = {Gerald E. Sacks},
Booktitle = {Recursion Theory Week},
Editor = {H.-D. Ebbinghaus and G.~H. Muller and Gerald E. Sacks},
Pages = {333--342},
Publisher = {Springer--Verlag},
Series = {Lecture Notes in Mathematics},
Title = {Some Open Questions in Recursion Theory},
Volume = {1141},
Year = {1985}}
@article{Sacks:86,
Author = {Gerald E. Sacks},
Journal = {Ann. Pure Appl. Logic},
Pages = {333--342},
Title = {The Limits of ${E}$-Recursive Enumerability},
Volume = {31},
Year = {1986}}
@book{Sacks:90,
Address = {Heidelberg},
Author = {Gerald Sacks},
Publisher = {Springer--Verlag},
Series = {Perspectives in Mathematical Logic},
Title = {Higher Recursion Theory},
Year = {1990}}
@incollection{Sacks:90*2,
Author = {Gerald E. Sacks},
Booktitle = {Computability and Recursion Theory},
Publisher = {CIME},
Title = {Prolog Programming},
Year = {1990}}
@article{Sacks:nd,
Author = {Gerald E. Sacks},
Journal = {Ann. Pure Appl. Logic},
Note = {To appear},
Title = {Effective versus Proper Forcing}}
@article{Sasso:74,
Author = {Sasso, L. P.},
Journal = {J. Symbolic Logic},
Pages = {571-574},
Title = {A minimal degree not realizing least possible jump},
Volume = {39},
Year = {1974}}
@article{Schmerl:80,
Author = {James H. Schmerl},
Journal = {Canad. J. Math.},
Pages = {821--830},
Title = {Recursive Colorings of Graphs},
Volume = {32},
Year = {1980}}
@article{Schmerl:82,
Author = {James H. Schmerl},
Journal = {Canad. J. Math.},
Pages = {1036--1046},
Title = {The Recursive Version of {B}roo{ks's} Theorem},
Volume = {34},
Year = {1982}}
@incollection{Schmerl:85,
Author = {James H. Schmerl},
Booktitle = {Graphs and Orders},
Editor = {I. Rival},
Pages = {467--484},
Publisher = {D. Reidel Publishing Company},
Title = {Recursion Theoretic Aspects of Graphs and Orders},
Year = {1985}}
@book{Schoning:85,
Address = {Heidelberg},
Author = {Uwe {Sch\"oning}},
Publisher = {Springer--Verlag},
Title = {Complexity and Structure},
Year = {1985}}
@phdthesis{Schwarz:83,
Author = {Steven Schwarz},
School = {University of Chicago},
Title = {Index sets of recursively enumerable sets, quotient lattices, and recursive linear orderings},
Year = {1983}}
@article{Schwarz:84,
Author = {Steven Schwarz},
Journal = {Ann. Pure Appl. Logic},
Pages = {69--73},
Title = {Recursive automorphisms of recursive linear orderings},
Volume = {25},
Year = {1984}}
@inproceedings{Scott:62,
Address = {Providence, R.I.},
Author = {Dana Scott},
Booktitle = {Recursive Function Theory},
Number = {5},
Pages = {117--121},
Publisher = {American Mathematical Society},
Series = {Proceedings of Symposia in Pure Mathematics},
Title = {Algebras of sets binumerable in complete extensions of arithmetic},
Year = {1962}}
@article{Scott:64,
Author = {Scott, D. S.},
Journal = {Fund. Math.},
Pages = {117--128},
Title = {Invariant {B}orel sets},
Volume = {56},
Year = {1964}}
@incollection{Scott:65,
Address = {Amsterdam},
Author = {Scott, Dana},
Booktitle = {Theory of Models (Proc. 1963 Internat. Sympos. Berkeley)},
Mrclass = {02.35},
Mrnumber = {34 \#32},
Mrreviewer = {E. Engeler},
Pages = {329--341},
Publisher = {North-Holland},
Title = {Logic with denumerably long formulas and finite strings of quantifiers},
Year = {1965}}
@inproceedings{Scott:92,
Address = {New York},
Author = {Scott, E. A.},
Booktitle = {Algorithms and classification in combinatorial group theory},
Editor = {G. Baumslag and C. F. Miller, III},
Publisher = {Springer--Verlag},
Title = {A tour around finitely presented infinite groups},
Year = {1992}}
@unpublished{Seetapun.Slaman:94,
Author = {Seetapun, David and Slaman, Theodore A.},
Title = {Minimal Complements},
Year = {1994}}
@inproceedings{Shinoda.Slaman:88,
Author = {Shinoda, Juichi and Slaman, Theodore A.},
Booktitle = {Annual Conference on Structure in Complexity Theory},
Title = {On the Theory of the {PTIME} Degrees of the Recursive Sets},
Year = {1988}}
@inproceedings{Shinoda.Slaman:89,
Address = {Heidelberg},
Author = {Shinoda, Juichi and Slaman, Theodore A.},
Booktitle = {Mathematical Logic and it Applications, Proceedings, Kyoto, 1987},
Editor = {Juichi Shinoda and Theodore A. Slaman and T. Tugu\'e},
Publisher = {Springer--Verlag},
Series = {Lecture Notes in Mathematics},
Title = {The continuum hypothesis and the theory of the {K}leene degrees},
Volume = {1388},
Year = {1989}}
@article{Shinoda.Slaman:91,
Author = {Shinoda, Juichi and Slaman, Theodore A.},
Journal = {J. Comput. System Sci.},
Pages = {321--336},
Title = {On the theory of the \emph{{P}{T}{I}{M}{E}} degrees of the recursive sets},
Volume = {40},
Year = {1991}}
@article{Shoenfield.Soare:78,
Author = {Joseph R. Shoenfield and Robert I. Soare},
Journal = {The Recursive Function Theory Newsletter},
Pages = {219},
Title = {The Generalized Diamond Theorem},
Volume = {19},
Year = {1978}}
@article{Shoenfield:59,
Author = {Joseph R. Shoenfield},
Journal = {Ann. of Math. (2)},
Pages = {644--653},
Title = {On degrees of unsolvability},
Volume = {69},
Year = {1959}}
@article{Shoenfield:60,
Author = {Joseph R. Shoenfield},
Journal = {J. Symbolic Logic},
Pages = {233--237},
Title = {Degrees of Models},
Volume = {25},
Year = {1960}}
@incollection{Shoenfield:61,
Address = {Hebrew University, Jerusalem},
Author = {Shoenfield, Joseph R.},
Booktitle = {Essays on the Foundations of Mathematics},
Pages = {132--139},
Publisher = {Magnes Press},
Title = {The problem of predicativity},
Year = {1961}}
@article{Shoenfield:61*1,
Author = {Shoenfield, Joseph R.},
Journal = {Fund. Math.},
Pages = {171--179},
Title = {Undecidable and creative theories},
Volume = {49},
Year = {1961}}
@inproceedings{Shoenfield:65,
Address = {Amsterdam},
Author = {Shoenfield, Joseph R.},
Booktitle = {The Theory of Models, Proceedings of the 1963 International Symposium at Berkeley},
Editor = {J. W. Addison and L. Henkin and A. Tarski},
Pages = {359--363},
Publisher = {North--Holland Publishing Co.},
Series = {Studies in Logic and the Foundations of Mathematics},
Title = {Applications of model theory to degrees of unsolvability},
Year = {1965}}
@article{Shoenfield:66,
Author = {Shoenfield, J. R.},
Journal = {J. Symbolic Logic},
Pages = {539-544},
Title = {A theorem on minimal degrees},
Volume = {31},
Year = {1966}}
@article{Shoenfield:76,
Author = {Joseph R. Shoenfield},
Journal = {J. Symbolic Logic},
Pages = {695--696},
Title = {Degrees of Classes of Recursively Enumerable Sets},
Volume = {41},
Year = {1976}}
@article{Shoenfield:90,
Author = {Shoenfield, J.R.},
Journal = {Ann. Pure Appl. Logic},
Pages = {191-205},
Title = {Non-bounding constructions},
Volume = {50},
Year = {1990}}
@article{Shoenfield:95,
Author = {Joseph R. Shoenfield},
Journal = {Bull. Symbolic Logic},
Pages = {9--43},
Title = {The Mathematical Work of {S}. {C}. {K}leene},
Volume = {1},
Year = {1995}}
@inproceedings{Shore.Slaman:89,
Author = {Shore, Richard A. and Slaman, Theodore A.},
Booktitle = {Annual Conference on Structure in Complexity Theory},
Title = {The {P}-{T}-Degrees of the Recursive Sets: Lattice Embeddings, Extensions of Embeddings and the Two Quantifier Theory (Extended Abstract)},
Year = {1989}}
@article{Shore.Slaman:91,
Author = {Shore, Richard A. and Slaman, Theodore A.},
Journal = {Ann. Pure Appl. Logic},
Pages = {1--25},
Title = {Working below a low$_2$ recursively enumerable degree},
Volume = {52},
Year = {1991}}
@article{Shore.Slaman:92,
Author = {Shore, Richard A. and Slaman, Theodore A.},
Journal = {Theoretical Computer Science},
Pages = {263--282},
Title = {The ${P}$-${T}$-degrees of the recursive sets: lattice embeddings, extensions of embeddings, and the two quantifier theory},
Volume = {97},
Year = {1992}}
@article{Shore.Slaman:93,
Author = {Shore, Richard A. and Slaman, Theodore A.},
Journal = {J. Symbolic Logic},
Pages = {824--859},
Title = {Working below a high recursively enumerable degree},
Volume = {58},
Year = {1993}}
@unpublished{Shore.Slaman:nd,
Author = {Shore, Richard A. and Slaman, Theodore A.},
Note = {Unpublished},
Title = {An elementary difference between the recursively enumerable and the meta-recursively enumerable degrees}}
@incollection{Shore:00,
Author = {Richard Shore},
Booktitle = {Computability Theory and Its Applications: Current Trends and Open Problems},
Editor = {Peter Cholak and Steffen Lempp and Manny Lerman and Richard Shore},
Publisher = {American Mathematical Society},
Title = {Natural definability in degree structures},
Year = {2000}}
@incollection{Shore:02,
Author = {Richert A. Shore},
Booktitle = {Computability Theory and Its Applications: Current Trends and Open Problems},
Editor = {Peter Cholak and Steffen Lempp and Manny Lerman and Richard Shore},
Publisher = {American Mathematical Society},
Title = {Natural definability in degree structure},
Year = {2002}}
@article{Shore:75,
Author = {Richard A. Shore},
Journal = {Trans. Amer. Math. Soc.},
Pages = {65--78},
Title = {Splitting an $\alpha$-Recursively Enumerable Set},
Volume = {204},
Year = {1975}}
@article{Shore:76,
Author = {Shore, Richard A.},
Journal = {Ann. Math. Logic},
Pages = {123--155},
Title = {The recursively enumerable $\alpha$-degrees are dense},
Volume = {9},
Year = {1976}}
@article{Shore:77,
Author = {Richard A. Shore},
Journal = {Proc. Amer. Math. Soc.},
Pages = {318--325},
Title = {Determining Automorphisms of the Recursively Enumerable Sets},
Volume = {65},
Year = {1977}}
@inproceedings{Shore:78,
Address = {Amsterdam},
Author = {Shore, Richard A.},
Booktitle = {Generalized Recursion Theory II},
Editor = {J.~Fenstad, R.~O.~Gandy and G.~E.~Sacks},
Pages = {331--354},
Publisher = {North--Holland Publishing Co.},
Series = {Stud. Logic Foundations Math.},
Title = {On the $\forall\exists$-sentences of $\alpha$-recursion theory},
Volume = {94},
Year = {1978}}
@article{Shore:78*1,
Author = {Richard A. Shore},
Journal = {J. Symbolic Logic},
Pages = {322--330},
Title = {Nowhere Simple Sets and the Lattice of Recursively Enumerable Sets},
Volume = {43},
Year = {1978}}
@article{Shore:79,
Author = {Shore, R. A.},
Journal = {Proc. Nat. Acad. Sci. U.S.A.},
Pages = {4218-4219},
Title = {The homogeneity conjecture},
Volume = {76},
Year = {1979}}
@article{Shore:81,
Author = {Shore, Richard A.},
Journal = {J. London Math. Soc.},
Pages = {1--14},
Title = {The theory of the degrees below $0'$},
Volume = {24},
Year = {1981}}
@article{Shore:82,
Author = {Shore, Richard A.},
Journal = {J. Symbolic Logic},
Pages = {8--16},
Title = {On homogeneity and definability in the {T}uring degrees},
Volume = {47},
Year = {1982}}
@article{Shore:88,
Author = {Richard A. Shore},
Journal = {Ann. Pure Appl. Logic},
Pages = {277--303},
Title = {A Noninversion Theorem for the Jump Operator},
Volume = {40},
Year = {1988}}
@inproceedings{Shore:92,
Author = {Shore, R. A.},
Booktitle = {Set theory of the Continuum},
Editor = {H. Judah and W. Just and H. Woodin},
Pages = {123-135},
Publisher = {Springer--Verlag},
Series = {MSRI Publications 26},
Title = {Degrees of constructibility},
Volume = {26},
Year = {1992}}
@incollection{Shore:93,
Address = {Boston},
Author = {Shore, R. I.},
Booktitle = {Logical Methods},
Editor = {J. N. C. Crossley and J. Remmel and R. A. Shore and M. Sweedler},
Pages = {782-813},
Publisher = {Birkh\" auser},
Title = {On the strength of Fra\"\i ss\'e's conjecture},
Year = {1993}}
@inproceedings{Shore:93*1,
Author = {Shore, R. A.},
Booktitle = {Proc. IX Latin American Symposium on Mathematical Logic (part 1)},
Pages = {61-70},
Publisher = {Universidad Nacional del Sur, Bahia Blanca, Argentina},
Series = {Notas de Lo'gica Mathema'tica},
Title = {The theories of the T, tt and wtt r.\ e.\ degrees: undecidability and beyond},
Volume = {38},
Year = {1993}}
@incollection{Shore:99,
Author = {Richard Shore},
Booktitle = {Handbook of computability theory},
Chapter = {6},
Editor = {Edward R. Griffor},
Pages = {169--198},
Publisher = {North--Holland Publishing Co.},
Series = {Studies in Logic},
Title = {The recursively enumerable degrees},
Volume = {140},
Year = {1999}}
@incollection{Shore:nd*1,
Author = {Shore, R. A.},
Booktitle = {Proc. Symposium in Honor of Gerald Sacks' 60$^{th}$ birthday},
Editor = {T. Slaman},
Note = {To appear},
Title = {Conjectures and questions from Gerald Sacks's {\it Degrees of Unsolvability}}}
@article{Silver:70,
Author = {Jack Silver},
Journal = {J. Symbolic Logic},
Pages = {60--64},
Title = {Every analytic set is {R}amsey},
Volume = {35},
Year = {1970}}
@incollection{Simpson:77,
Address = {Amsterdam},
Author = {Simpson, Stephen G.},
Booktitle = {Handbook of Mathematical Logic},
Editor = {Jon Barwise},
Pages = {1133--1142},
Publisher = {North-Holland},
Title = {Degrees of unsolvability: a survey of results},
Year = {1977}}
@article{Simpson:77*1,
Author = {Simpson, Stephen G.},
Journal = {Ann. of Math. (2)},
Pages = {121--139},
Title = {First order theory of the degrees of recursive unsolvability},
Volume = {105},
Year = {1977}}
@article{Simpson:78,
Author = {Stephen G. Simpson},
Journal = {J. Symbolic Logic},
Pages = {135--138},
Title = {Sets which do not have subsets of every higher degree},
Volume = {43},
Year = {1978}}
@article{Simpson:84,
Author = {Stephen G. Simpson},
Journal = {J. Symbolic Logic},
Pages = {783--802},
Title = {Which set existence axioms are needed to prove the {C}auchy-{P}eano {T}heorem for ordinary differential equations?},
Volume = {49},
Year = {1984}}
@inproceedings{Simpson:85,
Address = {Heidelberg},
Author = {Stephen G. Simpson},
Booktitle = {Recursion Theory Week at Oberwolfach},
Pages = {357--371},
Publisher = {Springer--Verlag},
Series = {Lecture Notes in Mathematics},
Title = {Recursion theoretic aspects of the dual {R}amsey Theorem},
Volume = {1141},
Year = {1985}}
@inproceedings{Simpson:85*1,
Author = {Stephen G. Simpson},
Booktitle = {{H}arvey {F}riedman's Research on the Foundations of Mathematics},
Series = {Studies in Logic and the Found. of Mathematics},
Title = {Nonprovability of certain combinatorial properties of finite trees},
Volume = {117},
Year = {1985}}
@inproceedings{Simpson:87,
Author = {Stephen G. Simpson},
Booktitle = {Logic and Combinatorics},
Pages = {359--394},
Publisher = {American Mathematical Society},
Series = {Contemporary Mathematics},
Title = {Unprovable theorems and fast growing functions},
Volume = {65},
Year = {1987}}
@unpublished{Slaman.Soare:94,
Author = {Slaman, Theodore A. and Soare, Robert I.},
Note = {Preprint},
Title = {Extension of Embeddings in the Computably Enumerable Degrees},
Year = {1994}}
@article{Slaman.Soare:95,
Author = {Slaman, Theodore A. and Soare, Robert I.},
Journal = {Proc. Nat. Acad. Sci. U.S.A.},
Pages = {617--621},
Title = {Algebraic Aspects of the Computably Enumerable Degrees},
Volume = {92},
Year = {1995}}
@inproceedings{Slaman.Solovay:91,
Author = {Slaman, Theodore A. and Solovay, Robert},
Booktitle = {Fourth Annual Conference on Computational Learning Theory},
Pages = {379--383},
Publisher = {Morgan Kaufman, Los Altos, CA},
Title = {When oracles do not help},
Year = {1991}}
@unpublished{Slaman.Sorbi:95,
Author = {Slaman, Theodore A. and Sorbi, Andrea},
Note = {Preprint},
Title = {Quasi-minimal enumeration degrees and minimal {T}uring degrees},
Year = {1995}}
@incollection{Slaman.Steel:88,
Address = {Heidelberg},
Author = {Slaman, Theodore A. and Steel, John R.},
Booktitle = {Cabal Seminar 81-85},
Number = {1333},
Pages = {37--55},
Publisher = {Springer--Verlag},
Series = {Lecture Notes in Mathematics},
Title = {Definable functions on degrees},
Year = {1988}}
@article{Slaman.Steel:89,
Author = {Slaman, Theodore A. and Steel, John R.},
Journal = {J. Symbolic Logic},
Pages = {160--176},
Title = {Complementation in the {T}uring degrees},
Volume = {54},
Year = {1989}}
@article{Slaman.Woodin:86,
Author = {Slaman, Theodore A. and Woodin, W. Hugh},
Journal = {Illinois J. Math.},
Pages = {320--334},
Title = {Definability in the {T}uring degrees},
Volume = {30},
Year = {1986}}
@inproceedings{Slaman.Woodin:89,
Address = {Heidelberg},
Author = {Slaman, Theodore A. and Woodin, W. Hugh},
Booktitle = {Mathematical Logic and Applications},
Editor = {Juichi Shinoda and Theodore A. Slaman and T. Tugu\'e},
Pages = {178--188},
Publisher = {Springer--Verlag},
Title = {${\Sigma}_1$-Collection and the Finite Injury Method},
Year = {1989}}
@unpublished{Slaman.Woodin:89*1,
Author = {Slaman, T. A. and Woodin, W. H.},
Title = {Definability in the {$\protect\Delta^0_2$} Turing degrees},
Year = {1989}}
@unpublished{Slaman.Woodin:94,
Author = {Slaman, Theodore A. and Woodin, W. Hugh},
Note = {Preprint},
Title = {Definability in the enumeration degrees},
Year = {1994}}
@article{Slaman.Woodin:98,
Author = {Slaman, Theodore A. and Woodin, W. Hugh},
Coden = {APALD7},
Fjournal = {Annals of Pure and Applied Logic},
Issn = {0168-0072},
Journal = {Ann. Pure Appl. Logic},
Mrclass = {06A05 (03D80 03E15)},
Mrnumber = {99f:06002},
Note = {Conference on Computability Theory (Oberwolfach, 1996)},
Number = {1-3},
Pages = {253--261},
Title = {Extending partial orders to dense linear orders},
Volume = {94},
Year = {1998}}
@phdthesis{Slaman:81,
Author = {Slaman, Theodore A.},
School = {Harvard University},
Title = {Aspects of $E$-Recursion},
Year = {1981}}
@article{Slaman:83,
Author = {Slaman, Theodore A.},
Journal = {Nagoya Math. J.},
Pages = {107--120},
Title = {The extended plus-one hypothesis\ ---\ a relative consistency result},
Volume = {92},
Year = {1983}}
@incollection{Slaman:85,
Author = {Slaman, Theodore A.},
Booktitle = {Proceedings of Symposia in Pure Mathematics},
Pages = {195--213},
Publisher = {American Mathematical Society},
Title = {The ${E}$-recursively enumerable degrees are dense},
Volume = {42},
Year = {1985}}
@article{Slaman:85*1,
Author = {Slaman, Theodore A.},
Journal = {Ann. Pure Appl. Logic},
Pages = {79--106},
Title = {Reflection and forcing in ${E}$-recursion theory},
Volume = {29},
Year = {1985}}
@incollection{Slaman:85*2,
Address = {Heidelberg},
Author = {Slaman, Theodore A.},
Booktitle = {Proceedings of the Recursion Theory Conference in Oberwolfach, April 1984},
Pages = {372--404},
Publisher = {Springer--Verlag},
Series = {Lecture Notes in Mathematics},
Title = {Reflection and the priority method in ${E}$-recursion theory},
Volume = {1141},
Year = {1985}}
@article{Slaman:86,
Author = {Slaman, Theodore A.},
Journal = {J. Symbolic Logic},
Pages = {352--359},
Title = {On the {K}leene degrees of $\mathbf{\Pi}_1^1$ sets},
Volume = {51},
Year = {1986}}
@article{Slaman:86*1,
Author = {Slaman, Theodore A.},
Journal = {J. Symbolic Logic},
Pages = {453--461},
Title = {${\Sigma}_1$ definitions with parameters},
Volume = {51},
Year = {1986}}
@inproceedings{Slaman:89,
Author = {Slaman, Theodore A.},
Booktitle = {Logic Colloquium},
Title = {On Bounded Time {T}uring Reducibility on the Recursive Sets},
Year = {1989}}
@inproceedings{Slaman:91,
Address = {Heidelberg},
Author = {Slaman, Theodore A.},
Booktitle = {Proceedings of the International Congress of Mathematicians, Kyoto, 1990},
Pages = {303--316},
Publisher = {Springer--Verlag},
Title = {Degree Structures},
Volume = {I},
Year = {1991}}
@article{Slaman:91*1,
Author = {Slaman, Theodore A.},
Journal = {Ann. Pure Appl. Logic},
Pages = {1--25},
Title = {The density of infima in the recursively enumerable degrees},
Volume = {52},
Year = {1991}}
@unpublished{Slaman:93,
Author = {Theodore Slaman},
Note = {Continually updated since 1993},
Title = {Open Questions in Recursion Theory},
Url = {www.math.berkeley.edu/~slamam/qrt/qrt.pdf}}
@unpublished{Slaman:95,
Author = {Theodore A. Slaman},
Note = {Preprint},
Title = {Mathematical Definability},
Year = {1995}}
@incollection{Slaman:99,
Author = {Theodore Slaman},
Booktitle = {Handbook of computability theory},
Chapter = {5},
Editor = {Edward R. Griffor},
Pages = {155--168},
Publisher = {North--Holland Publishing Co.},
Series = {Studies in Logic},
Title = {The global structure of the {T}uring degrees},
Volume = {140},
Year = {1999}}
@article{Slobodskoi:81,
Author = {Slobodskoi, A. M.},
Journal = {Algebra i Logika},
Pages = {207-230},
Title = {Unsolvability of the universal theory of finite groups},
Volume = {20},
Year = {1981}}
@book{Smullyan:61,
Address = {Princeton, New Jersey},
Author = {R. Smullyan},
Note = {Annals of Mathematical Studies Vol 47},
Publisher = {Princeton University Press},
Title = {Theory of Formal Systems},
Year = {1961}}
@inproceedings{Soare.Stob:82,
Address = {Amsterdam},
Author = {Soare, Robert I. and Stob, M.},
Booktitle = {Proceedings of the Herbrand Symposium, Logic Colloquium '81},
Editor = {J. Stern},
Pages = {299--324},
Publisher = {North--Holland Publishing Co.},
Title = {Relative recursive enumerability},
Year = {1982}}
@incollection{Soare:00,
Author = {Robert I. Soare},
Booktitle = {Computability theory and its applications (Boulder, CO, 1999},
Pages = {279--307},
Publisher = {Amer. Math. Soc.},
Series = {Contemp. Math.},
Title = {Extensions, Automorphisms, and Definability},
Volume = {257},
Year = {2000}}
@article{Soare:72,
Author = {Robert I. Soare},
Journal = {Canad. J. Math.},
Pages = {1070--1078},
Title = {The Friedberg-Munchnik Theorem Reexamined},
Volume = {24},
Year = {1972}}
@article{Soare:74,
Author = {Soare, Robert I.},
Journal = {Ann. of Math. (2)},
Pages = {80--120},
Title = {Automorphisms of the lattice of recursively enumerable sets {I}: maximal sets},
Volume = {100},
Year = {1974}}
@article{Soare:76,
Author = {Robert I. Soare},
Journal = {J. Symbolic Logic},
Pages = {513--530},
Title = {The Infinite Injury Priority Method},
Volume = {41},
Year = {1976}}
@article{Soare:77,
Author = {Robert I. Soare},
Journal = {J. Symbolic Logic},
Pages = {545--563},
Title = {Computational Complexity, Speedable and Levelable Sets},
Volume = {42},
Year = {1977}}
@inproceedings{Soare:80,
Address = {Cambridge, UK},
Author = {Soare, R. I.},
Booktitle = {Recursion theory: Its generalizations and applications (Proceedings of Logic Colloquium '79, Leeds, August, 1979)},
Editor = {F. Drake and S. S. Wainer},
Number = {45},
Pages = {1-51},
Publisher = {Cambridge University Press},
Series = {London mathematical Society Lecture Notes Series},
Title = {Fundamental methods for constructing recursively enumerable degrees},
Year = {1980}}
@article{Soare:82,
Author = {Soare, Robert I.},
Journal = {Ann. Math. Logic},
Pages = {69--107},
Title = {Automorphisms of the lattice of recursively enumerable sets {II}: low sets},
Volume = {22},
Year = {1982}}
@book{Soare:87,
Address = {Heidelberg},
Author = {Soare, Robert I.},
Publisher = {Springer--Verlag},
Series = {Perspectives in Mathematical Logic, Omega Series},
Title = {Recursively Enumerable Sets and Degrees},
Year = {1987}}
@article{Soare:96,
Author = {Soare, Robert I.},
Fjournal = {The Bulletin of Symbolic Logic},
Issn = {1079-8986},
Journal = {Bull. Symbolic Logic},
Number = {3},
Pages = {284--321},
Title = {Computability and recursion},
Volume = {2},
Year = {1996}}
@unpublished{Soare:nd,
Author = {Soare, Robert I.},
Note = {To appear},
Title = {The New Extension Theorem}}
@article{Solon:92,
Author = {Boris Solon},
Journal = {Siberian Math. J.},
Pages = {211--214},
Title = {E-hiperimmune sets},
Volume = {33},
Year = {1992}}
@article{Solovay:78,
Author = {Robert M. Solovay},
Journal = {Trans. Amer. Math. Soc.},
Pages = {99--121},
Title = {Hyperarithmetically encodable sets},
Volume = {239},
Year = {1978}}
@unpublished{Solovay:84,
Author = {Solovay, R. M.},
Note = {Preliminary version, Unpublished)},
Title = {Degrees of models of true arithmetic},
Year = {1984}}
@article{Sorbi:90,
Author = {Sorbi, Andrea},
Journal = {Arch. Math. Logic},
Pages = {29--48},
Title = {On some filters and ideals of the {M}edvedev lattice},
Volume = {30},
Year = {1990}}
@inproceedings{Specker:71,
Author = {E. Specker},
Booktitle = {Logic Colloquium; 1969 Manchester},
Pages = {439--442},
Title = {{R}amsey's {T}heorem does not hold in recursive set theory},
Year = {1971}}
@article{Spector:56,
Annote = {Also proves the existence of a minimal degree},
Author = {Spector, C.},
Journal = {Ann. of Math. (2)},
Pages = {581--592},
Title = {On the degrees of recursive unsolvability},
Volume = {64},
Year = {1956}}
@article{Steel:82,
Author = {John R. Steel},
Journal = {J. Symbolic Logic},
Pages = {347--358},
Title = {A Classification of Jump Operators},
Volume = {47},
Year = {1982}}
@phdthesis{Stob:79,
Author = {M. Stob},
School = {University of Chicago},
Title = {The Structure and Elementary Theory of the Recursive Enumerable Sets},
Year = {1979}}
@article{Stob:82,
Author = {M. Stob},
Journal = {J. Symbolic Logic},
Pages = {241--248},
Title = {Index Sets and Degrees of Unsolvability},
Volume = {47},
Year = {1982}}
@article{Stob:82*1,
Author = {M. Stob},
Journal = {Pacific J. Math.},
Pages = {445--471},
Title = {Invariance of Properties under Automorphisms of the Lattice of Recursively Enumerable Sets},
Volume = {100},
Year = {1982}}
@article{Stob:83,
Author = {M. Stob},
Journal = {J. Symbolic Logic},
Pages = {921--930},
Title = {wtt-Degrees and T-Degrees of Recursively Enumerable Sets},
Volume = {48},
Year = {1983}}
@article{Stone:36,
Author = {Stone, M.},
Journal = {Trans. Amer. Math. Soc.},
Pages = {37-111},
Title = {The theory of representations for Boolean algebras},
Volume = {40},
Year = {1936}}
@article{Sui:93,
Author = {Sui, Y.},
Journal = {Acta Math. Sinica},
Title = {On the problem of critical bound},
Year = {1993}}
@book{Takeuti:87,
Address = {Amsterdam},
Author = {Takeuti, Gaisi},
Edition = {Second},
Isbn = {0-444-87943-9},
Note = {With an appendix containing contributions by Georg Kreisel, Wolfram Pohlers, Stephen G. Simpson and Solomon Feferman},
Pages = {x+490},
Publisher = {North-Holland Publishing Co.},
Series = {Studies in Logic and the Foundations of Mathematics},
Title = {Proof theory},
Volume = {81},
Year = {1987}}
@article{Tarski:31,
Author = {A. Tarski},
Journal = {Fund. Math.},
Pages = {210--239},
Title = {Sur les ensembles d\'efinissables des nombres r\'eels},
Volume = {17},
Year = {1931}}
@article{Tarski:36,
Author = {Tarski, A.},
Journal = {Studia Philosophica},
Pages = {261--405},
Title = {Der Wahrheitsbegriff in den formalisierten Sprachten},
Volume = {1},
Year = {1936}}
@article{Tarski:49,
Author = {A. Tarski},
Journal = {J. Symbolic Logic},
Pages = {75--76},
Title = {On essential undecidability},
Volume = {14},
Year = {1949}}
@article{Thomason:71,
Author = {Thomason, S. K.},
Journal = {Z. Math. Logik Grundlag. Math.},
Pages = {273--280},
Title = {Sublattices of the recursively enumerable degrees},
Volume = {17},
Year = {1971}}
@unpublished{Thurber:nd,
Author = {Thurber, J. J.},
Note = {To appear},
Title = {Recursive and r.e. quotient Boolean algebras}}
@unpublished{Thurber:nd*1,
Author = {Thurber, J.J.},
Note = {To appear},
Title = {Every low$_2$ Boolean algebra has a recursive copy}}
@article{Trakhtenbrot:53,
Author = {Trakhtenbrot, B. A.},
Journal = {Dokl. Akad. Nauk SSSR},
Pages = {953-956},
Title = {Recursive separability},
Volume = {88},
Year = {1953}}
@article{Trakhtenbrot:55,
Author = {B. A. Trakhtenbrot},
Journal = {Dokl. Akad. Nauk SSSR},
Pages = {417--420},
Title = {Tabular representation of recursive operators},
Volume = {101},
Year = {1955}}
@article{Trakhtenbrot:64,
Author = {B. A. Trakhtenbrot},
Journal = {Algebra i Logika},
Note = {(in Russian)},
Pages = {25--32},
Title = {On the frequency computation of functions},
Volume = {2},
Year = {1964}}
@article{Turing:36,
Author = {Turing, Alan M.},
Journal = {Proc. London Math. Soc. (3)},
Note = {A correction, 43:544--546},
Pages = {230--265},
Title = {On computable numbers with an application to the {E}ntscheidungsproblem},
Volume = {42},
Year = {1936}}
@article{Turing:39,
Author = {Turing, Alan M.},
Journal = {Proc. London Math. Soc. (3)},
Pages = {161--228},
Title = {Systems of logic based on ordinals},
Volume = {45},
Year = {1939}}
@article{Tverberg:84,
Author = {Helga Tverberg},
Journal = {J. Combin. Theory Ser. B},
Pages = {27--30},
Title = {On {S}chmerl's effective version of {B}rooks's Theorem},
Volume = {37},
Year = {1984}}
@article{Valiant:84,
Author = {Leslie G. Valiant},
Journal = {Communications of the ACM},
Pages = {1134--1142},
Title = {A Theory of the Learnable},
Volume = {27},
Year = {1984}}
@phdthesis{Wald:99,
Author = {Kevin Wald},
School = {University of Chicago},
Title = {Automorphism and noninvariant properites of the computably enumerable sets},
Year = {1999}}
@book{Wang:81,
Address = {New York},
Author = {Hao Wang},
Publisher = {Van Nostrand Reinhold Company and Science Press},
Title = {Popular Lectures on Mathematical Logic},
Year = {1981}}
@phdthesis{Weinstein:88,
Author = {Barry Weinstein},
School = {University of California, Berkeley},
Title = {On Embedding of the Lattice 1-3-1 into the Recursively Enumerable Degrees},
Year = {1988}}
@phdthesis{Welch:81,
Author = {Welch, L.},
School = {University of Illinois at Urbana-Champaign},
Title = {A Hierarchy of Families of Recursively Enumerable Degrees and a Theorem on Bounding Minimal Pairs},
Year = {1981}}
@article{Yates:65,
Author = {C. E. M. Yates},
Journal = {Duke Math. J.},
Pages = {461--468},
Title = {Three Theorems of the Degrees of Recursively Enumerable Sets},
Volume = {32},
Year = {1965}}
@article{Yates:66,
Author = {Yates, C.E.M.},
Journal = {Trans. Amer. Math. Soc.},
Pages = {309-328},
Title = {On the degrees of index sets},
Volume = {121},
Year = {1966}}
@article{Yates:66*1,
Author = {Yates, C. E. M.},
Journal = {J. Symbolic Logic},
Pages = {159--168},
Title = {A minimal pair of recursively enumerable degrees},
Volume = {31},
Year = {1966}}
@inproceedings{Yates:70,
Address = {Amsterdam},
Author = {Yates, C.E.M.},
Booktitle = {Proceedings of an international colloquium, Jerusalem, Nov. 11-14,1968)},
Editor = {Y. Bar-Hillel},
Pages = {63-83},
Series = {Mathematical logic and foundation of set theory},
Title = {Initial segments of the degrees of unsolvability, Part I: A survey},
Year = {1970}}
@article{Yates:70*1,
Author = {Yates, C.E.M.},
Journal = {J. Symbolic Logic},
Pages = {243-266},
Title = {Initial segments of the degrees of unsolvability, Part II: Minimal degrees},
Volume = {35},
Year = {1970}}
@article{Yates:74,
Author = {Yates, C.E.M.},
Journal = {Fund. Math.},
Pages = {217-237},
Title = {Prioric games and minimal degrees below $0^\prime$},
Volume = {82},
Year = {1974}}
@article{Yates:76,
Author = {Yates, C.E.M.},
Journal = {Math. Proc. Cambridge Philos. Soc.},
Pages = {195-220},
Title = {Banach-Mazur games, comeager sets and degrees of unsolvability},
Volume = {79},
Year = {1976}}
@unpublished{Yi:nd,
Author = {Yi, X.},
Note = {To appear},
Title = {A non-splitting theorem for d.r.e. sets}}