Arbeitsgruppe Mathematische Logik und Theoretische Informatik 

Schriftenverzeichnis von Klaus Ambos-Spies 

(A) Artikel in Zeitschriften

(A01)

An extension of the nondiamond theorem in classical and alpha-recursion theory.
Journal of Symbolic Logic 49 (1984) 586-607.

(A02)

(gemeinsam mit C.G. Jockusch, Jr., R.A. Shore und R.I. Soare)
An algebraic decomposition of the recursively enumerable degrees and the coincidence of several degree classes with the promptly simple degrees.
Transactions of the American Mathematical Society 281 (1984) 109-128.

(A03)

On pairs of recursively enumerable degrees.
Transactions of the American Mathematical Society 283 (1984) 507-531.

(A04)

Anti-mitotic recursively enumerable degrees.
Zeitschrift für mathematische Logik und Grundlagen der Mathematik 31 (1985) 461-477.

(A05)

Cupping and noncapping in the r.e. weak truth table and Turing degrees.
Archiv für mathematische Logik und Grundlagenforschung 25 (1985) 109-126.

(A06)

Sublattices of the polynomial time degrees.
Information and Control 65 (1985) 63-84.

(A07)

An inhomogeneity in the structure of Karp degrees.
SIAM Journal on Computing 15 (1986) 958-63.

(A08)

Inhomogeneities in the polynomial time degrees: the degrees of super sparse sets.
Information Processing Letters 22 (1986) 113-117.

(A09)

(gemeinsam mit M. Lerman)
Lattice embeddings into the recursively enumerable degrees.
Journal of Symbolic Logic 51 (1986) 257-272.

(A10)

A note on complete problems for complexity classes.
Information Processing Letters 23 (1986) 227-230.

(A11)

(gemeinsam mit H. Fleischhack und H. Huwig)
Diagonalizations over polynomial time computable sets.
Theoretical Computer Science 51 (1987) 177-204.

(A12)

(gemeinsam mit P.A. Fejer)
Degree theoretic splitting properties of recursively enumerable sets.
Journal of Symbolic Logic 53 (1988) 1110-1137.

(A13)

On the relative complexity of hard problems for complexity classes without complete problems.
Theoretical Computer Science 63 (1989) 43-61.

(A14)

(gemeinsam mit M. Lerman)
Lattice embeddings into the recursively enumerable degrees, part II.
Journal of Symbolic Logic 54 (1989) 735-760.

(A15)

(gemeinsam mit R.I. Soare)
The recursively enumerable degrees have infinitely many one types.
Annals of Pure and Applied Logic 44 (1989) 1-23.

(A16)

Honest polynomial time reducibilities and the P=?NP problem.
Journal of Computer and System Sciences 39 (1989) 250-281.

(A17)

(gemeinsam mit A. Nies und R. Shore)
The theory of the recursively enumerable weak-truth-table degrees is undecidable.
Journal of Symbolic Logic 57 (1992) 864-874.

(A18)

(gemeinsam mit A. Nies)
Cappable recursively enumerable degrees and Post's program.
Archive of Mathematical Logic 32 (1992) 51-56.

(A19)

(gemeinsam mit R. Shore)
Undecidability and 1-types in the recursively enumerable degrees.
Annals of Pure and Applied Logic 63 (1993) 3-37.

(A20)

(gemeinsam mit A. Lachlan und R.I. Soare)
The continuity of cupping to 0'.
Annals of Pure and Applied Logic 64 (1993) 195-209.

(A21)

(gemeinsam mit M. Lerman und S. Lempp)
Lattice embeddings into the r.e. degrees preserving 0 and 1.
Journal of the London Mathematical Society (2) 49 (1994) 1-15.

(A22)

(gemeinsam mit S. Homer und R.I. Soare)
On minimal pairs and complete problems.
Theoretical Computer Science 132 (1994) 229-241.

(A23)

(gemeinsam mit D. Ding)
Discontinuity of cappings in the recursively enumerable degrees and strongly nonbranching degrees. Mathematical Logic Quarterly 40 (1994) 287-317.

(A24)

(gemeinsam mit D. Yang)
Some methods used in the research of structural polynomial complexity (Chinesisch).
Advances in Mathematics (China) 24 (1995) 289-298.

