Pavel Semukhin

Research Associate
Department of Computer Science
University of Oxford

Email:  





Research interests:  reachability problems, automata theory, algorithmic learning theory, computability theory.


PhD Thesis:
    Topics in Computable Model Theory, The University of Auckland, 2008.
    PostScript –  PDF
 


List of Publications:
  1. I. Potapov and P. Semukhin, Membership problem in GL(2, Z) extended by singular matrices, Mathematical foundations of Computer Science , MFCS, 44:1–44:13, 2017.
      PDF
  2. I. Potapov and P. Semukhin, Decidability of the membership problem for 2×2 integer matrices, ACM-SIAM Symposium on Discrete Algorithms, SODA, 170–186, 2017.
      PDF –  Slides
  3. I. Potapov and P. Semukhin, Vector and Scalar reachability problem in SL(2, Z), submitted to J. Computer and System Sciences.
      PDF
  4. I. Potapov and P. Semukhin, Vector reachability problem in SL(2, Z), Mathematical foundations of Computer Science, MFCS, 84:1–84:14, 2016.
      PDF
  5. E. Fokina, B. Khoussainov, P. Semukhin, and D. Turetsky, Linear orders realized by c.e. equivalence relations, J. Symbolic Logic, 81(2): 463–482, 2016.
      PDF
  6. R. Samei, P. Semukhin, B. Yang and S. Zilles, Sample Compression for Multi-label Concept Classes, extended journal version, submitted for publication.
      PDF
  7. R. Samei, P. Semukhin, B. Yang and S. Zilles, Sample Compression for Multi-label Concept Classes, Conference on Learning Theory, COLT, 371–393, 2014.
      PDF
  8. R. Samei, P. Semukhin, B. Yang and S. Zilles, Algebraic methods proving Sauer's bound for teaching complexity, Theoretical Computer Science, 558: 35–50, 2014.
      PDF
  9. J. Case, S. Jain, Y. Ong, P. Semukhin and F. Stephan, Automatic learners with feedback queries, Journal of Computer and System Sciences, 80(4): 806–820, 2014.
      PDF
  10. R. Samei, P. Semukhin, B. Yang and S. Zilles, Sauer's bound for a notion of teaching complexity, Algorithmic Learning Theory, ALT 2012. Proceedings. Springer LNAI 7568: 96–110, 2012.
      PDF
  11. P. Semukhin and F. Stephan, Automatic models of first-order theories, Annals of Pure and Applied Logic, 164(9): 837–854, 2013.
      PDF
  12. J. Case, S. Jain, T. Le, Y. Ong, P. Semukhin and F. Stephan, Automatic learning of subclasses of pattern languages, Information and Computation, 218: 17–35, 2012. Language and Automata Theory and Applications, LATA 2011. Proceedings. Springer LNCS 6638: 192–203, 2011.
      PDF
  13. J. Case, S. Jain, Y. Ong, P. Semukhin and F. Stephan, Automatic learners with feedback queries, Computability in Europe, CiE 2011. Proceedings. Springer LNCS 6735: 31–40, 2011.
      PDF
  14. S. Jain, Q. Luo, P. Semukhin, F. Stephan, Uncountable automatic classes and learning, Theoretical Computer Science, 412(19): 1805–1820, 2011. Algorithmic Learning Theory, ALT 2009. Proceedings. Springer LNAI 5809: 293–307, 2009.
      PDF
  15. P. Semukhin, Prime models of finite computable dimension, J. Symbolic Logic, 74(1): 336–348, 2009.
      PDF
  16. A. Nies, P. Semukhin, Finite automata presentable abelian groups, Annals of Pure and Applied Logic, 161(3): 458–467, 2009.
      PDF
  17. B. Khoussainov, P. Semukhin, F. Stephan, Applications of Kolmogorov complexity to computable model theory, J. Symbolic Logic, 72(3): 1041–1054, 2007.
      PDF
  18. A. Nies, P. Semukhin, Finite automata presentable abelian groups, Proc. of Logical Foundations of Computer Science, LFCS, 422–436, 2007.
      PDF
  19. B. Khoussainov, T. Slaman, P. Semukhin, Π01-presentations of algebras, Arch. Math. Logic, 45(6): 769–781, 2006.
      PDF
  20. D. Hirschfeldt, B. Khoussainov, P. Semukhin, An uncountably categorical theory whose only computably presentable model is saturated, Notre Dame J. Formal Logic 47(1): 63–71, 2006.
      PDF
  21. P. Semukhin, Degree spectra of definable relations on Boolean algebras, Sibirsk. Mat. Zh. 46(4): 928–941, 2005; translation in Siberian Math. J. 46(4): 740–750, 2005.
      PDF (in English)
      PDF (in Russian)
  22. P. Semukhin, Spectrum of the ideal of atomless elements in a recursive Boolean algebra, Vestnik NGU, Ser. Mat. Mekh. Inform. (Bull. of Novosibirsk State Univ., Series: math., mech. and informatics) 1(2): 108–111, 2001.

Conference talks:
  1. Membership problem for 2×2 integer matrices,
    Oxford University CS Departmental Seminar, Oxford, July, 2017.
  2. Membership problem for 2×2 nonsingular integer matrices,
    Computability in Europe, Turku, June, 2017.
  3. Decidability of the Membership problem for 2×2 integer matrices,
    Symposium of Discrete Algorithms, Barcelona, January, 2017.
  4. Decidability of the Membership problem for 2×2 integer matrices,
    Reachability Problems, Aalborg, September, 2016.
  5. Vector reachability problem in SL(2, Z),
    Mathematical Foundations of Computer Science, Krakow, August, 2016.
  6. Decidability of reachability problems in SL(2, Z),
    Logic Colloquium, Leeds, August, 2016.
  7. Degree spectra of structures under Σ1-equivalence,
    Logic Colloquium, Vienna, July, 2014.
  8. Automatic models of first-order theories,
    Invited talk at AMS Spring Western Section Meeting, Honolulu, HI, March, 2012.
  9. Automatic models of first-order theories,
    Workshop on Automata Theory and Applications, Singapore, September, 2011.
  10. Uncountable automatic classes and learning,
    Algorithmic Learning Theory, Porto, October, 2009.
  11. Prime models of finite computable dimension,
    Computability in Europe, Heidelberg, July, 2009.
  12. Finite automata presentable abelian groups,
    Logical Foundations of Computer Science symposium, New York, June, 2007.
  13. Applications of Kolmogorov complexity to computable model theory,
    Workshop on Computability, Randomness and Model Theory, Auckland, 2006.
  14. On Π01-presentations of algebras,
    The 9th Asian Logic Conference, Novosibirsk, August, 2005.
  15. Spectrum of the Atomless Elements Ideal,
    Proceedings of the workshop "Computability and models", Almaty, June 24–28, 2002.