Pavel Semukhin

Research Associate

Department of Computer Science

University of Oxford

Department of Computer Science

University of Oxford

Email: | pavel _at_ semukhin.name |

pavel.semukhin _at_ cs.ox.ac.uk |

PostScript – PDF

- 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 - 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 - I. Potapov and P. Semukhin, Vector
and Scalar
reachability problem in SL(2, Z), submitted to
*J. Computer and System Sciences*.

PDF - I. Potapov and P. Semukhin, Vector
reachability problem in SL(2, Z),
*Mathematical foundations of Computer Science*, MFCS, 84:1–84:14, 2016.

PDF - 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 - R. Samei, P. Semukhin, B. Yang and S. Zilles, Sample Compression for Multi-label Concept
Classes,
extended journal version, submitted for publication.

PDF - 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 - 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 - 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 - 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 - P. Semukhin and F. Stephan, Automatic
models of first-order theories,
*Annals of Pure and Applied Logic*, 164(9): 837–854, 2013.

PDF - 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 - 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 - 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 - P. Semukhin, Prime
models
of finite computable dimension,
*J. Symbolic Logic*, 74(1): 336–348, 2009.

PDF - A. Nies, P. Semukhin, Finite
automata presentable abelian groups,
*Annals of Pure and Applied Logic*, 161(3): 458–467, 2009.

PDF - B. Khoussainov, P. Semukhin, F. Stephan, Applications of
Kolmogorov complexity to computable model theory,
*J. Symbolic Logic*, 72(3): 1041–1054, 2007.

PDF - A. Nies, P. Semukhin, Finite
automata presentable abelian groups,
*Proc. of Logical Foundations of Computer Science*, LFCS, 422–436, 2007.

PDF - B. Khoussainov, T. Slaman, P. Semukhin, Π
^{0}_{1}-presentations of algebras,*Arch. Math. Logic*, 45(6): 769–781, 2006.

PDF - 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 - 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) - 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.

- Membership problem for 2×2 integer
matrices,

*Oxford University CS Departmental Seminar*, Oxford, July, 2017. - Membership problem for 2×2 nonsingular integer
matrices,

*Computability in Europe*, Turku, June, 2017. - Decidability of the Membership problem for 2×2 integer
matrices,

*Symposium of Discrete Algorithms*, Barcelona, January, 2017. - Decidability of the Membership problem for 2×2 integer
matrices,

*Reachability Problems*, Aalborg, September, 2016. - Vector reachability problem in SL(2, Z),

*Mathematical Foundations of Computer Science*, Krakow, August, 2016. - Decidability of reachability problems in SL(2, Z),

*Logic Colloquium*, Leeds, August, 2016. - Degree spectra of structures under Σ
_{1}-equivalence,

*Logic Colloquium*, Vienna, July, 2014. - Automatic models of first-order theories,

Invited talk at*AMS Spring Western Section Meeting*, Honolulu, HI, March, 2012. - Automatic models of first-order theories,

Workshop on*Automata Theory and Applications*, Singapore, September, 2011. - Uncountable automatic classes and learning,

*Algorithmic Learning Theory*, Porto, October, 2009. - Prime models of finite computable dimension,

*Computability in Europe*, Heidelberg, July, 2009. - Finite automata presentable abelian groups,

*Logical Foundations of Computer Science symposium*, New York, June, 2007. - Applications of Kolmogorov complexity to
computable model
theory,

*Workshop on Computability, Randomness and Model Theory*, Auckland, 2006. - On Π
^{0}_{1}-presentations of algebras,

*The 9th Asian Logic Conference*, Novosibirsk, August, 2005. - Spectrum of the Atomless Elements Ideal,

*Proceedings of the workshop "Computability and models"*, Almaty, June 24–28, 2002.