(A25)

(gemeinsam mit H.-C. Neis und S. A. Terwijn)
Genericity and measure for exponential time.
Theoretical Computer Science 168 (1996) 3-19.

(A26)

(gemeinsam mit P. A. Fejer, S. Lempp und M. Lerman)
The two quantifier theory of the r.e. weak-truth-table degrees is decidable.
Journal of Symbolic Logic 61 (1996) 880-905.

(A27)

(gemeinsam mit S. A. Terwijn und X. Zheng)
Resource bounded randomness and weakly complete problems.
Theoretical Computer Science 172 (1997) 195-207.

(A28)

(gemeinsam mit S. B. Cooper und S. Lempp)
Initial segments of recursive linear orders.
Order 14 (1998) 101-105.

(A29)

(gemeinsam mit D. R. Hirschfeld und R. A. Shore)
Undecidability and 1-types in intervals of the computablly enumerable degrees.
Annals of Pure and Applied Logic 106 (2000) 1-47.

(A30)

(gemeinsam mit L. Bentzien)
Separating NP-completeness notions under strong hypotheses.
Journal of Computer and System Sciences 61 (2000) 335-361.

(A31)

On optimal polynomial time approximations.
Erscheint in RAIRO Theoretical Informatics.

(A32)

(gemeinsam mit K. Weihrauch und X. Zheng)
Weakly computable real numbers.
Journal of Complexity 16 (2000) 676-690.

(A33)

(gemeinsam mit W. Merkle, J. Reimann und S.A. Terwijn)
Almost complete sets.
Erscheint in Theoretical Computer Science.

(A34)

(gemeinsam mit P. A. Fejer)
Embeddings of N5 and the contiguous degrees.
Erscheint in Annals of Pure and Applied Logic.

(B) Beiträge in Tagungs- und Sammelbänden

(B01)

On the structure of polynomial time degrees.
In "STACS 84, Symposium on Theoretical Aspects of Computer Science, Paris, April 1984" (M. Fontet u. K. Mehlhorn, Hg.), Lecture Notes in Computer Science, Band 166 (1984) 198-208, Springer-Verlag.

(B02)

P-mitotic sets.
In "Logic and Machines: Decision Problems and Complexity, Proceedings" (E. Börger, G. Hasenjaeger und D. Rödding, Hg.), Lecture Notes in Computer Science, Band 171 (1984) 1-23, Springer-Verlag.
(Um einen Anhang erweiterte Fassung in Forschungsbericht Nr. 167 (1983) der Abteilung Informatik, Universität Dortmund).

(B03)

(gemeinsam mit H. Fleischhack und H. Huwig)
P-generic sets.
In "Automata, Languages and Programming, 11th Colloquium, Antwerp, Belgium, July 1984" (J. Paredaens, Hg.), Lecture Notes in Computer Science, Band 172 (1984) 58-68, Springer-Verlag.
(Ausführliche Fassung: s. (A11).)

(B04)

Contiguous r.e. degrees.
In "Computation and Proof Theory, Proceedings, Logic Colloquium Aachen 1983, Part II" (M.M. Richter, E. Börger, W. Oberschelp, B. Schinzel und W. Thomas, Hg.), Lecture Notes in Mathematics, Band 1104 (1984) 1-37, Springer-Verlag.

(B05)

On the relative complexity of subproblems of intractable problems.
In "STACS 85, 2nd Annual Symposium on Theoretical Aspects of Computer Science, Saarbrücken, January 1985" (K. Mehlhorn, Hg.), Lecture Notes in Computer Science, Band 182 (1985) 1-12, Springer-Verlag.

(B06)

Generators of the recursively enumerable degrees.
In "Recursion Theory Week, Proceedings, Oberwolfach 1984" (H.-D. Ebbinghaus, G.H. Müller und G.E. Sacks, Hg.), Lecture Notes in Mathematics, Band 1141 (1985) 1-28, Springer-Verlag.

(B07)

Three theorems on polynomial degrees of NP-sets.
In "26th Annual Symposium on Foundations of Computer Science", 1985, 51-55, IEEE Computer Society Press.

(B08)

