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 a star (*)

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,
IEEE Transactions on Computers from the IEEE Computer Society,
Information and Computation from Academic Press,
Journal of Automata, Languages and Combinatorics from Otto-von-Guericke-Universitaet Magdeburg,
Journal of Computer and System Sciences from Academic Press,
Mathematical Logic Quarterly from Wiley VCH,
RAIRO Informatique Theorique et Applications from EDP Sciences,
The Journal of Symbolic Logic from the Association of Symbolic Logic,
Theoretical Computer Science from Elsevier,
Theory of Computing Systems from Springer.


Artikel in wissenschaftlichen Zeitschriften / 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, 1995, 73-90. Extended Abstract in 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. Extended Abstract in Proceedings of the Third Kurt-Goedel-Colloquium, Springer LNCS 713, 243-254, 1993.
  8. Efim Kinber and Frank Stephan. Language learning from texts: mind changes, limited memory and monotonicity. Information and Computation, 123:224-241, 1995. Extended Abstract in Proceedings of the Eighth Annual ACM Conference on Computational Learning Theory - COLT 1995, ACM-Press, 182-189, 1995.
  9. Richard Beigel, Martin Kummer and Frank Stephan. Approximable sets. Information and Computation, 120:304-314, 1995. Extended Abstract in Proceedings Structure in Complexity Theory, Ninth Annual Conference, IEEE Press, 12-23, 1994.
  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. Extended Abstract in 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. Extended Abstract in 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. (*) Theoretical Computer Science 185:129-157, 1997. Extended Abstract in 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. (*) Theory of Computing Systems, 31:679-693, 1998.
  15. Frank Stephan. Learning via queries and oracles. (*) Annals of Pure and Applied Logic, 94:273-296, 1998. Extended Abstract in 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. Extended Abstract in 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. (*) Information and Computation, 154:149-166, 1999. Extended Abstract in 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. Extended Abstract in 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. (*) Theoretical Computer Science, 241:115-141, 2000. Extended Abstract in 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. (*) 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. Extended Abstract in 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. (*) Theoretical Computer Science - Series A, 259:427-454, 2001. Extended Abstract in 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. (*) 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 (*) Theoretical Computer Science - Series A, 268:323-349, 2001. Extended Abstract in 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. (*) Theoretical Computer Science - Series A, 268:221-273, 2001. Extended Abstract in 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. (*) 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. Extended Abstract in 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. Extended Abstract in 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. (*) Theoretical Computer Science - Series A, 288:309-341, 2002. Extended Abstract (previous 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. (*) Annals of Pure and Applied Logic, 116:273-295, 2002.
  34. Wolfgang Merkle and Frank Stephan. Refuting Learning Revisited. (*) 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. Elsevier Preprint Server File (ps) (pdf)
  35. Eric Martin, Arun Sharma and Frank Stephan. Learning power and language expressiveness. (*) Theoretical Computer Science - Series A, 298:365-383, 2003.
  36. Wolfram Menzel and Frank Stephan. Topological Aspects of Numberings. (*) Mathematical Logic Quarterly, 49:129-149, 2003.
  37. Sanjay Jain and Frank Stephan. Learning by switching type of information. (*) 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. Sanjay Jain and Frank Stephan. Learning how to separate. (*) 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.
  39. Sanjay Jain, Frank Stephan and Sebastiaan A. Terwijn. Counting extensional differences in BC-learning. (*) 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.
  40. 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. Elsevier Preprint Server File (ps) (pdf)
Konferenzartikel sofern noch nicht in wissenschaftlichen Zeitschriften erschienen / Conference articles which are not yet 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. Wolfgang Merkle and Frank Stephan. Trees and learning. (*) Proceedings of the Ninth Annual Conference on Computational Learning Theory - COLT 1996, ACM-Press, 270-279, 1996. Long version: Forschungsberichte Mathematische Logik 57 / 2002, Mathematisches Institut, Universitaet Heidelberg, Heidelberg, 2002.
  3. John Case, Efim Kinber, Arun Sharma and Frank Stephan. On the classification of computable languages. Proceedings of the Symposium on Theoretical Aspects of Computer Science - STACS 1997, Springer LNCS 1200, 225-236, 1997. Long version: Technical Report No. 9603, School of Computer Science and Engineering, The University of New South Wales, Sydney, NSW 2052, Australia.
  4. 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.
  5. 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.
  6. William Gasarch and Frank Stephan. A techniques-oriented survey of bounded queries. (*) 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.
  7. Klaus Ambos-Spies, Levke Bentzien, Peter Fejer, Wolfgang Merkle and Frank Stephan. Collapsing polynomial-time degrees. (*) (PS-File of the Logic Colloquium) 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.
  8. 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.
  9. 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.
  10. Ganesh Baliga, John Case, Wolfgang Merkle and Frank Stephan. Unlearning helps. Proceedings of the 27th International Colloquium on on Automata, Languages and Programming - ICALP 2000, Springer LNCS 1853, 844-855, 2000.
  11. 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.
  12. John Case, Sanjay Jain, Frank Stephan and Rolf Wiehagen. Robust Learning - Rich and Poor. (*) 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. Long version: Technical Report LSA-2000-03E, Centre for Learning Systems and Applications, Department of Computer Science, University of Kaiserslautern, 2000.
  13. 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.
  14. Rod G. Downey, Denis R. Hirschfeldt, Andre Nies and Frank Stephan. Trivial Reals (*) 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.
  15. 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.
  16. Sanjay Jain, Wolfram Menzel and Frank Stephan. Classes with easily learnable subclasses. (*) Algorithmic Learning Theory. 13th International Conference, ALT 2002, Luebeck, Germany, November 2002, Proceedings, Springer LNCS 2533:218-232, 2002. A journal where the paper is submitted to made it availabe as a Elsevier Preprint Server File (ps) (pdf)
  17. Valentina S.Harizanov and Frank Stephan. On the learnability of vector spaces. (*) Algorithmic Learning Theory. 13th International Conference, ALT 2002, Luebeck, Germany, November 2002, Proceedings, Springer LNCS 2533:233-247, 2002. Long version: Forschungsberichte Mathematische Logik 55 / 2002, Mathematisches Institut, Universitaet Heidelberg, Heidelberg, 2002.
  18. Eric Martin, Arun Sharma and Frank Stephan. Learing, logic and topology in a common framework (updated version). Algorithmic Learning Theory. 13th International Conference, ALT 2002, Luebeck, Germany, November 2002, Proceedings, Springer LNCS 2533:248-262, 2002.
  19. Sanjay Jain and Frank Stephan. A tour of robust learning. (*) 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. (click here for book anouncement)
  20. Marcus Schaefer and Frank Stephan. Strong reductions and immunity for exponential time. 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.
  21. Bakhadyr Khoussainov, Sasha Rubin and Frank Stephan. On automatic partial orders. Proceedings of Eighteenth IEEE Symposium on Logic in Computer Science, LICS, 168-177, 2003. (*) Research Report 208, Department of Computer Science, University of Auckland, November 2003.
  22. Eric Martin, Arun Sharma and Frank Stephan. On ordinal VC-dimension and some notions of complexity. Algorithmic Learning Theory, Fourteenth International Conference, ALT 2003, Sapporo, Japan, October 2003, Proceedings; Springer LNAI 2842:54-68, 2003.
  23. John Case, Sanjay Jain, Ruediger Reischuk, Frank Stephan and Thomas Zeugmann. Learning a subclass of regular patterns in polynomial time. (*) Algorithmic Learning Theory, Fourteenth International Conference, ALT 2003, Sapporo, Japan, October 2003, Proceedings; Springer LNAI 2842:234-246, 2003. Complete version: A polynomial time learner for a subclass of regular patterns, Electronic Colloquium on Computational Complexity, TR04-038, 2004.
  24. Richard Beigel, Lance Fortnow and Frank Stephan. Infinitely-often autoreducible sets. (*) Algorithms and Computation, 14th International Symposium, ISAAC 2003, Kyoto, Japan, December 15-17, 2003, Proceedings; Springer LNCS 2906:98-107, 2003. Forschungsberichte Mathematische Logik 62 / 2003, Mathematisches Institut, Universitaet Heidelberg, Heidelberg, 2003.
Technische Berichte / Technical Reports
  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. Frank Stephan. Martin-Loef Random and PA-complete Sets. (*) Forschungsberichte Mathematische Logik 58 / 2002, Mathematisches Institut, Universitaet Heidelberg, Heidelberg, 2002.
  3. Bakhadyr Khoussainov, Sasha Rubin and Frank Stephan. Definability and Regularity in Automatic Presentations of Subsystems of Arithmetic. (*) Research Report 209, Department of Computer Science, University of Auckland, January 2003.
  4. 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.
  5. Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpre, Andrej Muchnik, Frank Stephan, Leen Torenvliet. Enumerations of the Kolmogorov function. (*) Electronic Colloquium on Computational Complexity, TR04-015, 2004.
  6. Bernd Borchert, Klaus-Joern Lange, Frank Stephan, Pascal Tesson, Denis Therien. The dot-depth and the polynomial hierarchy correspond on the delta levels. (*) Technical Report WSI-2004-3, ISSN 0946-3852, Universitaet Tuebingen, Wilhelm Schicakrd Institut fuer Informatik, 2004.
  7. Frank Stephan. X-Raeume als Verallgemeinerung topologischer Raeume. Dissertation, Karlsruhe 1990.
  8. Frank Stephan. Degrees of Computing and Learning. (Updated Version) (*) Habilitationsschrift an der Universitaet Heidelberg. Ueberarbeitete Version veroeffentlicht als Forschungsberichte Mathematische Logik 46 / 1999, Mathematisches Institut, Universitaet Heidelberg, Heidelberg, 1999.
Result of database-query on Frank Stephan's publications