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:
 P. Bell, I. Potapov and P. Semukhin, On
the mortality problem: from multiplicative matrix equations to linear
recurrence sequences and beyond,
accepted to MFCS, 2019.
PDF
 T. Colcombet, J. Ouaknine, P. Semukhin and J. Worrell, On reachability problems for lowdimensional
matrix semigroups, ICALP,
44:1–44:15, 2019.
PDF
 I. Potapov and P. Semukhin, Vector
and Scalar
reachability problem in SL(2, Z), J.
Computer and System Sciences, 100: 30–43, 2019.
PDF
 I. Potapov and P. Semukhin, Membership
problem in GL(2, Z) extended by singular matrices, MFCS,
44:1–44:13, 2017.
PDF
 I. Potapov and P. Semukhin, Decidability
of the membership problem for 2×2 integer matrices, SODA,
170–186, 2017.
PDF –
Slides
 I. Potapov and P. Semukhin, Vector
reachability problem in SL(2, Z), 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 Multilabel Concept
Classes,
extended journal version, preprint.
PDF
 R. Samei, P. Semukhin, B. Yang and S. Zilles, Sample Compression for Multilabel 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, J. 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 firstorder 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.
Editorial works:
 I. Potapov and P. Semukhin, Special
issue: Developments in Language Theory (DLT 2015),
Int. J. Foundations of Computer Science, 29(2), 2018.
Conference talks:

On reachability problems for lowdimensional matrix semigroups,
International Colloquium on Automata, Languages and
Programming, Patras, July, 2019.
 Mortality problem for bounded languages and linear
recurrence sequences,
International Conference on Reachability Problems,
Marseille,
September, 2018.
 Membership problem in GL(2, Z) extended by singular
matrices,
International Conference on Reachability Problems,
London,
September, 2017.
 Membership Problem in GL(2, Z) extended by Singular
Matrices,
Mathematical Foundations of Computer Science,
Aalborg, August, 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,
International Conference on 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 firstorder theories,
Invited talk at AMS Spring Western Section Meeting,
Honolulu, HI, March, 2012.
 Automatic models of firstorder 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.