Randomness, relativizations, and polynomial reducibilities.
In "Structure in Complexity Theory Conference, Proceedings of the Conference held at the University of California, Berkeley, California, June 1986" (A.L. Selman, Hg.), Lecture Notes in Computer Science, Band 223 (1986) 23-34, Springer-Verlag.

(B09)

Honest polynomial reducibilities, recursively enumerable sets, and the P=?NP problem.
In "Proceedings Structure in Complexity Theory, Second Annual Conference", 1987, 60-68, IEEE Computer Society Press.
(Ausführliche Fassung des ersten Teils: s. (A16).)

(B10)

Polynomial time degrees of NP-sets.
In "Trends in Theoretical Computer Science" (E. Börger, Hg.), 1987, 95-142, Computer Science Press.

(B11)

Minimal pairs for polynomial time reducibilities.
In "Computation Theory and Logic" (E. Börger, Hg.), Lecture Notes in Computer Science, Band 270 (1987) 1-13, Springer-Verlag.

(B12)

(gemeinsam mit H. Fleischhack und H. Huwig)
Diagonalizing over deterministic polynomial time.
In "CSL '87, 1st Workshop on Computer Science Logic, Karlsruhe, FRG, October 1987, Proceedings" (E. Börger, H. Kleine Büning und M.M. Richter, Hg.), Lecture Notes in Computer Science, Band 329 (1988) 1-16, Springer-Verlag.

(B13)

(gemeinsam mit J. Kämper)
On disjunctive selfreducibility.
In "CSL '88, 2nd Workshop on Computer Science Logic, Duisburg, FRG, October 1988, Proceedings" (E. Börger, H. Kleine Büning und M.M. Richter, Hg.), Lecture Notes in Computer Science, Band 385 (1989) 1-13, Springer-Verlag.

(B14)

(gemeinsam mit S. Homer und R.I. Soare)
On minimal pairs and complete problems.
In "STACS 90, 7th Annual Symposium on Theoretical Aspects of Computer Science, Rouen, France, February 1990, Proceedings" (C. Choffrut und T. Lengauer, Hg.), Lecture Notes in Computer Science, Band 415 (1990) 24-36, Springer-Verlag.
(Endgültige Fassung: s. (A22).)

(B15)

(gemeinsam mit D. Yang)
Honest polynomial time degrees of elementary recursive sets.
In "CSL '89, 3rd Workshop on Computer Science Logic, Kaiserslautern, FRG, October 1989, Proceedings" (E. Börger, H. Kleine Büning und M.M. Richter, Hg.)", Lecture Notes in Computer Science, Band 440 (1990) 1-15, Springer-Verlag.

(B16)

(gemeinsam mit S. Homer und D. Yang)
Honest polynomial reductions and exptally sets.
In "Recursion Theory Week, Proceedings, Oberwolfach 1989" (K. Ambos-Spies, G.H. Müller und G.E. Sacks, Hg.), Lecture Notes in Mathematics, Band 1432 (1990) 1-22, Springer-Verlag.

(B17)

(gemeinsam mit A. Nies)
The theory of the polynomial many-one degrees of recursive sets is undecidable.
In "STACS 92, 9th Annual Symposium on Theoretical Aspects of Computer Science, Cachan, France, February 1992, Proceedings" (A. Finkel und M. Jantzen, Hg.), Lecture Notes in Computer Science, Band 577 (1992) 209-218, Springer-Verlag.

(B18)

(gemeinsam mit D. Ding und P. A. Fejer)
Embedding distributive lattices preserving 1 below a nonzero recursively enumerable Turing degree.
In "Logical Methods: In Honor of Anil Nerode's Sixtieth Birthday" (J.N. Crossley, J.B. Remmel, R.A. Shore und M.E. Sweedler, Hg.), Progress in Computer Science and Applied Logic, Band 12 (1993) 92-129, Birkhäuser.

(B19)

(gemeinsam mit S.A. Terwijn und X. Zheng)
Resource bounded randomness and weakly complete problems.
In "Algorithms and Computation, 5th International Symposium, ISAAC '94, Beijing, P. R. China, August 1994, Proceedings" (D.-Z. Du und X.-S. Zhang, Hg.), Lecture Notes in Computer Science, Band 834 (1994) 369-377, Springer-Verlag.
(Endgültige Fassung: s. (A27).)

