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. [postscript] [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. [postscript] [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. [postscript] [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. [postscript] [pdf]

• A. Kucera and S. A. Terwijn, Lowness for the class of random sets, Journal of Symbolic Logic 64(4) (1999) 1396-1402. [postscript] [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. [postscript] [pdf]

• S. A. Terwijn, On the quantitative structure of Delta⁰₂, 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.

• 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. [postscript] [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. [postscript] [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. [postscript] [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.

• R. Downey and S. A. Terwijn, Computably enumerable reals and uniformly presentable ideals, Mathematical Logic Quarterly 48(1) (2002) 29-40. [postscript] [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. [postscript] [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. [postscript] [pdf]

• S. A. Terwijn, Complexity and randomness, Rendiconti del Seminario Matematico di Torino Vol. 62 No. 1 (2004) 1-38. [postscript] [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. [postscript] [pdf]

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

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

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

• S. A. Terwijn, Probabilistic logic and induction, Journal of Logic and Computation 15(4) (2005) 507-515. [postscript] [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. [postscript] [pdf]

• R. Downey, D. R. Hirschfeldt, A. Nies, and S. A. Terwijn, Calibrating randomness, Bulletin of Symbolic Logic 12(3) (2006) 411-491. [postscript] [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. [postscript] [pdf]

• S. A. Terwijn, On the structure of the Medvedev lattice, Journal of Symbolic Logic 73(2) (2008) 543-558. [postscript] [pdf]
  Erratum to Lemma 2.3 [postscript] [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. [postscript] [pdf]

• B. Bauwens and S. A. Terwijn, Notes on sum-tests and independence tests, Theory of Computing Systems 48 (2011) 247-268. [postscript] [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 (in press). [postscript] [pdf]

• A. Sorbi and S. A. Terwijn, Intuitionistic logic and Muchnik degrees, Algebra Universalis (in press). [postscript] [pdf]

Theses

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

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