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:
- 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, Π01-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.
Conference talks:
- 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 Π01-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.