(B20)

(gemeinsam mit H.-C. Neis und S. A. Terwijn)
Genericity and measure for exponential time.
In "Mathematical Foundations of Computer Science 1994, 19th International Symposium, MFCS '94, Kosice, Slovakia, August 1994, Proceedings" (I. Privara, B. Rovan und P. Ruzicka, Hg.), Lecture Notes in Computer Science, Band 841 (1994) 221-232, Springer-Verlag.
(Endgültige Fassung: s. (A24).)

(B21)

(gemeinsam mit S. Lempp und M. Lerman)
Lattice embeddings into the r.e. degrees preserving 1.
In "Logic, Methodology and Philosophy of Science IX" (D. Prawitz et al., Hg.), 1994, 179-198, North Holland.

(B22)

On optimal polynomial time approximations: P-levelability vs. Delta-levelability.
In "Automata, Languages and Programming, 22nd International Colloquium, ICALP 95, Szeged, Hungary, July 1995, Proceedings" (Z. Fülöp und F. Gécseg, Hg.), Lecture Notes in Computer Science, Band 944 (1995) 384-392, Springer.
(Endgültige Fassung: s. (A31).)

(B23)

Resource-bounded genericity.
In "Proceedings Structure in Complexity Theory, Tenth Annual Conference, June 19-22, 1995, Minneapolis, Minnesota", 1995, 162-181, IEEE Computer Society Press.
(Endgültige Fassung: s. (B24).)

(B24)

Resource-bounded genericity.
In "Computability, Enumerability, Unsolvability. Directions in recursion theory" (S.B. Cooper, T.A. Slaman und S.S. Wainer, Hg.), London Mathematical Society Lecture Notes Series, Band 224 (1996) 1-59, Cambridge University Press.

(B25)

(gemeinsam mit E. Mayordomo, Y. Wang und X. Zheng)
Resource-bounded balanced genericity, stochasticity and weak randomness.
In "STACS 96, 13th Annual Symposium on Theoretical Aspects of Computer Science, Grenoble, France, February 1996, Proceedings" (C. Puech und R. Reischuk, Hg.), Lecture Notes in Computer Science, Band 1046 (1996) 63-74, Springer.

(B26)

(gemeinsam mit E. Mayordomo und X. Zheng)
A comparison of weak completeness notions.
In "Proceedings Eleventh Annual IEEE Conference on Computational Complexity (Formerly: Structure in Complexity Theory Conference), May 24-27, 1996, Philadelphia, Pennsylvania", 1996, 171-178, IEEE Computer Society Press.

(B27)

(gemeinsam mit E. Mayordomo)
Resource-bounded measure and randomness.
In "Complexity, Logic, and Recursion Theory" (A. Sorbi, Hg.), Lecture Notes in Pure and Applied Mathematics, Band 187 (1997) 1-47, Marcel Dekker.

(B28)

(gemeinsam mit L. Bentzien)
Separating NP-completeness notions under strong hypotheses.
In "Proceedings Twelfth Annual IEEE Conference on Computational Complexity (Formerly: Structure in Complexity Theory Conference), June 24-27, 1997, Ulm, Germany", 1997, 121-127, IEEE Computer Society Press.
(Endgültige Fassung: s. (A30).)

(B29)

(gemeinsam mit J. Reimann)
Effective Baire catgorie concepts.
In "Proceedings of the Sixth Asian Logic Conference, Beijing, China, 20-24 May 1996" (C.T. Chong, Q. Feng, D. Ding, Q. Huang und M. Yasugi, Hg.), 1998, 13-29, World Scientific, Singapore University Press.

(B30)

(gemeinsam mit S. Lempp und G. Mainhardt)
Randomness vs. completeness: On the diagonalization strength of resource-bounded random sets.
In "Mathematical Foundations of Computer Science 1998, 23rd International Symposium, MFCS '98, Brno, Czech Republic, August 1998, Proceedings" (L. Brim, J. Gruska und J. Zlatuska, Hg.), Lecture Notes in Computer Science, Band 1450 (1998) 465-473, Springer.

