Frank Christian STEPHAN

Habilitation (Mathematics, University of Heidelberg, Germany, 1999)
Ph.D. (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 Interests

  • Automata Theory
  • Learning Theory
  • Recursion Theory
  • Inductive Inference
  • Automatic Structures
  • Infinite Games On Finite Graphs
  • Computational Complexity and Parameterised Complexity
  • Algorithmic Randomness and Kolmogorov 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.

Current Projects

Selected Publications

  • Carl Jockusch and Frank Stephan. A cohesive set which is not high. Mathematical Logic Quarterly 39(1):515-530, 1993 and 43(4):569-569, 1997. 

  • Richard Beigel, Martin Kummer and Frank Stephan. Approximable Sets. Information and Computation 120(2):304-314, 1995. 

  • Efim Kinber and Frank Stephan. Language learning from texts: mindchanges, limited memory and monotonicity. Information and Computation 123(2):224-241, 1995. 

  • Martin Kummer and Frank Stephan. On the structure of degrees of inferability. Journal of Computer and System Sciences 52(2):214-238, 1996. 

  • Frank Stephan. On the structures inside truth-table degrees. The Journal of Symbolic Logic 66(2):731-770, 2001. 

  • André Nies, Frank Stephan and Sebastiaan A. Terwijn. Randomness, relativization and Turing degrees. The Journal of Symbolic Logic 70(2):515-535, 2005. 

  • Bakhadyr Khoussainov, André Nies, Sasha Rubin and Frank Stephan. Automatic Structures: Richness and Limitations. Logical Methods in Computer Science 3(2), 2007. 

  • Ganesh Baliga, John Case, Wolfgang Merkle, Frank Stephan and Rolf Wiehagen. When unlearning helps. Information and Computation, 206(5):694-709, 2008. 

  • Bjørn Kjos-Hanssen, Wolfgang Merkle and Frank Stephan. Transactions of the American Mathematical Society 363(10):5465-5480, 2011. 

  • Sanjay Jain, Qinglong Luo and Frank Stephan. Learnability of automatic classes. Journal of Computer and System Sciences 78(6):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 61(4):1254-1287, 2017. 

Awards & Honours

Teaching (2020/2021)

  • CS5236: Advanced Automata Theory