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,
Journal of Logic and Analysis,
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.

Many publications are also available as Technical Reports at the School of Computing of the NUS.

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). The 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. Bjoern 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. Nineteenth 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. Bjoern 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 412:2253-2261, 2011. Developments in Language Theory, Twelfth International Conference, DLT 2008, Kyoto, Japan. Proceedings. Springer LNCS 5257:170-182, 2008.
  86. Sanjay Jain, Qinglong Luo, Pavel Semukhin and Frank Stephan. Uncountable automatic classes and learning. (TRB1/09) Theoretical Computer Science 412:1805-1820, 2011. Algorithmic Learning Theory, Twentieth International Conference, ALT 2009, Porto, Portugal, October 3-5, 2009. Proceedings. Springer LNAI 5809:293-307, 2009.
  87. 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.
  88. Johanna Franklin and Frank Stephan. Van Lambalgen's theorem and high degrees. Notre Dame Journal of Formal Logic, 25:173-185, 2011.
  89. Bjoern Kjos-Hanssen, Wolfgang Merkle and Frank Stephan. Kolmogorov Complexity and the Recursion Theorem. (0901.3933) Transactions of the American Mathematical Society, 263:5465-5480, 2011. 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.
  90. Frank Stephan and Jason Teutsch. An incomplete set of shortest descriptions. The Journal of Symbolic Logic, 77:291-307, 2012.
  91. Laurent Bienvenu, Frank Stephan and Jason Teutsch. How powerful are integervalued martingales? Theory of Computing Systems, 51:330-351, 2012. 6th Conference on Computability in Europe, CiE 2010, Ponta Delgada, Azores, Portugal, June 30 - July 4, 2010, Proceedings. Springer LNCS 6158:59-68, 2010.
  92. John Case, Sanjay Jain, Trong Dao Le, Yuh Shin Ong, Pavel Semukhin and Frank Stephan. Automatic learning of subclasses of pattern languages. Information and Computation, 218:17-35, 2012. Language and Automata Theory and Applications, LATA 2011, Taragona, Spain, May 2011, Proceedings. Springer LNCS 6638:192-203, 2011.
  93. Sanjay Jain, Qinglong Luo and Frank Stephan. Learnability of automatic classes. (TRA1/09) Journal of Computer and System Sciences, 78:1910-1927, 2012. Language and Automata Theory and Applications, Fourth International Conference, LATA 2010, Trier, May 2010, Proceedings. Springer LNCS 6031:293-307, 2010.
  94. Bjoern Kjos-Hanssen, Frank Stephan and Jason Teutsch. Arithmetic complexity via effective names for random sequences. ACM Transactions on Computational Logic, 13(3):24:1-24:18, 2012.
  95. Frank Stephan and Guohua Wu. Highness, locally noncappability and nonboundings. Annals of Pure and Applied Logic 164:511-522, 2013.
  96. Philipp Schlicht and Frank Stephan. Automata on ordinals and linear orders. Annals of Pure and Applied Logic 164:523-527, 2013. Seventh conference on Computability in Europe, CiE 2011, Sofia, Bulgaria, June/July 2011, Proceedings. Springer LNCS 6735:252-259, 2011.
  97. Pavel Semukhin and Frank Stephan. Automatic models of first order theories. Annals of Pure and Applied Logic 164:837-854, 2013.
  98. Johanna Franklin, Noam Greenberg, Frank Stephan and Guohua Wu. Anticomplex sets and reducibilities with tiny use. The Journal of Symbolic Logic, 78:1307-1327, 2013.
  99. John Case, Sanjay Jain, Samuel Seah and Frank Stephan. Automatic functions, linear time and learning. Logical Methods in Computer Science, 9(3), 2013. How the World Computes - Turing Centenary Conference and Eighth Conference on Computability in Europe, CiE 2012, Cambridge, UK, June 18-23, 2012. Proceedings. Springer LNCS 7318:96-106, 2012.
  100. Rupert Hoelzl, Thorsten Kraeling, Frank Stephan and Guohua Wu. Initial segment complexities of randomness notions. Information and Computation 234:57-67, 2014. 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.
  101. Frank Stephan and Jason Teutsch. Things which can be made into themselves. (1208.0682v3) Information and Computation, 237:174-186, 2014.
  102. Sanjay Jain, Eric Martin and Frank Stephan. Robust learning of automatic classes of languages. (TRA4/10) Journal of Computer and System Sciences, 80:777-795, 2014. Algorithmic Learning Theory, Twentysecond International Conference, ALT 2011, Espoo, Finland, October 5-7, 2011. Proceedings. Springer LNAI 6925:55-69, 2011.
  103. John Case, Sanjay Jain, Yuh Shin Ong, Pavel Semukhin and Frank Stephan. Automatic learners with feedback queries. Journal of Computer and System Sciences, 80:806-820, 2014. Seventh conference on Computability in Europe, CiE 2011, Sofia, Bulgaria, June/July 2011, Proceedings. Springer LNCS 6735:31-40, 2011.
  104. Alex Gavryushkin, Sanjay Jain, Bakhadyr Khoussainov and Frank Stephan. Graphs realised by r.e. equivalence relations. (455) Annals of Pure and Applied Logic, 165:1263-1290, 2014.
  105. Frank Stephan and Liang Yu. A reducibility related to being hyperimmune-free. Annals of Pure and Applied Logic, 165:1291-1300, 2014.
  106. Keng Meng Ng, Andre Nies and Frank Stephan. The complexity of recursive splittings of random sets. Computability, 3:1-8, 2014.
  107. Cameron Freer, Bjoern Kjos-Hanssen, Andre Nies and Frank Stephan. Algorithmic aspects of Lipschitz functions. (1402.2429) Computability, 3:45-61, 2014.
  108. Ziyuan Gao and Frank Stephan. Confident and consistent partial learning of recursive functions. (TRB7/14) Theoretical Computer Science, 558:5-17, 2014. Algorithmic Learning Theory, Twentythird International Conference, ALT 2012, Lyon, France, October 29-31, 2012. Proceedings. Springer LNAI 7568:51-65, 2012.
  109. Stephen G. Simpson and Frank Stephan. Cone avoidance and randomness preservation. Annals of Pure and Applied Logic, 166:713-728, 2015.
  110. Chitat Chong, Gordon Hoi, Frank Stephan and Daniel Turetsky. Partial functions and Domination. (1506.06869) Logical Methods in Computer Science 11(3), 2015.
  111. Rupert Hoelzl, Frank Stephan and Liang Yu. On Martin's Pointed Tree Theorem. (1404.2073) Computability 5:147-157, 2015.
  112. Cristian S. Calude, Rusins Freivalds, Sanjay Jain and Frank Stephan. Deterministic frequency pushdown automata. (JUCS-Version) Journal of Universal Computer Science, 21:1563-1576, 2015.
  113. Christopher Hanrui Chak, Rusins Freivalds, Frank Stephan and Henrietta Tan Wan Yik. On Block Pumpable Languages. Theoretical Computer Science, 609:272-285, 2016.
  114. Alex Gavryushkin, Bakhadyr Khoussainov and Frank Stephan. Reducibilities among Equivalence Relations induced by Recursively Enumerable Structures. (456) Theoretical Computer Science, 612:137-152, 2016.
  115. Ziyuan Gao, Frank Stephan and Sandra Zilles. Partial learning of recursively enumerable languages. Theoretical Computer Science 620:137-152, 2016. Algorithmic Learning Theory, Twentyfourth International Conference, ALT 2013, Singapore, October 6-9, 2013. Proceedings. Springer LNAI 8139:113-127, 2013.
  116. Sanjay Jain, Bakhadyr Khoussainov, Philipp Schlicht and Frank Stephan. Tree-automatic scattered linear orders. Theoretical Computer Science, 626:83-96, 2016.
  117. Cristian S. Calude, Ludwig Staiger and Frank Stephan. Finite state incompressible infinite sequences. Information and Computation, 247:23-36, 2016. Theory and Applications of Models of Computation - Eleventh Annual Conference, TAMC 2014, Chennai, India, April 11-13, 2014. Proceedings. Springer LNCS 8402:50-66, 2014.
  118. Sanjay Jain, Timo Koetzing, Junqi Ma and Frank Stephan. On the role of update constraints and text-types in iterative learning. Information and Computation, 247:152-168, 2016. (TRA7/14) Algorithmic Learning Theory - Twentyfifth International Conference, ALT 2014, Bled, Slovenia, 8-10 October 2014, Springer LNCS, 8776:55-69, 2014.
  119. Rupert Hoelzl, Sanjay Jain and Frank Stephan. Inductive inference and reverse mathematics. Annals of Pure and Applied Logic 167:1242-1266, 2016. Thritysecond International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4-7, 2015, Garching, Germany. LIPIcs 30, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pages 420-433, 2015.
  120. Sanjay Jain, Timo Koetzing and Frank Stephan. Enlarging learnable classes. Information and Computation 251:194-207, 2016. Algorithmic Learning Theory, Twentythird International Conference, ALT 2012, Lyon, France, October 29-31, 2012. Proceedings. Springer LNAI 7568:36-50, 2012.
  121. Bjoern Kjos-Hanssen, Frank Stephan and Sebastiaan A. Terwijn. Covering the recursive sets. Annals of Pure and Applied Logic, 168(4):804-823, 2017. Evolving Computability - Eleventh Conference on Computability in Europe, CiE2015, Bucharest, Romania, 29 June - 3 July 2015. Proceedings. Springer LNCS 9136:44-53, 2015.
  122. Sanjay Jain, Frank Stephan and Jason Teutsch. Closed left-r.e. sets. Computability, 6(1):1-21, 2017. Theory and Models of Computation 2011, Eighth Annual Conference, TAMC 2011, Tokyo, Japan, May 2011, Proceedings. Springer LNCS 6648:218-229, 2011.
  123. Philippe Moser and Frank Stephan. Depth, highness and DNR degrees. Discrete Mathematics and Theoretical Computer Science, 19(4-2):1-15, 2017. Fundamentals of Computation Theory, Twentieth International Symposium, FCT 2015, Gdansk, Poland, August 17-19, 2015, Proceedings. Springer LNCS 9210, 81-94, 2015.
  124. Sanjay Jain, Bakhadyr Khoussainov, Frank Stephan, Dan Teng and Siyuan Zou. Semiautomatic structures. Theory of Computing Systems, 61(4):1254-1287, 2017. Computer Science - Theory and Applications - Ninth International Computer Science Symposium in Russia, CSR 2014, Moscow, Russia, June 7-11, 2014. Proceedings. Springer LNCS 8476:204-217, 2014.
  125. Kenshi Miyabe, Andre Nies and Frank Stephan. Randomness and Solovay Degrees. Journal of Logic and Analysis, 10(3):1-13, 2018.
  126. Philippe Moser and Frank Stephan. Limit-depth and DNR degrees. Information Processing Letters, 135:36-40, 2018.
  127. John Case, Sanjay Jain and Frank Stephan. Effectivity questions for Kleene's Recursion Theorem. Theoretical Computer Science, 733:55-70, 2018. Symposium on Logical Foundations in Computer Science, LFCS 2013, San Diego, CA, USA, January 2013. Springer LNCS 7734:89-103, 2013.
  128. Rupert Hoelzl, Sanjay Jain and Frank Stephan. Learning pattern languages over groups. Theoretical Computer Science, 742:66-81, 2018. Algorithmic Learning Theory - Twentyseventh International Conference, ALT 2016, Bari, Italy, October 19-21, 2016, Proceedings. Springer LNCS 9925:189-203, 2016.
  129. Eric Martin and Frank Stephan. Implementing fragments of ZFC within an r.e. universe. Journal of Logic and Computation, 28(1):1-32, 2018. (TRE6/09) Technical Report TRE6/09, School of Computing, National University of Singapore, 2009.
  130. Sanjay Jain, Bakhadyr Khoussainov and Frank Stephan. Finitely generated semiautomatic groups. Computability, 7(2-3):273-287, 2018. Pursuit of the Universal, Twelfth Conference on Computability in Europe, CiE 2016, Paris, France, 27 June - 1 July 2016, Proceedings. Springer LNCS 9709:282-291, 2016.
  131. George Barmpalias, Nan Fang and Frank Stephan. Equivalences between learning of data and probability distributions and their applications. Information and Computation 262:123-140, 2018.
  132. Sanjay Jain, Bakhadyr Khoussainov, Philipp Schlicht and Frank Stephan The isomorphism problem for tree-automatic ordinals with addition. Information Processing Letters, 149:19-24, 2019.
  133. Sanjay Jain, Alexei Miasnikov and Frank Stephan. The complexity of verbal languages over groups. Journal of Computer and System Sciences, 101:68-85, 2019. Twentyseventh IEEE Symposium on Logic in Computer Science, LICS 2012, 25-28 June 2012, Dubrovnik, Croatia; IEEE Computer Society, pages 405-414, 2012.
  134. Ian Herbert, Sanjay Jain, Manat Mustafa, Steffen Lempp and Frank Stephan. Reductions between types of numberings. Annals of Pure and Applied Logic, 170:102716:1-25, 2019.
  135. Cristian S. Calude, Sanjay Jain, Wolfgang Merkle and Frank Stephan. Searching for shortest and least programs. Theoretical Computer Science, 807:114-127, 2020.
  136. Rupert Hoelzl, Wolfgang Merkle, Joseph Miller, Frank Stephan and Liang Yu. Chaitin's Omega as a continuous function. The Journal of Symbolic Logic, 85:486-510, 2020.
  137. Kojiro Higuchi, Steffen Lempp, Dilip Raghavan and Frank Stephan. On the order dimension of locally countable partial orderings. Proceedings of the AMS, 148:2823-2833, 2020. Also available as technical report on http://arxiv.org/abs/1902.06030.
  138. Cristian S. Calude, Karen Frilya Celine, Ziyuan Gao, Sanjay Jain, Ludwig Staiger and Frank Stephan. Bi-immunity of different size alphabets. Theoretical Computer Science 894:31-49, 2021. Also available as technical report Research Reports CDMTCS-552 at the University of Auckland https://researchspace.auckland.ac.nz/handle/2292/58014
  139. Gordon Hoi and Frank Stephan. Improved algorithms for the generalised exact satisfiability problem. Theoretical Computer Science 889:60-84, 2021.
  140. Sanjay Jain, Frank Stephan and Thomas Zeugmann. On the amount of nonconstructivity in learning formal languages from text. Information and Computation 281:101893, 2021.
  141. Ziyuan Gao, Sanjay Jain, Zeyong Li, Ammar Fathin Sabili and Frank Stephan. A computation model with automatic functions and relations as primitive operations. Theoretical Computer Science 924:94-116, 2022.
  142. Andre Nies and Frank Stephan. Randomness and initial segment complexity for measures. Theoretical Computer Science 900:1-19, 2022. Title of technical report: A weak randomness notion for probability measures. Technical Report on http://arxiv.org/abs/1902.07871, 2019.
  143. Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li and Frank Stephan. Deciding parity games in quasipolynomial time. SIAM Journal on Computing 51(2):17-152, 2022. Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017. Pages 252-263, ACM, 2017. (STOC 2017 Best Paper Award) See also: Technical Report, Centre for Discrete Mathematics and Theoretical Computer Science, University of Auckland, Number 500, October 2016, Revised April 2017 (Auckland CDMTCS500)
  144. Sanjay Jain, Shao Ning Kuek, Eric Martin and Frank Stephan. Learners based on transducers. Information and Computation 283:104676, 2022. Language and Automata Theory and Applications - Twelfth International Conference, LATA 2018, Ramat Gan, Israel, 9-11 April 2018, Proceedings. Springer LNCS, 10792:169-181, 2018.
  145. Sanjay Jain, Birzhan Moldagaliyev, Frank Stephan and Tien Dat Tran. Lamplighter groups and automata. Acta Informatica 59(4):451-478, 2022.
  146. {BJKS23} Dmitry Berdinsky, Sanjay Jain, Bakhadyr Khoussainov and Frank Stephan. String-compression in FA-presentable structures. Theoretical Computer Science 947:113705, 2023.
  147. Sanjay Jain, Xiaodong Jia, Ammar Fathin Sabili and Frank Stephan. Addition machines, automatic functions and open problems of Floyd and Knuth. Journal of Computer and System Sciences, 136:135-156, 2023.
