Pavel Semukhin

Lecturer

Department of Computer Science

Liverpool John Moores University

Department of Computer Science

Liverpool John Moores University

Email: | pavel[@]semukhin.name |

P.Semukhin[@]ljmu.ac.uk |

PostScript – PDF

- S. Kiefer, P. Semukhin and C. Widdershoven,
Linear-time model checking branching processes
,
*CONCUR*, 6:1–6:16, 2021.

PDF - P. Bell and P. Semukhin,
Decision questions for probabilistic automata on small alphabets,
*MFCS*, 15:1–15:17, 2021.

PDF - P. Bell and P. Semukhin,
Decidability of cutpoint isolation for probabilistic
finite automata on letter-bounded inputs,
*CONCUR*, 22:1–22:16, 2020.

PDF - 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 - 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 - T. Colcombet, J. Ouaknine, P. Semukhin and J. Worrell, On reachability problems for low-dimensional
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 - E. Fokina, P. Semukhin and D.
Turetsky, Degree spectra of structures
relative to equivalence relations,
*Algebra and Logic*, 58(2): 158–172, 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 multi-label concept
classes,
extended journal version, preprint.

PDF - R. Samei, P. Semukhin, B. Yang and S. Zilles, Sample compression for multi-label concept
classes,
*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*, 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*, 192–203, 2011.

PDF - J. Case, S. Jain, Y. Ong, P. Semukhin and F.
Stephan, Automatic learners
with feedback queries,
*Computability in Europe, CiE*, 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*, 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.

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

- 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. - On reachability problems for low-dimensional
matrix
semigroups,

*International Conference on Reachability Problems*, Brussels, September, 2019. -
On the mortality problem: from multiplicative matrix
equations to
linear recurrence
sequences and beyond,

*Mathematical Foundations of Computer Science*, Aachen, August, 2019. - On reachability problems for low-dimensional
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 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.