Papers in mathematical logic and theoretical computer science

• K. Ambos-Spies, H.-C. Neis, and S. A. Terwijn, Genericity and measure for exponential time, Theoretical Computer Science 168(1) (1996) 3-19.
  Preliminary version in Proceedings of the 19th International Symposium on Mathematical Foundations of Computer Science (MFCS'94), Lecture Notes in Computer Science 841, 221-232, Springer-Verlag, 1994. [pdf]

• K. Ambos-Spies, S. A. Terwijn, and X. Zheng, Resource bounded randomness and weakly complete problems, Theoretical Computer Science 172 (1997) 195-207.
  Preliminary version in Proceedings of the 5th International Symposium on Algorithms and Computation (ISAAC'94), Lecture Notes in Computer Science 834, 369-377, Springer-Verlag, 1994. [pdf]

• J. P. R. Christensen, V. G. Kanovei, S. A. Terwijn, and D. Zambella, On the complexity of finitely additive measures, technical report 1997 Nr. 10, Matematisk Institut, Københavns Universitet, April 24, 1997.

• S. A. Terwijn and L. Torenvliet, Arithmetical measure, Mathematical Logic Quarterly 44(4) (1998) 277-286. [pdf]

• F. C. Stephan and S. A. Terwijn, The complexity of universal text-learners, Information and Computation 154(2) (1999) 149-166.
  Preliminary version in Proceedings of the 11-th International Symposium on Fundamentals of Computation Theory (FCT '97), Lecture Notes in Computer Science 1279, 441-451, Springer-Verlag, 1997. [pdf]

• A. Kucera and S. A. Terwijn, Lowness for the class of random sets, Journal of Symbolic Logic 64(4) (1999) 1396-1402. [pdf]

• S. A. Terwijn, Extensional set learning, Proceedings of the Twelfth Annual Conference on Computational Learning Theory (COLT '99), 243-248, ACM Press, University of California at Santa Cruz, July 6-9, 1999. [pdf]

• S. A. Terwijn, On the quantitative structure of \(\Delta^0_2\), in: U. Berger, H.Osswald, and P. Schuster (eds.), Reuniting the Antipodes. Constructive and Nonstandard Views of the Continuum, Synthèse Library, Kluwer Academic Press, 2000, 271-283. [pdf]

• K. Ambos-Spies, W. Merkle, J. Reimann, and S. A. Terwijn, Almost complete sets, Theoretical Computer Science 306 (2003) 177-194.
  Preliminary version in Proceedings of the 17th International Symposium on Theoretical Aspects of Computer Science (STACS 2000), Lecture Notes in Computer Science 1770, 419-430, Springer-Verlag, 2000. [pdf]

• S. Jain, F. Stephan, and S. A. Terwijn, Counting extensional differences in BC-learning, Information and Computation 188(1) (2004) 127-142.
  Preliminary version by Stephan and Terwijn in Grammatical Inference: Algorithms and Applications. Proceedings of the 5th International Colloquium on Grammatical Inference (ICGI 2000), Lecture Notes in Artificial Intelligence 1891, 256-269, Springer, 2000. [pdf]

• K. Aehlig, J. Johannsen, H. Schwichtenberg, and S. A. Terwijn, Linear ramified higher type recursion and parallel computation, Proof Theory in Computer Science, R. Kahle, P. Schröder-Heister, R. Stärk (eds.), Lecture Notes in Computer Science 2183, 1-21, Springer, 2001. [pdf]

• S. A. Terwijn and D. Zambella, Computational randomness and lowness, Journal of Symbolic Logic 66(3) (2001) 1199-1205. [pdf]

• S. A. Terwijn, On the learnability of hidden Markov models, Grammatical Inference: Algorithms and Applications (ICGI 2002), Lecture Notes in Artificial Intelligence 2484, 261-268, Springer, 2002. [pdf]

• R. Downey and S. A. Terwijn, Computably enumerable reals and uniformly presentable ideals, Mathematical Logic Quarterly 48(1) (2002) 29-40. [pdf]

• S. A. Terwijn, Learning and computing in the limit, Proceedings of the ASL Logic Colloquium 2002, Lecture Notes in Logic 27 (2006) 349-359. [pdf]

• J. M. Hitchcock, J. H. Lutz, and S. A. Terwijn, The arithmetical complexity of randomness and dimension, ACM Transactions on Computational Logic 8(2) (2007) article no. 13.
  Preliminary version in Proc. 17th International Workshop on Computer Science Logic (CSL 2003), Lecture Notes in Computer Science 2803, 241-254, Springer, 2003. [pdf]

• S. A. Terwijn, Complexity and randomness, Rendiconti del Seminario Matematico di Torino Vol. 62 No. 1 (2004) 1-38. [pdf]

• C. Calude, L. Staiger, and S. A. Terwijn, On partial randomness, Annals of Pure and Applied Logic 138 (2006) 20-30. [pdf]

• A. Nies, F. Stephan, and S. A. Terwijn, Randomness, relativization and Turing degrees, Journal of Symbolic Logic 70(2) (2005) 515-535. [pdf]

• S. A. Terwijn, Constructive logic and the Medvedev lattice, Notre Dame Journal of Formal Logic 47(1) (2006) 73-82. [pdf]

• S. A. Terwijn, The Medvedev lattice of computably closed sets, Archive for Mathematical Logic 45(2) (2006) 179-190. [pdf]

• S. A. Terwijn, Kripke models, distributive lattices, and Medvedev degrees, Studia Logica 85(3) (2007) 327--340.
  Preliminary version in Computability in Europe (CiE 2005), Lecture Notes in Computer Science 3526, 486-494, Springer, 2005. [pdf]

• S. A. Terwijn, Probabilistic logic and induction, Journal of Logic and Computation 15(4) (2005) 507-515. [pdf]

• D. R. Hirschfeldt and S. A. Terwijn, Limit computability and constructive measure, in: Computational Prospects of Infinity, Part II, Lecture Notes Series Vol. 15, Institute of Mathematical Sciences, National University of Singapore (2008) 131-141. [pdf]

• R. Downey, D. R. Hirschfeldt, A. Nies, and S. A. Terwijn, Calibrating randomness, Bulletin of Symbolic Logic 12(3) (2006) 411-491. [pdf].

• A. Sorbi and S. A. Terwijn, Intermediate logics and factors of the Medvedev lattice, Annals of Pure and Applied Logic 155 (2008) 69-85. [pdf]

• S. A. Terwijn, On the structure of the Medvedev lattice, Journal of Symbolic Logic 73(2) (2008) 543-558. [pdf]
  Erratum to Lemma 2.3 [pdf]

• S. A. Terwijn, Decidability and undecidability in probability logic, Proceedings of Logical Foundations of Computer Science, Lecture Notes in Computer Science 5407, 441-450, Springer, 2009. [pdf]

• B. Bauwens and S. A. Terwijn, Notes on sum-tests and independence tests, Theory of Computing Systems 48 (2011) 247-268. [pdf]

• S. A. Terwijn, L. Torenvliet, and P. M. B. Vitanyi, Nonapproximability of the normalized information distance, Journal of Computer and System Sciences 77 (2011) 738-742. [pdf]

• S. A. Terwijn, The finite intervals of the Muchnik lattice, Transactions of the American Mathematical Society 364 (2012) 2521-2538. [pdf]

• A. Sorbi and S. A. Terwijn, Intuitionistic logic and Muchnik degrees, Algebra Universalis 67 (2012) 175-188. [pdf]

• R. Kuyper and S. A. Terwijn, Model theory of measure spaces and probability logic, Review of Symbolic Logic 6(3) (2013) 367-393. [pdf]

• A. Sorbi and S. A. Terwijn, Generalizations of the weak law of the excluded middle, Notre Dame Journal of Formal Logic 56(2) (2015) 321-331. [pdf]

• R. Kuyper and S. A. Terwijn, Effective genericity and differentiability, Journal of Logic and Analysis 6:4 (2014), 1-14. [pdf]

• S. A. Terwijn, The mathematical foundations of randomness, book chapter in N.P. Landsman and E. van Wolde (eds.), The Challenge of Chance, Springer, 2016, 49-66. [pdf]

• B. Kjos-Hanssen, F. Stephan, and S. A. Terwijn, Covering the recursive sets, Annals of Pure and Applied Logic 168 (2017) 804-823.
  Preliminary version in Computability in Europe (CiE 2015), Lecture Notes in Computer Science 9136 (2015) 44-53. [pdf]

• K. Ambos-Spies, W. Merkle, and S. A. Terwijn, Normalized information distance and the oscillation hierarchy, Journal of Computer and System Sciences 124 (2022) 65-76. [pdf]

• S. A. Terwijn, Generalizations of the recursion theorem, Journal of Symbolic Logic 83(4) (2018) 1683-1690. [pdf]

• S. A. Terwijn, The noneffectivity of Arslanov's completeness criterion and related theorems, Archive for Mathematical Logic 59(5) (2020) 703-713. [pdf]

• H. P. Barendregt and S. A. Terwijn, Fixed point theorems for precomplete numberings, Annals of Pure and Applied Logic 170 (2019) 1151-1161. [pdf]

• H. P. Barendregt and S. A. Terwijn, Partial combinatory algebra and generalized numberings, Theoretical Computer Science 925 (2022) 37-44. [pdf]

• S. A. Terwijn, Computability in partial combinatory algebras, Bulletin of Symbolic Logic 26(3-4) (2020) 224-240. [pdf]

• P. Shafer and S. A. Terwijn, Ordinal analysis of partial combinatory algebras, Journal of Symbolic Logic 86(3) (2021) 1154-1188. [pdf]

• A. Golov and S. A. Terwijn, Fixpoints and relative precompleteness, Computability 11(2) (2022) 135-146. [pdf]

• A. Golov and S. A. Terwijn, Embeddings between partial combinatory algebras, Notre Dame Journal of Formal Logic 64(1) (2023) 129-158. [pdf]

Theses

• S. A. Terwijn, Computability and measure, PhD thesis, University of Amsterdam, 1998. [pdf]

• S. A. Terwijn, Constructive logic and computational lattices, habilitation thesis, Technical University of Vienna, 2007.