Refereed 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 2003; IEEE Computer Society, pages 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. 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.
  21. 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.
  22. 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.
  23. 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.
  24. 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.
  25. Frank Stephan. Hausdorff-dimension and weak truth-table reducibility. (TR52/05) Logic Colloquium 2004, ASL Lecture Notes in Logic 29:157-167, 2008.
  26. 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.
  27. Sanjay Jain and Frank Stephan. Consistent partial identification. (COLT 2009) Computational Learning Theory, Proceedings, 10 pages, 2009.
  28. 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.
  29. 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.
  30. 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.
  31. 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.
  32. Sanjay Jain, Eric Martin and Frank Stephan. Learning and classifying. Algorithmic Learning Theory, Twentysecond International Conference, ALT 2011, Espoo, Finland, October 5-7, 2011. Proceedings. Springer LNAI 6925:70-83, 2011.
  33. 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.
  34. 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.
  35. 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.
  36. Wolfgang Merkle, Frank Stephan, Jason Teutsch, Wei Wang and Yue Yang. Selection by recursively enumerable sets. Theory and Models of Computation 2013, Tenth International Conference, TAMC 2013, Hong Kong, China, May 2013, Proceedings. Springer LNCS 7876:144-155, 2013.
  37. Ziyuan Gao, Sanjay Jain and Frank Stephan. On conservative learning of r.e. languages. Ninth Conference on Computability in Europe, CiE 2013, Milan, Italy, July 1-5, 2013. Springer LNCS 7921:181-190, 2013.
  38. Ziyuan Gao, Sanjay Jain, Frank Stephan and Sandra Zilles. A survey on recent results on partial learning. Proceedings of the Thirteenth Asian Logic Conference, World Scientific, pages 68-92, 2015.
  39. Sanjay Jain, Junqi Ma and Frank Stephan. Priced learning. Algorithmic Learning Theory - Twentysixth International Conference, ALT 2015, Banff, AB, Canada, October 4-6, 2015, Proceedings. Springer LNCS 9355, 41-55, 2015.
  40. Ziyuan Gao, Frank Stephan and Sandra Zilles. Combining models of approximation with partial learning. Algorithmic Learning Theory - Twentysixth International Conference, ALT 2015, Banff, AB, Canada, October 4-6, 2015, Proceedings. Springer LNCS 9355:56-70, 2015.
  41. John Fearnley, Sanjay Jain, Sven Schewe, Frank Stephan and Dominik Wojczak. An ordered approach to solving parity games in quasi polynomial time and quasi linear space. SPIN 2017, The Proceedings of the 24th International ACM SIGSOFT International SPIN Symposium on Model Checking of Software, pages 112-121, 2017. See also: Technical report on http://arxiv.org/abs/1703.01296, 2017. (1703.01296)
  42. Rupert Hoelzl, Sanjay Jain, Philipp Schlicht, Karen Seidel and Frank Stephan. Automatic learning from repetative texts. International Conference on Algorithmic Learning Theory, ALT 2017, 15-17 October 2017, Kyoto University, Kyoto, Japan. Proceedings of Machine Learning Research, 76:129-150, 2017.
  43. Andre Nies and Frank Stephan. Robustness of resource bounded randomness notions. Symposium on Theoretical Aspects of Computer Science, LIPICS Proceedings, STACS 2018, 51:1-10, 2018.
  44. Ziyuan Gao, Sanjay Jain, Frank Stephan and Thomas Zeugmann. On the help of bounded shot verifiers, comparators and standardisers for learnability in inductive inference. International Conference on Algorithmic Learning Theory, ALT 2018, 7-9 April 2018, Lanzarote, Canary Islands, Spain Proceedings of Machine Learning Research, 83:413-437, 2018.
  45. Gordon Hoi, Sanjay Jain, Sibylle Schwarz and Frank Stephan. Exact satisfiability with jokers. International Conference on Theory and Applications of Models of Computation, TAMC 2019, Springer LNCS, 11436:279-294, 2019.
  46. Aquinas Hobor, Elaine Li and Frank Stephan. Pumping, with or Without Choice. Programming Languages and Systems - Seventeenths Asian Symposium, APLAS 2019, Springer LNCS 11893:427-446, 2019.
  47. Gordon Hoi, Sanjay Jain and Frank Stephan. A fast exponential time algorithm for Max Hamming Distance X3SAT. Thirtyninth IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2019, LIPIcs 150:17:1-17:14, 2019.
  48. Gordon Hoi and Frank Stephan. Measure and Conquer for Max Hamming Distance XSAT. Thirtieth International Symposium on Algorithms and Computation, ISAAC 2019, LIPIcs 149:15:1-15:19, 2019.
  49. Ziyuan Gao, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, Alexander G. Melnikov, Karen Seidel and Frank Stephan. Random Subgroups of Rationals. Fortyfourth International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, LIPIcs 138:25:1-25:14, 2019.
  50. Ziyuan Gao, Sanjay Jain, Ji Qi, Philipp Schlicht, Frank Stephan and Jacob Tarr. Ordered semiautomatic rings with applications to geometry. Language and Automata Theory and Applications, Fourteenth International Conference, LATA 2020, Milan, Italy, Proceedings. Springer LNCS 12038:141-153, 2020.
  51. David Belanger, Ziyuan Gao, Sanjay Jain, Wei Li and Frank Stephan. Learnability and positive equivalence relations. Language and Automata Theory and Applications - Fifteenth International Conference, LATA 2021, Milan, 1-5 March 2021, Proceedings. Springer LNCS 12638:145-156, 2021.
  52. Ziyuan Gao, Sanjay Jain, Zeyong Li, Ammar Fathin Sabili and Frank Stephan. Alternating automatic register machines. Theoretical Aspects of Computing - ICTAC 2022 - Nineteenth International Colloquium, Tbilisi, Georgia, 27-29 September 2022, Proceedings. Springer LNCS 13572:195-211, 2022.
  53. Keng Meng Ng, Frank Stephan, Yue Yang and Liang Yu. On trees without hyperimmune branches. (See the file on the coauthor's homepage.) Revolutions and Revelations in Computability - Eighteenth Conference on Computability in Europe, CiE 2022, Swansea, UK, 11-15 July 2022, Proceedings. Springer LNCS 13359:234-245, 2022.
  54. Gordon Hoi, Sanjay Jain, Ammar Fathin Sabili and Frank Stephan. A bisection approach to Subcubic Maximum Induced Matching. Accepted for Walcom 2024, Springer, 16 pages, 2024.
Bookchapters and Invited Unrefereed Talks
  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. Frank Stephan. Automatic structures - recent results and open questions. Keynote Talk. Third International Conference on Science and Engineering in Mathematics, Chemistry and Physics, ScieTech 2015 (pages 121-130 in proceedings booklet), Journal of Physics: Conference Series, 622/1 (Paper 012013) 2015.
  4. Sanjay Jain and Frank Stephan. Learning automatic families of languages. SOFSEM 2016: Theory and Practice of Computer Science - Fourty Second International Conference on Current Trends in Theory and Practice of Computer Science Harrachov, Cxech Republic, January 23-28, 2016, Proceedings. Springer LNCS 9587, 29-40, 2016.
  5. Rupert Hoelzl, Dilip Raghavan, Frank Stephan and Jing Zhang. Weakly represented families in reverse mathematics. Computability and Complexity - Essays Dedicated to Rodney G. Downey on the Occasion of His Sixtieth Birthday. Springer LNCS 10010:160-187, 2017.
Examination texts
  1. Frank Stephan. X-Raeume als Verallgemeinerung topologischer Raeume. Dissertation, Karlsruhe 1990.
  2. 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. Intersections of r.e. and random sets. Manuscript, 2012.
  4. Sanjay Jain, Efim Kinber and Frank Stephan. Automatic learning from positive data and negative counterexamples. Manuscript, 2016.
  5. Sanjay Jain, Prateek Saxena, Frank Stephan and Jason Teutsch. How to verify computation with a rational network. Technical report on http://www.arxiv.org/abs/1606.05917.
  6. Philippe Moser and Frank Stephan. Towards a theory of sophistication of sets. Manuscript, 2018.
  7. Rupert Hoelzl, Soeren Kleine and Frank Stephan. Improved lower bounds for strong n-conjectures. (Old File) Technical report on https://arxiv.org/abs/2409.13439, 2024.
  8. Gordon Hoi and Frank Stephan. Improved algorithms for the general exact satisfiablity problem. Technical report on https://arxiv.org/abs/2101.08637.
Proceedings and Special Issues Edited
  1. Jose L. Balcazar, Philip M. Long and Frank Stephan (Eds.). Algorithmic Learning Theory. Seventeenth International Conference, ALT 2006, Barcelona, Spain, October 7-10, 2006, Proceedings. Springer LNCS 4264, 2006. Special Issue in Theoretical Computer Science, Volume 405, Issue 3, Oct. 17, 2008.
  2. Marcus Hutter, Frank Stephan, Vladimir Vovk and Thomas Zeugmann (Eds.). Algorithmic Learning Theory. Twentyfirst International Conference, ALT 2010, Canberra, Australia, October 6-8, 2010. Proceedings. Springer LNCS 6331, 2010. Special Issue in Theoretical Computer Science, Volume 473, February 18, 2013.
  3. Sanjay Jain, Remi Munos, Frank Stephan and Thomas Zeugmann (Eds.). Algorithmic Learning Theory. Twentyfourth International Conference, ALT 2013, Singapore, October 6-9, 2013. Proceedings. Springer LNCS 8139, 2013. Special Issue in Theoretical Computer Science, Volume 620, March 2016.
  4. Rahul Jain, Sanjay Jain and Frank Stephan (Eds.). Theory and Applications of Models of Computation. Twelfth Annual Conference, TAMC 2015, Singapore, May 18-20, 2015, Proceedings. Springer LNCS 9076, 2015.
Lecture Notes
  1. Frank Stephan. Einfuerung in die Lerntheorie (Introduction into Learning Theory in German). University of Heidelberg, 2002.
  2. Frank Stephan. Set Theory. National University of Singapore, 2009.
  3. Frank Stephan. Recursion Theory. Also available as Technical Report TR10/12 of the School of Computing, National University of Singapore, 2012.
  4. Frank Stephan. Methods and Theory of Automata and Languages, consisting of course notes for Theory of Computation and Advanced Automata Theory, School of Computing, National University of Singapore; version of November 2016.
Webpage of former PhD student Birzhan Moldagaliyev and a link for his PhD thesis.
Further former PhD student is Gordon Hoi; currently graduating is Ammar Fathin Sabili.