(B31)

Algorithmic randomness revisited.
In "Language, Logic and Formalization of Knowledge. Coimbra Lecture and Proceedings of a Symposium held in Siena in September 1997" (B. McGuinness, Hg.), 1998, 33-52, Bibliotheca.

(B32)

Polynomial time reducibilities and degrees.
In "Handbook of Computability Theory" (E. Griffor, Hg.), Studies in Logic and the Foundations of Mathematics, Band 140 (1999) 683-705, Elsevier.

(B33)

(gemeinsam mit L. Bentzien, P. A. Fejer, W. Merkle und F. Stephan)
Collapsing polynomial-time degrees.
In "Logic Colloquium '98, Proceedings of the Annual European Summer Meeting of the Association for Symbolic Logic, held in Prague, Czech Republic, August 9-15, 1998" (S.R. Buss, P. Hájek, P. Pudlák, Hg.), Lecture Notes in Logic 13 (1999) 1-24, Association for Symbolic Logic.

(B34)

(gemeinsam mit W. Merkle, J. Reimann und S. A. Terwijn)
Almost complete sets.
In "STACS 2000, 17th Annual Symposium on Theoretical Aspects of Computer Science, Lille, France, February 2000, Proceedings" (H. Reichel und S. Tison, Hg.), Lecture Notes in Computer Science, Band 1770 (2000) 419-430, Springer.
(Ausführliche Fassung: s. (A33).)

(B35)

(gemeinsam mit A. Kucera)
Randomness in computability.
"Computability Theory: Current Trends and Open Problems" (P. Cholak et al., Hg.), Contemporary Mathematics, Band 257 (2000) 1-14, American Mathematical Society.

(B36)

Measure theoretic completeness notions for the exponential time classes.
In "Mathematical Foundations of Computer Science 2000, 25th International Symposium, MFCS 2000, Bratislava, Slovakia, August/September 2000, Proceedings" (M. Nielsen and B. Rovan, Hg.), Lecture Notes in Computer Science, Band 1893 (2000) 152-161, Springer.

(B37)

(gemeinsam mit W. Merkle, J. Reimann und F. Stephan)
Hausdorff Dimension in Exponential Time.
In "Proceedings Sixteenth Annual IEEE Conference on Computational Complexity (Formerly: Structure in Complexity Theory Conference), 18-21 June 2001, Chicago, IL", 2001, 210-217, IEEE Computer Society Press.

(C) Sonstige Arbeiten

(C01)

Die Unvollständigkeitssätze von Gödel und Rosser für halbformale Systeme der Zahlentheorie
Diplomarbeit, 121 Seiten, Fakultät für Mathematik, Ludwig-Maximilians-Universität München, 1976.

(C02)

On the Structure of the Recursively Enumerable Degrees.
Dissertation, 160+ix Seiten, Fakultät für Mathematik, Ludwig-Maximilians-Universität München, 1980.

(C03)

On the Structure of the Polynomial Time Degrees of Recursive Sets.
Habilitationsschrift, 97 Seiten, Abteilung Informatik, Universität Dortmund, 1984. Erschienen als Forschungsbericht 206 (1985) der Abteilung Informatik der Universität Dortmund.

(C05)

A note on recursively approximable real numbers.
Forschungsbericht Mathematische Logik 38 (September 1998), 7 Seiten, Universität Heidelberg.

(D) Herausgegebene Bände

(D01)

(gemeinsam mit G.H. Müller und G.E. Sacks)
Recursion Theory Week, Proceedings, Oberwolfach.
Lecture Notes in Mathematics, Band 1432, 1990, Springer-Verlag, 393+vi Seiten.

(D02)

(gemeinsam mit S. Homer und U. Schöning)
Complexity Theory, Current Research.
Cambridge University Press, 1993, 313+viii Seiten.

(D03)

(gemeinsam mit T.A. Slaman und R.I. Soare)
Conference on computability theory. Proceedings of the conference, Oberwolfach, Germany, January 27 - February 3, 1996.
Sonderheft der Annals of Pure and Applied Logic, Band 94, 1998, 296+vi Seiten.

(E) Zur Veröffentlichung eingereichte Arbeiten