Frank Christian STEPHAN

Professor (NUS Department of Mathematics)
Joint Appointed with Department of Computer Science
Habilitation (Mathematics, University of Heidelberg, Germany, 1999)
Ph.D. (Dr. of Natural Sciences: Mathematics, University of Karlsruhe, Germany, 1990)
Diploma (Computer Science, University of Karlsruhe, Germany, 1989)
651 64246

Research Areas

  • Algorithms & Theory
  • Artificial Intelligence

Research Sub Areas

Research Interests

  • Automata Theory and in particular Automatic Structures
  • Learning Theory, mainly Inductive Inference
  • Recursion Theory
  • Infinite Games On Finite Graphs, mainly Parity Games
  • Algorithmic Randomness and Kolmogorov Complexity
  • Computational Complexity and Parameterised Complexity


Frank Stephan is joint appointed by the Departments of Mathematics (primary) and Computer Science (secondary) of the National University of Singapore. He joint the NUS in 2004 after having worked at the National ICT Australia at the UNSW Sydney (2003-2004), the University of Heidelberg (1995-2003) and the University of Karlsruhe (T.H.) (1990-1995), where he studied Computer Science (Diploma) and Mathematics (Doctorate) from 1983 until 1990. Frank Stephan's research interests are within the areas of mathematical logic and theoretical computer science. In particular, he is working in recursion theory, inductive inference, automata theory, automatic structures, algorithmic randomness and computational complexity. Frank Stephan is an editor of the journal Computability and an associate editor of the Journal of Computer and System Sciences and a member of the editorial board of Information and Computation.

Research Group

Research Project

Teaching Innovation

Selected Publications

  • Carl Jockusch and Frank Stephan. A cohesive set which is not high. Mathematical Logic Quarterly 391:515-530, 1993 and 434:569-569, 1997.
  • Richard Beigel, Martin Kummer and Frank Stephan. Approximable Sets. Information and Computation 1202:304-314, 1995.
  • Efim Kinber and Frank Stephan. Language learning from texts: mindchanges, limited memory and monotonicity. Information and Computation 1232:224-241, 1995.
  • Martin Kummer and Frank Stephan. On the structure of degrees of inferability. Journal of Computer and System Sciences 522:214-238, 1996.
  • Frank Stephan. On the structures inside truth-table degrees. The Journal of Symbolic Logic 662:731-770, 2001.
  • André Nies, Frank Stephan and Sebastiaan A. Terwijn. Randomness, relativization and Turing degrees. The Journal of Symbolic Logic 702:515-535, 2005.
  • Bakhadyr Khoussainov, André Nies, Sasha Rubin and Frank Stephan. Automatic Structures: Richness and Limitations. Logical Methods in Computer Science 32, 2007.
  • Ganesh Baliga, John Case, Wolfgang Merkle, Frank Stephan and Rolf Wiehagen. When unlearning helps. Information and Computation, 2065:694-709, 2008.
  • Bjørn Kjos-Hanssen, Wolfgang Merkle and Frank Stephan. Transactions of the American Mathematical Society 36310:5465-5480, 2011.
  • Sanjay Jain, Qinglong Luo and Frank Stephan. Learnability of automatic classes. Journal of Computer and System Sciences 786:1910-1927, 2012.
  • Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li and Frank Stephan. Deciding parity games in quasipolynomial time. Proceedings of the 49th Annual ACM SIGACT Sympositum on the Theory of Computing, STOC 2017, pages 252-263, 2017 Best Paper Award.
  • Sanjay Jain, Bakhadyr Khoussainov, Frank Stephan, Dan Teng and Siyuan Zou. Semiautomatic structures. Theory of Computing Systems 614:1254-1287, 2017.
  • Reductions between types of numberings.

Awards & Honours

  • STOC 2017 Best Paper Award for Quasipolynomial Time Algorithm solving Parity Games

Teaching (2021/2022)

  • CS3231: Theory of Computation