![](https://dblp.uni-trier.de/img/logo.ua.320x120.png)
![](https://dblp.uni-trier.de/img/dropdown.dark.16x16.png)
![](https://dblp.uni-trier.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp.uni-trier.de/img/search.dark.16x16.png)
![search dblp](https://dblp.uni-trier.de/img/search.dark.16x16.png)
default search action
Klaus Ambos-Spies
Person information
- affiliation: Heidelberg University, Germany
Refine list
![note](https://dblp.uni-trier.de/img/note-mark.dark.12x12.png)
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
Books and Theses
- 1985
- [b1]Klaus Ambos-Spies:
On the structure of the polynomial time degrees of recursive sets. University of Dortmund, Germany, Forschungsberichte 206, 1985
Journal Articles
- 2024
- [j44]Klaus Ambos-Spies, Rod Downey, Martin Monath:
Lowness properties for strong reducibilities and the computational power of maximal sets. Comput. 13(1): 1-56 (2024) - 2022
- [j43]Klaus Ambos-Spies
, Wolfgang Merkle, Sebastiaan A. Terwijn:
Normalized information distance and the oscillation hierarchy. J. Comput. Syst. Sci. 124: 65-76 (2022) - 2021
- [j42]Klaus Ambos-Spies, Rodney G. Downey, Martin Monath:
On Supersets of non-low 22_2 Sets. J. Symb. Log. 86(3): 1282-1292 (2021) - 2019
- [j41]Klaus Ambos-Spies, Timur Bakibayev
:
Weak Completeness Notions for Exponential Time. Theory Comput. Syst. 63(6): 1388-1412 (2019) - 2018
- [j40]Klaus Ambos-Spies:
Automorphism bases for the recursively enumerable degrees. Comput. 7(2-3): 237-258 (2018) - 2013
- [j39]Klaus Ambos-Spies, Philipp Bodewig, Yun Fan, Thorsten Kräling:
The partial orderings of the computably enumerable ibT-degrees and cl-degrees are not elementarily equivalent. Ann. Pure Appl. Log. 164(5): 577-588 (2013) - [j38]Klaus Ambos-Spies, Joan Bagaria
, Enrique Casanovas
, Ulrich Kohlenbach:
Preface. Ann. Pure Appl. Log. 164(12): 1177 (2013) - [j37]Klaus Ambos-Spies, Arnold Beckmann, Erzsébet Csuhaj-Varjú, Benedikt Löwe:
Computability in Europe 2009. J. Log. Comput. 23(4): 727-728 (2013) - [j36]Klaus Ambos-Spies, Decheng Ding, Yun Fan, Wolfgang Merkle:
Maximal Pairs of Computably Enumerable Sets in the Computably Lipschitz Degrees. Theory Comput. Syst. 52(1): 2-27 (2013) - [j35]Klaus Ambos-Spies, Timur Bakibayev
:
Nontriviality for exponential time w.r.t. weak reducibilities. Theor. Comput. Sci. 494: 2-12 (2013) - 2012
- [j34]Klaus Ambos-Spies, Arnold Beckmann, Samuel R. Buss, Benedikt Löwe:
Computability in Europe 2009. Ann. Pure Appl. Log. 163(5): 483-484 (2012) - [j33]Klaus Ambos-Spies, Timur Bakibayev
:
Comparing Nontriviality for E and EXP. Theory Comput. Syst. 51(1): 106-122 (2012) - 2011
- [j32]Klaus Ambos-Spies, Serikzhan A. Badaev
, Sergey S. Goncharov:
Inductive inference and computable numberings. Theor. Comput. Sci. 412(18): 1652-1668 (2011) - 2010
- [j31]Klaus Ambos-Spies, Thorsten Kräling:
Quantitative aspects of speed-up and gap phenomena. Math. Struct. Comput. Sci. 20(5): 707-722 (2010) - 2009
- [j30]Klaus Ambos-Spies, Decheng Ding, Wei Wang, Liang Yu:
Bounding non-GL2 and R.E.A. J. Symb. Log. 74(3): 989-1000 (2009) - 2004
- [j29]Klaus Ambos-Spies, Bjørn Kjos-Hanssen, Steffen Lempp, Theodore A. Slaman:
Comparing DNR and WWKL. J. Symb. Log. 69(4): 1089-1104 (2004) - 2003
- [j28]Klaus Ambos-Spies, Wolfgang Merkle, Jan Reimann, Sebastiaan Terwijn:
Almost complete sets. Theor. Comput. Sci. 306(1-3): 177-194 (2003) - 2001
- [j27]Klaus Ambos-Spies, Peter A. Fejer:
Embedding of N5 and the contiguous degrees. Ann. Pure Appl. Log. 112(2-3): 151-188 (2001) - 2000
- [j26]Klaus Ambos-Spies, Denis R. Hirschfeldt, Richard A. Shore:
Undecidability and 1-types in intervals of the computably enumerable degrees. Ann. Pure Appl. Log. 106(1-3): 1-47 (2000) - [j25]Klaus Ambos-Spies, Klaus Weihrauch, Xizhong Zheng:
Weakly Computable Real Numbers. J. Complex. 16(4): 676-690 (2000) - [j24]Klaus Ambos-Spies, Levke Bentzien:
Separating NP-Completeness Notions under Strong Hypotheses. J. Comput. Syst. Sci. 61(3): 335-361 (2000) - 1997
- [j23]Klaus Ambos-Spies, Sebastiaan Terwijn, Xizhong Zheng:
Resource Bounded Randomness and Weakly Complete Problems. Theor. Comput. Sci. 172(1-2): 195-207 (1997) - 1996
- [j22]Klaus Ambos-Spies, Peter A. Fejer, Steffen Lempp, Manuel Lerman:
Decidability of the Two-Quantifier Theory of the Recursively Enumerable Weak Truth-Table Degrees and Other Distributive Upper Semi-Lattices. J. Symb. Log. 61(3): 880-905 (1996) - [j21]Klaus Ambos-Spies, Hans-Christian Neis, Sebastiaan Terwijn:
Genericity and Measure for Exponential Time. Theor. Comput. Sci. 168(1): 3-19 (1996) - 1994
- [j20]Decheng Ding, Klaus Ambos-Spies:
Discontinuity of Cappings in the Recursively Enumerable Degrees and Strongly Nonbranching Degrees. Math. Log. Q. 40: 287-317 (1994) - [j19]Klaus Ambos-Spies, Steven Homer, Robert I. Soare:
Minimal Pairs and Complete Problems. Theor. Comput. Sci. 132(2): 229-241 (1994) - 1993
- [j18]Klaus Ambos-Spies, Richard A. Shore:
Undecidability and 1-Types in the Recursively Enumerable Degrees. Ann. Pure Appl. Log. 63(1): 3-37 (1993) - [j17]Klaus Ambos-Spies, Alistair H. Lachlan, Robert I. Soare:
The Continuity of Cupping to 0'. Ann. Pure Appl. Log. 64(3): 195-209 (1993) - 1992
- [j16]Klaus Ambos-Spies, André Nies
:
Cappable recursively enumerable degrees and Post's program. Arch. Math. Log. 32(1): 51-56 (1992) - [j15]Klaus Ambos-Spies, André Nies, Richard A. Shore:
The Theory of the Recursively Enumerable Weak Truth-Table Degrees Is Undecidability. J. Symb. Log. 57(3): 864-874 (1992) - 1989
- [j14]Klaus Ambos-Spies, Robert I. Soare:
The Recursively Enumerable Degrees have Infinitely Many One-Types. Ann. Pure Appl. Log. 44(1-2): 1-23 (1989) - [j13]Klaus Ambos-Spies:
Honest Polynomial Time Reducibilities and the P = ? NP Problem. J. Comput. Syst. Sci. 39(3): 250-281 (1989) - [j12]Klaus Ambos-Spies, Manuel Lerman:
Lattice Embeddings into the Recursively Enumerable Degrees II. J. Symb. Log. 54(3): 735-760 (1989) - [j11]Klaus Ambos-Spies:
On the Relative Complexity of Hard Problems for Complexity Classes without Complete Problems. Theor. Comput. Sci. 63(1): 43-61 (1989) - 1988
- [j10]Klaus Ambos-Spies, Peter A. Fejer:
Degree Theoretical Splitting Properties of Recursively Enumerable Sets. J. Symb. Log. 53(4): 1110-1137 (1988) - 1987
- [j9]Klaus Ambos-Spies, Hans Fleischhack, Hagen Huwig:
Diagonalizations over Polynomial Time Computable Sets. Theor. Comput. Sci. 51: 177-204 (1987) - 1986
- [j8]Klaus Ambos-Spies:
Inhomogeneities in the Polynomial-Time Degrees: The Degrees of Super Sparse Sets. Inf. Process. Lett. 22(3): 113-117 (1986) - [j7]Klaus Ambos-Spies:
A Note on the Complete Problems for Complexity Classes. Inf. Process. Lett. 23(5): 227-230 (1986) - [j6]Klaus Ambos-Spies, Manuel Lerman:
Lattice Embeddings into the Recursively Enumerable Degrees. J. Symb. Log. 51(2): 257-272 (1986) - [j5]Klaus Ambos-Spies:
An Inhomogeneity in the Structure of Karp Degrees. SIAM J. Comput. 15(4): 958-963 (1986) - 1985
- [j4]Klaus Ambos-Spies:
Cupping and noncapping in the r.e. weak truth table and turing degrees. Arch. Math. Log. 25(1): 109-126 (1985) - [j3]Klaus Ambos-Spies:
Sublattices of the Polynomial Time Degrees. Inf. Control. 65(1): 63-84 (1985) - [j2]Klaus Ambos-Spies:
Anti-Mitotic Recursively Enumerable Sets. Math. Log. Q. 31(29-30): 461-477 (1985) - 1984
- [j1]Klaus Ambos-Spies:
An Extension of the Nondiamond Theorem in Classical and alpha-Recursion Theory. J. Symb. Log. 49(2): 586-607 (1984)
Conference and Workshop Papers
- 2021
- [c37]Klaus Ambos-Spies:
Some Observations on Mitotic Sets. Logic, Computation and Rigorous Methods 2021: 14-28 - 2019
- [c36]Klaus Ambos-Spies, Xizhong Zheng:
On the Differences and Sums of Strongly Computably Enumerable Real Numbers. CiE 2019: 310-322 - 2018
- [c35]Klaus Ambos-Spies:
Multiple Permitting and Array Noncomputability. CiE 2018: 30-39 - 2017
- [c34]Klaus Ambos-Spies:
On the Strongly Bounded Turing Degrees of the Computably Enumerable Sets. Computability and Complexity 2017: 563-598 - 2016
- [c33]Klaus Ambos-Spies:
Learning Finite Variants of Single Languages from Informant. ALT 2016: 163-173 - 2013
- [c32]Klaus Ambos-Spies, Ulrike Brandt, Martin Ziegler:
Real Benefit of Promises and Advice. CiE 2013: 1-11 - 2010
- [c31]Klaus Ambos-Spies, Timur Bakibayev
:
Weak Completeness Notions for Exponential Time. ICALP (1) 2010: 503-514 - [c30]Klaus Ambos-Spies, Timur Bakibayev
:
Nontriviality for Exponential Time w.r.t. Weak Reducibilities. TAMC 2010: 84-93 - 2009
- [c29]Klaus Ambos-Spies, Thorsten Kräling:
Quantitative Aspects of Speed-Up and Gap Phenomena. TAMC 2009: 88-97 - 2008
- [c28]Klaus Ambos-Spies, Serikzhan A. Badaev, Sergey Goncharov:
On a Question of Frank Stephan. TAMC 2008: 423-432 - 2004
- [c27]Klaus Ambos-Spies, Edgar Busse:
Computational Aspects of Disjunctive Sequences. MFCS 2004: 711-722 - 2003
- [c26]Klaus Ambos-Spies, Edgar Busse:
Automatic Forcing and Genericity: On the Diagonalization Strength of Finite Automata. DMTCS 2003: 97-108 - [c25]Klaus Ambos-Spies:
Problems with Cannot Be Reduced to Any Proper Subproblems. MFCS 2003: 162-168 - 2001
- [c24]Klaus Ambos-Spies, Wolfgang Merkle, Jan Reimann, Frank Stephan:
Hausdorff Dimension in Exponential Time. CCC 2001: 210-217 - 2000
- [c23]Klaus Ambos-Spies:
Measure Theoretic Completeness Notions for the Exponential Time Classes. MFCS 2000: 152-161 - [c22]Klaus Ambos-Spies, Wolfgang Merkle, Jan Reimann
, Sebastiaan Terwijn:
Almost Complete Sets. STACS 2000: 419-430 - 1998
- [c21]Klaus Ambos-Spies, Steffen Lempp, Gunther Mainhardt:
Randomness vs. Completeness: On the Diagonalization Strength of Resource-Bounded Random Sets. MFCS 1998: 465-473 - 1997
- [c20]Klaus Ambos-Spies, Levke Bentzien:
Separating NP-Completeness Notions under Strong Hypotheses. CCC 1997: 121-127 - 1996
- [c19]Klaus Ambos-Spies, Elvira Mayordomo, Xizhong Zheng:
A Comparison of Weak Completeness Notions. CCC 1996: 171-178 - [c18]Klaus Ambos-Spies, Elvira Mayordomo, Yongge Wang
, Xizhong Zheng:
Resource-Bounded Balanced Genericity, Stochasticity and Weak Randomness. STACS 1996: 63-74 - 1995
- [c17]Klaus Ambos-Spies:
Resource-Bounded Genericity. SCT 1995: 162-181 - [c16]Klaus Ambos-Spies:
On Optimal Polynomial Time Approximations: P-Levelability vs. Delta-Levelability (Extended Abstract). ICALP 1995: 384-392 - 1994
- [c15]Klaus Ambos-Spies, Sebastiaan Terwijn, Xizhong Zheng:
Resource Bounded Randomness and Weakly Complete Problems. ISAAC 1994: 369-377 - [c14]Klaus Ambos-Spies, Hans-Christian Neis, Sebastiaan Terwijn:
Genericity and Measure for Exponential Time. MFCS 1994: 221-232 - 1992
- [c13]Klaus Ambos-Spies, André Nies:
The Theory of the Polynomial Many-One Degrees of Recursive Sets is Undecidable. STACS 1992: 209-218 - 1990
- [c12]Klaus Ambos-Spies, Steven Homer, Robert I. Soare:
Minimal Pairs and Complete Problems. STACS 1990: 24-36 - 1989
- [c11]Klaus Ambos-Spies, Dongping Yang:
Honest Polynomial-Time Degrees of Elementary Recursive Sets. CSL 1989: 1-15 - 1988
- [c10]Klaus Ambos-Spies, Jürgen Kämper:
On Disjunctive Self-Reducibility. CSL 1988: 1-13 - 1987
- [c9]Klaus Ambos-Spies:
Minimal Pairs for Polynomial Time Reducibilities. Computation Theory and Logic 1987: 1-13 - [c8]Klaus Ambos-Spies:
Honest polynomial reducibilities, recursively enumerable sets, and the P=?NP problem. SCT 1987: 60-68 - [c7]Klaus Ambos-Spies, Hans Fleischhack, Hagen Huwig:
Diagonalizing over Deterministic Polynomial Time. CSL 1987: 1-16 - 1986
- [c6]Klaus Ambos-Spies:
Randomness, Relativizations, and Polynomial Reducibilities. SCT 1986: 23-34 - 1985
- [c5]Klaus Ambos-Spies:
Three Theorems on Polynomial Degrees of NP-Sets. FOCS 1985: 51-55 - [c4]Klaus Ambos-Spies:
On the Relative Complexity of Subproblems of Intractable Problems. STACS 1985: 1-12 - 1984
- [c3]Klaus Ambos-Spies:
P-Generic Sets. ICALP 1984: 58-68 - [c2]Klaus Ambos-Spies:
On the Structure of Polynomial Time Degrees. STACS 1984: 198-208 - 1983
- [c1]Klaus Ambos-Spies:
P-mitotic sets. Logic and Machines 1983: 1-23
Parts in Books or Collections
- 2014
- [p2]Klaus Ambos-Spies:
On the strongly bounded turing degrees of simple sets. Logic, Computation, Hierarchies 2014: 23-78 - 1999
- [p1]Klaus Ambos-Spies:
Polynomial Time Reducibilities and Degrees. Handbook of Computability Theory 1999: 683-705
Editorship
- 2009
- [e2]Klaus Ambos-Spies, Benedikt Löwe, Wolfgang Merkle:
Mathematical Theory and Computational Practice, 5th Conference on Computability in Europe, CiE 2009, Heidelberg, Germany, July 19-24, 2009. Proceedings. Lecture Notes in Computer Science 5635, Springer 2009, ISBN 978-3-642-03072-7 [contents] - 1993
- [e1]Klaus Ambos-Spies, Steven Homer, Uwe Schöning:
Complexity Theory: Current Research, Dagstuhl Workshop, February 2-8, 1992. Cambridge University Press 1993, ISBN 0-521-44220-6 [contents]
Reference Works
- 2014
- [r1]Klaus Ambos-Spies, Peter A. Fejer:
Degrees of Unsolvability. Computational Logic 2014: 443-494
Informal and Other Publications
- 2017
- [i2]Klaus Ambos-Spies, Wolfgang Merkle, Sebastiaan A. Terwijn:
Normalized Information Distance and the Oscillation Hierarchy. CoRR abs/1708.03583 (2017) - [i1]Klaus Ambos-Spies, Vasco Brattka, Rodney G. Downey, Steffen Lempp:
Computability Theory (Dagstuhl Seminar 17081). Dagstuhl Reports 7(2): 89-101 (2017)
Coauthor Index
![](https://dblp.uni-trier.de/img/cog.dark.24x24.png)
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-05-03 20:43 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint