Frank Stephan's Publications

Due to copy-right regulations, the readers should note, that the author does not have the right to update preprints in order to make them identical with the contents of a journal-publication. If you want to have the exact text of a journal publication instead of the one of the corresponding older technical report, you are kindly requested to look into your libary.

Technical Report versions are marked with the report number in brackets.

Many publications, in particular conference-proceedings, have appeared in the series Lecture Notes in Computer Science from Springer.

Publications appeared in the following journals:
Annals of Mathematics and Artificial Intelligence from Kluwer,
Annals of Pure and Applied Logic from Elsevier,
Archive for Mathematical Logic from Springer,
Fundamentae Informatica from the Polish Mathematical Society and the European Association for Theoretical Computer Science,
IEEE Transactions on Computers from the IEEE Computer Society,
Information and Computation from Academic Press,
International Journal of Foundations of Computer Science from World Scientific,
Journal of Automata, Languages and Combinatorics from Otto-von-Guericke-Universitaet Magdeburg,
Journal of Computer and System Sciences from Elsevier,
Journal of the London Mathematical Society,
Mathematical Logic Quarterly from Wiley VCH,
RAIRO Informatique Theorique et Applications from EDP Sciences,
SIAM Journal on Computing from the Society for Industrial and Applied Mathematics,
The Journal of Symbolic Logic from the Association of Symbolic Logic,
Theoretical Computer Science from Elsevier,
Theory of Computing Systems from Springer.


Articles in scientific journals
  1. Martin Kummer and Frank Stephan. Weakly semirecursive sets and r.e. orderings. Annals of Pure and Applied Logic 60:133-150, 1993.
  2. Carl Jockusch and Frank Stephan. A cohesive set which is not high. Mathematical Logic Quarterly, 39:515-530, 1993. A corrective note (keeping the main results intact) appeared in the same journal, 43:569, 1997.
  3. Heinz Braun and Frank Stephan. On optimizing diameter and average distance of directed interconnected networks. IEEE Transactions on Computers, 42:353-358, 1993.
  4. Lance Fortnow, William Gasarch, Sanjay Jain, Efim Kinber, Martin Kummer, Stuart A. Kurtz, Mark Pleszkoch, Theodore A. Slaman, Robert Solovay and Frank Stephan. Extremes in the degrees of inferability. Annals of Pure and Applied Logic, 66:231-276, 1994.
  5. Martin Kummer and Frank Stephan. Effective search problems. Mathematical Logic Quarterly, 40:224-236, 1994.
  6. Richard Beigel, Martin Kummer and Frank Stephan. Quantifying the amount of verboseness. Information and Computation 118:71-90, 1995. Proceedings of the Second International Symposium on Logical Foundations of Computer Science - Logic at Tver 1992, Springer LNCS 620, 21-32, 1992.
  7. Martin Kummer and Frank Stephan. Recursion theoretic properties of frequency computation and bounded queries. Information and Computation, 120:59-77, 1995. Proceedings of the Third Kurt-Goedel-Colloquium, Springer LNCS 713, 243-254, 1993.
  8. Richard Beigel, Martin Kummer and Frank Stephan. Approximable sets. Information and Computation, 120:304-314, 1995. Proceedings Structure in Complexity Theory, Ninth Annual Conference, IEEE Press, 12-23, 1994.
  9. Efim Kinber and Frank Stephan. Language learning from texts: mind changes, limited memory and monotonicity. Information and Computation, 123:224-241, 1995. Proceedings of the Eighth Annual ACM Conference on Computational Learning Theory - COLT 1995, ACM-Press, 182-189, 1995.
  10. Martin Kummer and Frank Stephan. On the structure of degrees of inferability. Journal of Computer and System Sciences (Special Issue COLT 1993), 52:214-238, 1996. Proceedings of the Sixth Annual ACM Conference on Computational Learning Theory - COLT 1993, 117-126, ACM-Press, New York, 1993.
  11. Martin Kummer and Frank Stephan. Inclusion problems in parallel learning and games. Journal of Computer and System Sciences (Special Issue COLT 1994), 52:403-420, 1996. Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory - COLT 1994, 287-298, ACM-Press, New York, 1994.
  12. Frank Stephan. Noisy inference and oracles. (TR 19) Theoretical Computer Science 185:129-157, 1997. Proceedings of the 6th International Workshop on Algorithmic Learning Theory - ALT 1995, Springer LNCS 997, 185-200, 1995.
  13. Lance Fortnow, Rusins Freivalds, William Gasarch, Martin Kummer, Stuart A. Kurtz, Carl Smith and Frank Stephan. On the relative sizes of learnable sets. Theoretical Computer Science, 197:139-156, 1998. An extended abstract appeared under the title ``Measure, category and learning theory'' in Proceedings of the 22nd International Colloquium on Automata, Languages and Programming - ICALP 1995, Springer LNCS 944, 558-569, 1995.
  14. Bernd Borchert, Desh Ranjan and Frank Stephan. On the computational complexity of some classical equivalence relations on Boolean functions. (TR 18) Theory of Computing Systems, 31:679-693, 1998.
  15. Frank Stephan. Learning via queries and oracles. (TR 20) Annals of Pure and Applied Logic, 94:273-296, 1998. Proceedings of the Eighth Annual ACM Conference on Computational Learning Theory - COLT 1995, ACM-Press, New York, 162-169, 1995.
  16. William Gasarch, Mark Pleszkoch, Frank Stephan and Mahendran Velauthapillai. Classification using information. Annals of Mathematics and Artificial Intelligence. Selected papers from ALT 1994 and AII 1994, 23:147-168, 1998.
  17. Henning Fernau and Frank Stephan. Characterizations of recursively enumerable languages by programmed grammars with unconditional transfer. Journal of Automata, Languages and Combinatorics, 4:117-142, 1999. Konferenzversion: How powerful is unconditional transfer? - When UT meets AC. - Proceedings of the Conference Developments in Language Theory - DLT 1997 (S. Bozapalidis, ed.), 249-260, Aristotle University of Thessaloniki, Thessaloniki, 1997.
  18. Bernd Borchert, Dietrich Kuske and Frank Stephan. On existentially first-order definable languages and their relation to NP. RAIRO Informatique Theorique et Applications, 33:259-270,1999. Proceedings of the 25th International Colloquium on Automata, Languages and Programming - ICALP 1998.
  19. Frank Stephan and Sebastiaan A. Terwijn. The complexity of universal text-learners. (TR 39) Information and Computation, 154:149-166, 1999. Proceedings of the Eleventh International Symposium on Fundamentals of Computation Theory - FCT 1997, Springer LNCS 1279, 441-451, 1997.
  20. Richard Beigel, William Gasarch, Martin Kummer, Georgia Martin, Timothy McNicholl and Frank Stephan. The complexity of Odd(A,n). Journal of Symbolic Logic, 65:1-18, 2000. Conference-Version: On the query complexity of sets. Proceedings of the Twentyfirst International Symposium on Mathematical Foundations of Computer Science - MFCS 1996, Springer LNCS 1113, 206-217, 1996.
  21. John Case, Sanjay Jain, Matthias Ott, Arun Sharma and Frank Stephan. Robust learning aided by context. Journal of Computer and System Sciences (Special Issue COLT 1998), 60:234-257, 2000. Proceedings of the Eleventh Annual ACM Conference on Computational Learning Theory - COLT 1998, ACM-Press, 44-55, 1998.
  22. John Case, Sanjay Jain and Frank Stephan. Vacillatory and BC learning on noisy data. (TR96-002) Theoretical Computer Science, 241:115-141, 2000. Proceedings of the Seventh Annual Workshop on Algorithmic Learning Theory - ALT 1996, Springer LNCS 1160, 285-298, 1996. Siehe auch: Electronic Archive for Computational Learning Theory eC-TR-96-002, Dortmund, 1996.
  23. Bernd Borchert and Frank Stephan. Looking for an analogue of Rice's theorem in complexity theory. (TR 23) Mathematical Logic Quarterly, 46:489-504, 2000. Proceedings of the Fifth Kurt-Goedel-Colloquium - KGS 1997, Springer LNCS 1289, 114-127, 1997.
  24. Matthias Ott and Frank Stephan. Structural measures for games and process control in the branch learning model. Theoretical Computer Science - Series A, 244:135-165, 2000. Proceedings of the Third European Conference on Computational Learning Theory - EuroCOLT 1997, Springer LNCS 1208, 94-108, 1997.
  25. Susanne Kaufmann and Frank Stephan. Robust learning with infinite additional information. (TR 26) Theoretical Computer Science - Series A, 259:427-454, 2001. Proceedings of the Third European Conference on Computational Learning Theory - EuroCOLT 1997, Springer LNCS 1208, 316-330, 1997.
  26. Frank Stephan. On the structures inside truth-table degrees. (TR 29) The Journal of Symbolic Logic, 66:731-770, 2001.
  27. John Case, Sanjay Jain, Susanne Kaufmann, Arun Sharma and Frank Stephan. Predictive learning models for concept drift. (TR 40) Theoretical Computer Science - Series A, 268:323-349, 2001. Proceedings of the Ninth Annual Workshop on Algorithmic Learning Theory - ALT 1998, Springer LNCS 1501, 276-290, 1998.
  28. Frank Stephan and Yuri Ventsov. Learning Algebraic Structures from Text using Semantical Knowledge. (TR 34) Theoretical Computer Science - Series A, 268:221-273, 2001. Proceedings of the Ninth Annual Workshop on Algorithmic Learning Theory - ALT 1998, Springer LNCS 1501, 321-335, 1998.
  29. Frank Stephan. On one-sided versus two-sided classification. (TR 25) Archive for Mathematical Logic, 40:489-513, 2001.
  30. John Case, Matthias Ott, Arun Sharma and Frank Stephan. Learning to win process-control games watching game-masters. Information and Computation, 174:1-19, 2002. Proceedings of the Ninth Annual Workshop on Algorithmic Learning Theory - ALT 1998, Springer LNCS 1501, 31-45, 1998.
  31. Matthias Ott and Frank Stephan. Avoiding coding tricks by hyperrobust learning. Theoretical Computer Science - Series A, 284:161-180, 2002. Proceedings of the Fourth European Conference on Computational Learning Theory - EuroCOLT 1999. Springer LNCS 1572, 183-197, 1999.
  32. Frank Stephan and Thomas Zeugmann. Learning classes of approximations to non-recursive functions. (TRCS 166) Theoretical Computer Science - Series A, 288:309-341, 2002. Conference version (with title On the uniform learnability of approximations to non-recursive functions) in Proceedings of the Ninth Annual Workshop on Algorithmic Learning Theory - ALT 1999, Springer LNCS 1720, 276-290, 1999.
  33. Kejia Joyce Ho and Frank Stephan. Classes bounded by incomplete sets. (TR 45) Annals of Pure and Applied Logic, 116:273-295, 2002.
  34. Wolfgang Merkle and Frank Stephan. Refuting Learning Revisited. (TR 52) Theoretical Computer Science - Series A, 298:145-177, 2003. Algorithmic Learning Theory, Twelfth International Conference, ALT 2001, Washington, DC, USA, November 25-28, 2001, Proceedings, Springer LNAI 2225:299-314, 2001.
  35. Eric Martin, Arun Sharma and Frank Stephan. Learning power and language expressiveness. (TR 49) Theoretical Computer Science - Series A, 298:365-383, 2003.
  36. Wolfram Menzel and Frank Stephan. Topological aspects of numberings. (IRA 1999/15) Mathematical Logic Quarterly, 49:129-149, 2003.
  37. Sanjay Jain and Frank Stephan. Learning by switching type of information. (TR 56) Information and Computation, 185:90-105, 2003. Algorithmic Learning Theory, Twelfth International Conference, ALT 2001, Washington, DC, USA, November 25-28, 2001, Proceedings, Springer LNAI 2225:205-218, 2001.
  38. Wolfgang Merkle and Frank Stephan. Trees and learning. (TR 57) Journal of Computer and System Sciences, 68:134-156, 2004. Proceedings of the Ninth Annual Conference on Computational Learning Theory - COLT 1996, ACM-Press, 270-279, 1996.
  39. Sanjay Jain and Frank Stephan. Learning how to separate. (TR 51) Theoretical Coputer Science (Special Issue ALT 2001), 313:209-228, 2004. Algorithmic Learning Theory, Twelfth International Conference, ALT 2001, Washington, DC, USA, November 25-28, 2001, Proceedings, Springer LNAI 2225:219-234, 2001.
  40. Sanjay Jain, Frank Stephan and Sebastiaan A. Terwijn. Counting extensional differences in BC-learning. (TR 54) Information and Computation, 188:127-142, 2004. Conference version by Frank Stephan and Sebastiaan A. Terwijn only: Proceedings of the Fifth International Colloquium on Grammatical Inference - ICGI 2000, Springer LNAI 1891:256-269, 2000.
  41. Arun Sharma, Frank Stephan and Yuri Ventsov. Generalized notions of mind change complexity. Information and Computation 189:235-262, 2004. Proceedings of the Conference on Computational Learning Theory - COLT 1997, Nashville, 96-108, 1997.
  42. John Case, Efim Kinber, Arun Sharma and Frank Stephan. On the classification of recursive languages. (CSE 9603) Information and Computation 192:15-40, 2004. Proceedings of the Symposium on Theoretical Aspects of Computer Science - STACS 1997, Springer LNCS 1200, 225-236, 1997.
  43. John Case, Sanjay Jain, Frank Stephan and Rolf Wiehagen. Robust learning - rich and poor. (SIIM-TR-A-01-06) Journal of Computer and System Sciences 69:123-165, 2004. Proceedings of the Fourteenth Annual Conference on Computational Learning Theory and the Fifth European Conference on Computational Learning Theory - COLT 2001 and EuroCOLT 2001, Springer LNAI 2111:143-159, 2001.
  44. Sanjay Jain, Wolfram Menzel and Frank Stephan. Classes with easily learnable subclasses. (TR 59) Information and Computation, 190:81-99, 2004. Algorithmic Learning Theory. 13th International Conference, ALT 2002, Luebeck, Germany, November 2002, Proceedings, Springer LNCS 2533:218-232, 2002.
  45. Bernd Borchert, Klaus-Joern Lange, Frank Stephan, Pascal Tesson and Denis Therien. The dot-depth and the polynomial hierarchy correspond on the delta levels. (WSI-2004-3) International Journal of Foundations of Computer Science 16:625-644, 2005. Developments in Language Theory: 8th International Conference, DLT 2004. Auckland, New Zealand, December 13-17. Proceedings; Springer LNCS 3340:89-1001, 2004.
  46. Andre Nies, Frank Stephan and Sebastian A. Terwijn. Randomness, relativization and Turing degrees. (234) The Journal of Symbolic Logic 70:515-535, 2005.
  47. Wolfgang Merkle, Joseph Miller, Andre Nies, Jan Reimann and Frank Stephan. Kolmogorov-Loveland Randomness and Stochasticity. Annals of Pure and Applied Logic, 138:183-210, 2006. STACS 2005 - Twentysecond Annual Symposium on Theoretical Aspects of Computer Science, Stuttgart, Germany, February 24-26, 2005, Proceedings. Springer LNCS 3404:422-433, 2005.
  48. Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpre, Andrej Muchnik, Frank Stephan and Leen Torenvliet. Enumerations of the Kolmogorov function. (TR04-015 updated) The Journal of Symbolic Logic 71:501-528, 2006.
  49. John Case, Sanjay Jain, Eric Martin, Arun Sharma and Frank Stephan. Identifying clusters from positive data. (TR04-058) SIAM Journal on Computing 36:28-55, 2006. Grammatical Inference: Algorithms and Applications - 7th International Colloquium, ICGI 2004, Athens, Greece, October 11-13, 2004, Proceedings; Springer LNCS 3264, 103-114, 2004.
  50. Bjorn Kjos-Hanssen, Andre Nies and Frank Stephan. Lowness for the class of Schnorr random reals. SIAM Journal on Computing 35:647-657, 2006.
  51. Lorenzo Carlucci, Sanjay Jain, Efim Kinber and Frank Stephan. Variations of U-Shaped Learning. (TRA8/05) Information and Computation, 204:1264-1294, 2006. Computational Learning Theory: Eightteenth Annual Conference on Learning Theory, COLT 2005, Bertinoro, Italy, June 27-30, 2005. Proceedings. Springer LNCS 3559:382-397, 2005.
  52. Richard Beigel, Lance Fortnow and Frank Stephan. Infinitely-often autoreducible sets. (TR 62) SIAM Journal on Computing, 36:595-608, 2006. Algorithms and Computation, 14th International Symposium, ISAAC 2003, Kyoto, Japan, December 15-17, 2003, Proceedings; Springer LNCS 2906:98-107, 2003.
  53. Santiago Figueira, Frank Stephan and Guohua Wu. Randomness and universal machines. (TR32/05) Journal of Complexity, 22:738-751, 2006. Second International Conference on Computability and Complexity in Analysis, CCA 2005. Fernuniversitaet in Hagen, Informatik Bereichte 326:103-116, 2005.
  54. Eric Martin, Arun Sharma and Frank Stephan. Unifying logic, topology and learning in Parametric Logic. Theoretical Computer Science, 350:103-149, 2006. Appeared as ``Learning, logic and topology in a common framework'' at Algorithmic Learning Theory. 13th International Conference, ALT 2002, Luebeck, Germany, November 2002, Proceedings, Springer LNCS 2533:248-262, 2002.
  55. John Case, Sanjay Jain, Ruediger Reischuk, Frank Stephan and Thomas Zeugmann. Learning a subclass of regular patterns in polynomial time. (TR04-038) Theoretical Computer Science, 364:115-131, 2006. Algorithmic Learning Theory, Fourteenth International Conference, ALT 2003, Sapporo, Japan, October 2003, Proceedings; Springer LNAI 2842:234-246, 2003.
  56. Eric Martin, Arun Sharma and Frank Stephan. On ordinal VC-dimension and some notions of complexity. Theoretical Computer Science, 364:62-76, 2006. Algorithmic Learning Theory, Fourteenth International Conference, ALT 2003, Sapporo, Japan, October 2003, Proceedings; Springer LNAI 2842:54-68, 2003.
  57. Valentina S.Harizanov and Frank Stephan. On the learnability of vector spaces. (TR 55) Journal of Computer and System Sciences, 73:109-122, 2007. Algorithmic Learning Theory. 13th International Conference, ALT 2002, Luebeck, Germany, November 2002, Proceedings, Springer LNCS 2533:233-247, 2002.
  58. Eric Martin, Arun Sharma and Frank Stephan. On the Data Consumption Benefits of Accepting Increased Uncertainty. Theoretical Computer Science, 382:170-182, 2007. Algorithmic Learning Theory: 15th International Conference, ALT 2004, Padova, Italy, October 2-5, 2004. Proceedings; Springer LNCS 3244:83-98, 2004.
  59. Lorenzo Carlucci, John Case, Sanjay Jain and Frank Stephan. Results on memory-limited U-shaped learning. (updated version of TR51/05) Information and Computation, 205:1551-1573, 2007. Computational Learning Theory: Nineteenth Annual Conference, COLT 2006, Carnegie Mellon University, Pittsburgh, Pennsylvania, June 22-25, 2006. Proceedings. Springer LNAI 4005:259-273, 2006.
  60. Sanjay Jain, Jochen Nessel and Frank Stephan. Invertible Classes. (TR22/05) Theoretical Computer Science, 384:49-65, 2007. Theory and Applications of Models of Computation: Third International Conference, TAMC 2006, Beijing, China, May 15-20, 2006. Proceedings. Springer LNCS, 3959:707-720, 2006.
  61. Bakhadyr Khoussainov, Pavel Semukhin and Frank Stephan. Applications of Kolmogorov Complexity to Computable Model Theory. (TRA9/06) The Journal of Symbolic Logic, 72:1041-1054, 2007.
  62. Bahareh Afshari, George Barmpalias, S. Barry Cooper and Frank Stephan. Post's Programme for the Ershov Hierarchy. (TR10/06) Journal of Logic and Computation, 17:1025-1040, 2007.
  63. Denis R. Hirschfeldt, Andre Nies and Frank Stephan. Using random sets as oracles. (TR 64) Journal of the London Mathematical Society, 75:610-622, 2007.
  64. Bakhadyr Khoussainov, Andre Nies, Sasha Rubin and Frank Stephan. Automatic structures: richness and limitations. Logical Methods in Computer Science, volume 3, number 2, 2007. 19th IEEE Symposium on Logic in Computer Science, LICS 2004, 14-17 July 2004, Turku, Finland, Proceedings; IEEE Computer Society, pages 44-53, 2004.
  65. Sanjay Jain, Frank Stephan and Nan Ye. Prescribed learning of indexed families. (TRB9/07) Fundamenta Informaticae, 83:159-175, 2008.
  66. Ganesh Baliga, John Case, Wolfgang Merkle, Frank Stephan and Rolf Wiehagen. When unlearning helps. (TRA5/06) Information and Computation, 206:694-709, 2008. Preliminary version appeared as ``Unlearning helps'' by G. Baliga, J. Case, W. Merkle and F. Stephan in Proceedings of the 27th International Colloquium on Automata, Languages and Programming - ICALP 2000, Springer LNCS 1853, 844-855, 2000.
  67. Lorenzo Carlucci, John Case, Sanjay Jain and Frank Stephan. Non U-shaped vacillatory and team learning. (TR11/04) Journal of Computer and System Sciences, 74:409-430, 2008. Algorithmic Learning Theory: Sixteenth International Conference, ALT 2005, Singapore, October 2005. Proceedings. Springer LNAI 3734:241-255, 2005.
  68. Sanjay Jain and Frank Stephan. Learning in Friedberg numberings. (TR11/07) Information and Computation, 206:776-790, 2008. Algorithmic Learning Theory, Eighteenth International Conference, ALT 2007, Sendai, Japan, October 2-4, 2007. Proceedings. Springer LNAI 4754:79-93, 2007.
  69. Sanjay Jain and Frank Stephan. Mitotic Classes in Inductive Inference. (TRB8/07) SIAM Journal on Computing, 38:1283-1299, 2008. Computational Learning Theory, 20th Annual Conference on Computational Learning Theory, COLT 2007, San Diego, CA, USA, June 13-15, 2007, Proceedings. Springer LNCS 4539:218-232, 2007.
  70. Santiago Figueira, Andre Nies and Frank Stephan. Lowness properties and approximations of the jump. (TR11/05) Annals of Pure and Applied Logic, 152:51-66, 2008. Proceedings of the Twelfth Workshop of Logic, Language, Information and Computation (WoLLIC 2005). Electronic Lecture Notes in Theoretical Computer Science 143:45-57, 2006.
  71. Bakhadyr Khoussainov, Frank Stephan and Yue Yang. Computable categoricity and the Ershov hierarchy. (TRD8/07) Annals of Pure and Applied Logic, 156:86-95, 2008.
  72. George Barmpalias, Andy Lewis and Frank Stephan. Pi-0-1 classes, LR degrees and Turing degrees. (TRB4/07) Annals of Pure and Applied Logic 152:21-38, 2008.
  73. Frank Stephan and Jason Teutsch. Immunity and hyperimmunity for generalized random strings. (TRA5/07) Notre Dame Journal of Formal Logic, 49:107-125, 2008.
  74. Sanjay Jain, Frank Stephan and Nan Ye. Prescribed learning of r.e. classes. (TR10/07) Theoretical Computer Science 410:1796-1806, 2009. Algorithmic Learning Theory, Eighteenth International Conference, ALT 2007, Sendai, Japan, October 2-4, 2007. Proceedings. Springer LNAI 4754:64-78, 2007.
  75. Laurent Bienvenu, David Doty and Frank Stephan. Constructive dimension and Turing degrees. (TRC1/07) Theory of Computing Systems, 46:740-755, 2009. Revised version of a paper at Computation and Logic in the Real World, Third Conference on Computability in Europe, CiE 2007, Siena, Italy, Proceedings. Springer LNCS 4497:63-72, 2007.
  76. Sanjay Jain, Eric Martin and Frank Stephan. Input-dependence in function-learning. Theory of Computing Systems, 46:849-864, 2009. Computation and Logic in the Real World, Third Conference on Computability in Europe, CiE 2007, Siena, Italy, Proceedings. Springer LNCS 4497:378-388, 2007.
  77. Johanna Franklin and Frank Stephan. Schnorr trivial sets and truth-table reducibility. (TRA3/08) The Journal of Symbolic Logic, 75:501-521, 2010.
  78. Leonor Becerra-Bonache, John Case, Sanjay Jain and Frank Stephan. Iterative Learning of Simple External Contextual Languages. Theoretical Computer Science, 411:2741-2756, 2010. Algorithmic Learning Theory, Nineteenth International Conference, ALT 2008, Budapest, Hungary, October 2008. Proceedings. Springer LNAI 5254:359-373, 2008.
  79. Sanjay Jain and Frank Stephan. Numberings optimal for learning. (TRA8/08) Journal of Computer and System Sciences, 76:233-250, 2010. Algorithmic Learning Theory, Nineteenth International Conference, ALT 2008, Budapest, Hungary, October 2008. Proceedings. Springer LNAI 5254:434-448, 2008.
  80. Bjorn Kjos-Hanssen, Andre Nies, Frank Stephan and Liang Yu. Higher Kurtz randomness. (330) Annals of Pure and Applied Logic, 161:1280-1290, 2010.
  81. Carl Mummert and Frank Stephan. Topological aspects of poset spaces. (TRC6/06) The Michigan Mathematical Journal, 59:3-24, 2010.
  82. Sanjay Jain, Yuh Shin Ong and Frank Stephan. Regular patterns, regular languages and context-free languages. Information Processing Letters 110:1114-1119, 2010.
  83. Sanjay Jain, Frank Stephan and Jason Teutsch. Index sets and universal numberings. (TRA3/09) Journal of Computer and System Sciences 77:760-773, 2011.
  84. Cristian S. Calude, Nicholas J. Hay and Frank Stephan. Representation of left-computable epsilon-random reals. (365) Journal of Computer and System Sciences 77:812-819, 2011.
  85. Cristian S.Calude, Andre Nies, Ludwig Staiger and Frank Stephan. Universal recursively enumerable sets of strings. (326) Theoretical Computer Science 4123:2253-2261, 2011. Developments in Language Theory, Twelfth International Conference, DLT 2008, Kyoto, Japan. Proceedings. Springer LNCS 5257:170-182, 2008.
  86. Johanna Franklin, Frank Stephan and Liang Yu. Relativizations of randomness and genericity notions. (TRA2/09) Bulletin of the London Mathematical Society 43:721-733, 2011.
  87. Frank Stephan and Jason Teutsch. An incomplete set of shortest descriptions. The Journal of Symbolic Logic, 77:291-307, 2012.
Conference articles which are not yet or which will not be published in journals
  1. Martin Kummer and Frank Stephan. The power of frequency computation. Proceedings of the Tenth International Conference on Fundamentals of Computation Theory - FCT 1995, Springer LNCS 969, 323-332, 1995.
  2. Susanne Kaufmann and Frank Stephan. Resource bounded next value and explanatory identification: learning automata, patterns and polynomials on-line. Proceedings of the Conference on Computational Learning Theory - COLT 1997, Nashville, 263-274, 1997.
  3. Matthias Ott and Frank Stephan. The complexity of learning branches and strategies from queries. Proceedings of the Eighth Annual International Symposium on Algorithms and Computation - ISAAC 1997, Springer LNCS 1350, 283-292, 1997.
  4. William Gasarch and Frank Stephan. A techniques-oriented survey of bounded queries. (TR 32) Models and Computability (invited papers from Logic Colloquium 1997) London Mathematical Society Lecture Note Series 259, 117-156, 1999. Forschungsberichte Mathematische Logik 32 / 1998, Mathematisches Institut, Universitaet Heidelberg, Heidelberg, 1998.
  5. Klaus Ambos-Spies, Levke Bentzien, Peter Fejer, Wolfgang Merkle and Frank Stephan. Collapsing polynomial-time degrees. (TR 41) Logic Colloquium 1998 - Proceedings of the Annual European Summer Meeting of the Association for Symbolic Logic, held in Prague, Czech Republic, ASL Lecture Notes in Logic 13:1-24, 2000.
  6. Andrew Mitchell, Tobias Scheffer, Arun Sharma and Frank Stephan. The VC-Dimension of subclasses of pattern languages. Proceedings of the Ninth Annual Workshop on Algorithmic Learning Theory - ALT 1999, Springer LNCS 1720, 93-105, 1999.
  7. Frank Stephan and Thomas Zeugmann. Average-case complexity of learning polynomials. Proceedings of the Thirteenth Annual Conference on Computational Learning Theory - COLT 2000, Morgan Kaufmann, 59-68, 2000.
  8. Klaus Ambos-Spies, Wolfgang Merkle, Jan Reimann and Frank Stephan. Hausdorff Dimension in Exponential Time. Proceedings Sixteenth Annual IEEE Conference on Computational Complexity (formerly Structure in Complexity Theory), IEEE Computer Society, 210-217, 2001.
  9. Eric Martin, Arun Sharma and Frank Stephan. A general theory of deduction, induction and learning. Discovery Science, Fourth International Conference, DS 2001, Washington, DC, USA, November 2001, Proceedings, Springer LNAI 2226:228-242, 2001.
  10. Jan Reimann and Frank Stephan. Effective Hausdorff dimension. Logic Colloquium 2001, Proceedings of the Annual European Summer Meeting of the Association for Symbolic Logic, held in Vienna, Austria, August 1-6, 2001, ASL Lecture Notes in Logic 20:369-385, 2005.
  11. Rod G. Downey, Denis R. Hirschfeldt, Andre Nies and Frank Stephan. Trivial Reals (ENTCS 66 1 4) Fifth Workshop on Computability and Complexity in Analysis, Electronic Notes in Theoretical Computer Science, Elsevier, Volume 66, Issue 1, Article 5, 2002. Final version in: Proceedings of the 7th and 8th Asian Logic Conferences (7th Conference: Hsi-Tou, Taiwan 6 - 10 June 1999, 8th Conference: Chongqing, China 29 August - 2 September 2002), World Scientific, 103-131, 2003.
  12. Eric Martin, Phuong Nguyen, Arun Sharma and Frank Stephan. Learning in logic with RichProlog. Porceedings of the International Conference on Logic Programming - ICLP 2002, Springer LNCS 2401:239-254, 2002.
  13. Sanjay Jain and Frank Stephan. A tour of robust learning. (TR 53) Computability and Models. Perspectives East and West. Edited by S. Barry Cooper and Sergei S. Goncharov. Kluwer Academic / Plenum Publishers, University Series in Mathematics, pages 215-247, 2003.
  14. Marcus Schaefer and Frank Stephan. Strong reductions and immunity for exponential time. (TR02-004 updated) Twentieth International Symposium on Theoretical Aspects of Computer Science, STACS 2003, Berlin, Germany, February/March 2003, Proceedings; Springer LNCS 2607:559-570, 2003. Long version (that is, this file on the internet) is an update of the DePaul University Technical Report TR02-004, 2002.
  15. Bakhadyr Khoussainov, Sasha Rubin and Frank Stephan. On automatic partial orders. (208) Proceedings of Eighteenth IEEE Symposium on Logic in Computer Science, LICS, 168-177, 2003. Research Report 208, Centre for Discrete Mathematics and Theoretical Computer Science, The University of Auckland, November 2003.
  16. Bakhadyr Khoussainov, Sasha Rubin and Frank Stephan. Definability and regularity in automatic structures. (209) STACS 2004, 21st Annual Symposium on Theoretical Aspects of Computer Science, Montpellier, France, March 25-27, 2004, Proceedings; Springer LNCS 2996:440-451, 2004.
  17. Frank Stephan and Guohua Wu. Presentations of K-Trivial Reals and Kolmogorov Complexity. (LNCS 3526) New Computational Paradigms: First Conference on Computability in Europe, CiE 2005, Amsterdam, The Netherlands, June 8-12, 2005. Proceedings. Springer LNCS 3526:461-469, 2005.
  18. Sanjay Jain, Eric Martin and Frank Stephan. Absolute Versus Probabilistic Classification in a Logical Setting. (TRC3/06) Algorithmic Learning Theory: Sixteenth International Conference, ALT 2005, Singapore, October 2005. Proceedings. Springer LNAI 3734:327-342, 2005.
  19. Manindra Agrawal, Frank Stephan, P.S.Thiagarajan and Shaofa Yang. Behavioural Approximations for Restricted Linear Differential Hybrid Automata. Hybrid Systems: Computation and Control: Ninth International Workshop, HSCC 2006, Santa Barbara, CA, USA, March 29-31, 2006. Proceedings. Springer LNCS 3927:4-18, 2006.
  20. Bjorn Kjos-Hanssen, Wolfgang Merkle and Frank Stephan. Kolmogorov Complexity and the Recursion Theorem. (0901.3933) STACS 2006: Twenty-Third Annual Symposium on Theoretical Aspects of Computer Science, Marseille, France, February 23-25, 2006. Proceedings. Springer LNCS 3884:149-161, 2006.
  21. Sanjay Jain and Frank Stephan. Some recent results in U-shaped learning. (TR41/05) Some Recent Results in U-Shaped Learning. Theory and Applications of Models of Computation: Third International Conference, TAMC 2006, Beijing, China, May 15-20, 2006. Proceedings. Springer LNCS, 3959:421-431, 2006.
  22. Frank Stephan and Liang Yu. Lowness for weakly 1-generic and Kurtz-random. (TR62/05) Theory and Applications of Models of Computation: Third International Conference, TAMC 2006, Beijing, China, May 15-20, 2006. Proceedings. Springer LNCS, 3959:756-764, 2006.
  23. Frank Stephan. Martin-Loef Random and PA-complete Sets. (TR 58) Proceedings of ASL Logic Colloquium 2002. ASL Lecture Notes in Logic, 27:342-348, 2006.
  24. Jan Reimann and Frank Stephan. Hierarchies of randomness tests. (TRB2/06) Mathematical Logic in Asia. Proceedings of the Ninth Asian Logic Conference, Novosibirsk, Russia 16 - 19 August 2005, pages 215-232, 2006.
  25. Wolfgang Merkle and Frank Stephan. On C-Degrees, H-Degrees and T-Degrees. Twenty-Second Annual IEEE Conference on Computational Complexity (CCC 2007), San Diego, USA, 12 - 16 June 2007, pages 60-69, 2007.
  26. Frank Stephan. Hausdorff-dimension and weak truth-table reducibility. (TR52/05) Logic Colloquium 2004, ASL Lecture Notes in Logic 29:157-167, 2008.
  27. Alexander Raichev and Frank Stephan. A minimal rK-degree. (TR31/05) Computational Prospects of Infinity, Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore, 15:261-269, 2008.
  28. Sanjay Jain and Frank Stephan. Consistent partial identification. (COLT 2009) Computational Learning Theory, Proceedings, 10 pages, 2009.
  29. Sanjay Jain, Qinglong Luo, Pavel Semukhin and Frank Stephan. Uncountable automatic classes and learning. (TRB1/09) Algorithmic Learning Theory, Twentieth International Conference, ALT 2009, Porto, Portugal, October 3-5, 2009. Proceedings. Springer LNAI 5809:293-307, 2009. Technical Report TRB1/09, School of Computing, National University of Singapore, 2009.
  30. Sanjay Jain, Frank Stephan and Nan Ye. Learning from Streams. Algorithmic Learning Theory, Twentieth International Conference, ALT 2009, Porto, Portugal, October 3-5, 2009. Proceedings. Springer LNAI 5809:338-352, 2009.
  31. Frank Stephan, Yue Yang and Liang Yu. Turing degrees and the Ershov hierarchy. (TRC6/09) Proceedings of the Tenth Asian Logic Conference, Kobe, Japan, 1-6 September 2008, World Scientific, pages 300-321, 2009.
  32. Sanjay Jain, Qinglong Luo and Frank Stephan. Learnability of automatic classes. (TRA1/09) Language and Automata Theory and Applications, Fourth International Conference, LATA 2010, Trier, May 2010, Proceedings. Springer LNCS 6031:293-307, 2010. Technical Report TRA1/09, School of Computing, National University of Singapore, 2009.
  33. Laurent Bienvenu, Frank Stephan and Jason Teutsch. How powerful are integervalued martingales? 6th Conference on Computability in Europe, CiE 2010, Ponta Delgada, Azores, Portugal, June 30 - July 4, 2010, Proceedings. Springer LNCS 6158:59-68, 2010.
  34. Hongyang Li and Frank Stephan. Splitting of learnable classes. Grammatical Inference: Theoretical Results and Applications, Tenth International Colloquium, ICGI 2010, Valencia, Spain, September 13-16, 2010. Proceedings. Springer LNCS 6339:109-121, 2010.
  35. Rupert Hoelzl, Thorsten Kraeling, Frank Stephan and Guohua Wu. Initial segment complexities of randomness notions. Sixth IFIP TC 1/WG 2.2 International Conference on Theoretical Computer Science, IFIP TCS 2010, Brisbane, Australia, September 20-23, 2010. Proceedings. Springer IFIP 232:259-270, 2010.
  36. Sanjay Jain, Frank Stephan and Jason Teutsch. Closed left-r.e.sets. Theory and Models of Computation 2011, Eighth annual conference, TAMC 2011, Tokyo, Japan, May 2011, Proceedings. Springer LNCS 218-229, 2011.
  37. John Case, Sanjay Jain, Yuh Shin Ong, Pavel Semukhin and Frank Stephan. Automatic learners with feedback queries. Seventh conference on Computability in Europe, CiE 2011, Sofia, Bulgaria, June/July 2011, Proceedings. Springer LNCS 6735:31-40, 2011.
  38. Philipp Schlicht and Frank Stephan. Automata on ordinals and linear orders. Seventh conference on Computability in Europe, CiE 2011, Sofia, Bulgaria, June/July 2011, Proceedings. Springer LNCS 6735:252-259, 2011.
  39. John Case, Sanjay Jain, Trong Dao Le, Yuh Shin Ong, Pavel Semukhin and Frank Stephan. Automatic learning of subclasses of pattern languages. Language and Automata Theory and Applications, LATA 2011, Taragona, Spain, May 2011, Proceedings. Springer LNCS 6638:192-203, 2011.
  40. Sanjay Jain, Yuh Shin Ong, Shi Pu and Frank Stephan. On automatic families. (TRB1/10) Proceedings of the eleventh Asian Logic Conference in honour of Professor Chong Chitat on his sixtieth birthday, pages 94-113, World Scientific, 2012.
  41. Frank Stephan, Ryo Yoshinaka and Thomas Zeugmann. On the Parameterised Complexity of Learning Patterns. Computer and Information Sciences II - 26th International Symposium on Computer and Information Sciences, London, UK, 26-28 September 2011. Springer, pages 277-281, 2011.
  42. Ziyuan Gao, Frank Stephan, Guohua Wu and Akihiro Yamamoto. Learning families of closed sets in matroids. Computation, Physics and Beyond; International Workshop on Theoretical Computer Science, WTCS 2012, Springer LNCS 7160:120-139, 2012.
  43. Ziyuan Gao and Frank Stephan. Learnability of co-r.e.classes. Language and Automata Theory and Applications - Sixth International Conference, LATA 2012, Spain, March 5-9, 2012. Proceedings. Springer LNCS 7183:252-263, 2012.
Bookchapters, introductions and examination texts
  1. Wolfram Menzel and Frank Stephan. Inductive versus approximative learning. Perspectives on Adaptivity and Learning, edited by Reimer Kuehn, Randolf Menzel, Wolfram Menzel, Ulrich Ratsch, Michael M. Richter, Ion-Olimpiu Stamatescu. Springer, pages 187-209, 2003.
  2. Frank Stephan. The complexity of the set of nonrandom numbers. (TRC2/07) Randomness and Complexity, from Leibnitz to Chaitin, edited by Cristian S.Calude. World Scientific, pages 217-230, 2007.
  3. Jose L.Balcazar, Philip M.Long and Frank Stephan. Editors' Introduction for Algorithmic Learning Theory, Seventeenth International Conference, ALT 2006, Barcelona, Spain, October 7-10, 2006. Proceedings. Springer LNAI 4264:1-9, 2006.
  4. Frank Stephan. X-Raeume als Verallgemeinerung topologischer Raeume. Dissertation, Karlsruhe 1990.
  5. Frank Stephan. Degrees of Computing and Learning. (Updated Version) (TR 46) Habilitationsschrift at the Universitaet Heidelberg. Revised version, published as Forschungsberichte Mathematische Logik 46 / 1999, Mathematisches Institut, Universitaet Heidelberg, Heidelberg, 1999.
Technical reports and manuscripts
  1. Martin Kummer and Frank Stephan. Some aspects of frequency computation. Interner Bericht Nr. 21 / 1991, Fakultaet fuer Informatik, Universitaet Karlsruhe (T.H.), 76128 Karlsruhe, 1991.
  2. William Gasarch and Frank Stephan. Finding isolated cliques by queries - an approach to fault diagnosis with many faults. (Dagstuhl 04421) Dagstuhl Seminar Proceedings 04421, Algebraic Methods in Computational Complexity, Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany, 2005.
  3. Johanna Franklin and Frank Stephan. Van Lambalgen's theorem and high degrees. Manuscript, 2009.
  4. Eric Martin, Wai Yan Pong and Frank Stephan. Implementing fragments of ZFC within an r.e.universe. (TRE6/09) Technical Report TRE6/09, School of Computing, National University of Singapore, 2009.
  5. Sanjay Jain, Eric Martin and Frank Stephan. Robust learning of automatic classes of languages. (TRA4/10) Technical Report TRA4/10, School of Computing, National University of Singapore, 2010.
  6. Pavel Semukhin and Frank Stephan. Automatic structures and model theory. Manuscript, 2010.
  7. Johanna Franklin, Noam Greenberg, Frank Stephan and Guohua Wu. Anticomplex sets and reducibilities with tiny use. Manuscript, 2011.
  8. Sanjay Jain, Eric Martin and Frank Stephan. Learning and classifying. Manuscript, 2011.
  9. Johanna Franklin and Frank Stephan. Intersections of r.e.and random sets. Manuscript, 2012.
  10. John Case, Sanjay Jain, Samuel Seah and Frank Stephan. Automatic functions, linear time and learning. Manuscript, 2012.
  11. Sanjay Jain, Alexei Miasnikov and Frank Stephan. The complexity of verbal languages over groups. Manuscript, 2012.
  12. Sanjay Jain, Timo Koetzing and Frank Stephan Unionability and extendability of learnable classes. Manuscript, 2012.
  13. Ziyuan Gao and Frank Stephan. Confident and consistent partial learning of recursive functions. Manuscript, 2012.