Pavel Semukhin

Lecturer
Department of Computer Science
Liverpool John Moores University

Email:  





Research interests:  reachability problems in linear dynamical systems; finite and probabilistic automata; algorithmic learning theory; computability theory.


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


List of Publications:
  1. S. Kiefer, P. Semukhin and C. Widdershoven, Linear-time model checking branching processes , CONCUR, 6:1–6:16, 2021.
      PDF
  2. P. Bell and P. Semukhin, Decision questions for probabilistic automata on small alphabets, MFCS, 15:1–15:17, 2021.
      PDF
  3. P. Bell and P. Semukhin, Decidability of cutpoint isolation for probabilistic finite automata on letter-bounded inputs, CONCUR, 22:1–22:16, 2020.
      PDF
  4. V. Diekert, I. Potapov and P. Semukhin, Decidability of membership problems for flat rational subsets of GL(2, Q) and singular matrices, ISSAC, 122–129, 2020.
      PDF
  5. P. Bell, I. Potapov and P. Semukhin, On the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyond, MFCS, 83:1–83:15, 2019.
      PDF
  6. T. Colcombet, J. Ouaknine, P. Semukhin and J. Worrell, On reachability problems for low-dimensional matrix semigroups, ICALP, 44:1–44:15, 2019.
      PDF
  7. I. Potapov and P. Semukhin, Vector and Scalar reachability problem in SL(2, Z), J. Computer and System Sciences, 100: 30–43, 2019.
      PDF
  8. E. Fokina, P. Semukhin and D. Turetsky, Degree spectra of structures relative to equivalence relations, Algebra and Logic, 58(2): 158–172, 2019.
      PDF
  9. I. Potapov and P. Semukhin, Membership problem in GL(2, Z) extended by singular matrices, MFCS, 44:1–44:13, 2017.
      PDF
  10. I. Potapov and P. Semukhin, Decidability of the membership problem for 2×2 integer matrices, SODA, 170–186, 2017.
      PDF –  Slides
  11. I. Potapov and P. Semukhin, Vector reachability problem in SL(2, Z), MFCS, 84:1–84:14, 2016.
      PDF
  12. 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
  13. R. Samei, P. Semukhin, B. Yang and S. Zilles, Sample compression for multi-label concept classes, extended journal version, preprint.
      PDF
  14. R. Samei, P. Semukhin, B. Yang and S. Zilles, Sample compression for multi-label concept classes, COLT, 371–393, 2014.
      PDF
  15. 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
  16. J. Case, S. Jain, Y. Ong, P. Semukhin and F. Stephan, Automatic learners with feedback queries, J. Computer and System Sciences, 80(4): 806–820, 2014.
      PDF
  17. R. Samei, P. Semukhin, B. Yang and S. Zilles, Sauer's bound for a notion of teaching complexity, Algorithmic Learning Theory, ALT, 96–110, 2012.
      PDF
  18. P. Semukhin and F. Stephan, Automatic models of first-order theories, Annals of Pure and Applied Logic, 164(9): 837–854, 2013.
      PDF
  19. 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, 192–203, 2011.
      PDF
  20. J. Case, S. Jain, Y. Ong, P. Semukhin and F. Stephan, Automatic learners with feedback queries, Computability in Europe, CiE, 31–40, 2011.
      PDF
  21. 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, 293–307, 2009.
      PDF
  22. P. Semukhin, Prime models of finite computable dimension, J. Symbolic Logic, 74(1): 336–348, 2009.
      PDF
  23. A. Nies, P. Semukhin, Finite automata presentable abelian groups, Annals of Pure and Applied Logic, 161(3): 458–467, 2009.
      PDF
  24. B. Khoussainov, P. Semukhin, F. Stephan, Applications of Kolmogorov complexity to computable model theory, J. Symbolic Logic, 72(3): 1041–1054, 2007.
      PDF
  25. A. Nies, P. Semukhin, Finite automata presentable abelian groups, Proc. of Logical Foundations of Computer Science, LFCS, 422–436, 2007.
      PDF
  26. B. Khoussainov, T. Slaman, P. Semukhin, Π01-presentations of algebras, Arch. Math. Logic, 45(6): 769–781, 2006.
      PDF
  27. 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
  28. 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)
  29. 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.

Editorial works:
  1. I. Potapov and P. Semukhin, Special issue: Developments in Language Theory (DLT 2015), Int. J. Foundations of Computer Science, 29(2), 2018.

Conference talks:
  1. Decidability of membership problems for flat rational subsets of GL(2, Q) and singular matrices,
    International Symposium on Symbolic and Algebraic Computation, online, July, 2021.
  2. On reachability problems for low-dimensional matrix semigroups,
    International Conference on Reachability Problems, Brussels, September, 2019.
  3. On the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyond,
    Mathematical Foundations of Computer Science, Aachen, August, 2019.
  4. On reachability problems for low-dimensional matrix semigroups,
    International Colloquium on Automata, Languages and Programming, Patras, July, 2019.
  5. Mortality problem for bounded languages and linear recurrence sequences,
    International Conference on Reachability Problems, Marseille, September, 2018.
  6. Membership problem in GL(2, Z) extended by singular matrices,
    International Conference on Reachability Problems, London, September, 2017.
  7. Membership Problem in GL(2, Z) extended by Singular Matrices,
    Mathematical Foundations of Computer Science, Aalborg, August, 2017.
  8. Membership problem for 2×2 nonsingular integer matrices,
    Computability in Europe, Turku, June, 2017.
  9. Decidability of the Membership problem for 2×2 integer matrices,
    Symposium of Discrete Algorithms, Barcelona, January, 2017.
  10. Decidability of the Membership problem for 2×2 integer matrices,
    International Conference on Reachability Problems, Aalborg, September, 2016.
  11. Vector reachability problem in SL(2, Z),
    Mathematical Foundations of Computer Science, Krakow, August, 2016.
  12. Decidability of reachability problems in SL(2, Z),
    Logic Colloquium, Leeds, August, 2016.
  13. Degree spectra of structures under Σ1-equivalence,
    Logic Colloquium, Vienna, July, 2014.
  14. Automatic models of first-order theories,
    Invited talk at AMS Spring Western Section Meeting, Honolulu, HI, March, 2012.
  15. Automatic models of first-order theories,
    Workshop on Automata Theory and Applications, Singapore, September, 2011.
  16. Uncountable automatic classes and learning,
    Algorithmic Learning Theory, Porto, October, 2009.
  17. Prime models of finite computable dimension,
    Computability in Europe, Heidelberg, July, 2009.
  18. Finite automata presentable abelian groups,
    Logical Foundations of Computer Science symposium, New York, June, 2007.
  19. Applications of Kolmogorov complexity to computable model theory,
    Workshop on Computability, Randomness and Model Theory, Auckland, 2006.
  20. On Π01-presentations of algebras,
    The 9th Asian Logic Conference, Novosibirsk, August, 2005.
  21. Spectrum of the Atomless Elements Ideal,
    Proceedings of the workshop "Computability and models", Almaty, June 24–28, 2002.