Dr Pavel Semukhin

Journal article

Diekert V, Potapov I, Semukhin P. 2024. Decidability of membership problems for flat rational subsets of GL(2,Q) and singular matrices SIAM Journal on Computing, 53 :1663-1708 DOI Author Url Publisher Url Public Url

Bell PC, Semukhin P. 2023. DECISION QUESTIONS FOR PROBABILISTIC AUTOMATA ON SMALL ALPHABETS Logical Methods in Computer Science, 19 :36:1-36:22-36:1-36:22 DOI Publisher Url Public Url

Bell PC, Potapov I, Semukhin P. 2021. On the Mortality Problem: From Multiplicative Matrix Equations to Linear Recurrence Sequences and Beyond Information and Computation, DOI Author Url Publisher Url Public Url

Semukhin PM, Turetsky D, Fokina EB. 2019. Degree spectra of structures relative to equivalences Algebra i logika, 58 :229-251 DOI Publisher Url

Semukhin PM, Turetsky D, Fokina EB. 2019. Degree Spectra of Structures Relative to Equivalences Algebra and Logic, 58 :158-172 DOI Publisher Url

Potapov I, Semukhin P. 2019. Vector and scalar reachability problems in SL(2,Z) Journal of Computer and System Sciences, 100 :30-43 DOI Publisher Url

Colcombet T, Ouaknine J, Semukhin P, Worrell J. 2019. On Reachability Problems for Low-Dimensional Matrix Semigroups Author Url Publisher Url

Potapov I, Semukhin P. 2018. Preface International Journal of Foundations of Computer Science, 29 :139-141 DOI Publisher Url

Fokina E, Khoussainov B, Semukhin P, Turetsky D. 2016. LINEAR ORDERS REALIZED BY CE EQUIVALENCE RELATIONS JOURNAL OF SYMBOLIC LOGIC, 81 :463-482 DOI Author Url Publisher Url

Potapov I, Semukhin P. 2015. Vector Reachability Problem in $\mathrm{SL}(2,\mathbb{Z})$ DOI Author Url

Samei R, Semukhin P, Yang B, Zilles S. 2014. Algebraic methods proving Sauer's bound for teaching complexity THEORETICAL COMPUTER SCIENCE, 558 :35-50 DOI Author Url Publisher Url

Case J, Jain S, Ong YS, Semukhin P, Stephan F. 2014. Automatic learners with feedback queries JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 80 :806-820 DOI Author Url Publisher Url

Semukhin P, Stephan F. 2013. Automatic models of first order theories ANNALS OF PURE AND APPLIED LOGIC, 164 :837-854 DOI Author Url Publisher Url

Case J, Jain S, Le TD, Ong YS, Semukhin P, Stephan F. 2012. Automatic learning of subclasses of pattern languages INFORMATION AND COMPUTATION, 218 :17-35 DOI Author Url Publisher Url

Jain S, Luo Q, Semukhin P, Stephan F. 2011. Uncountable automatic classes and learning THEORETICAL COMPUTER SCIENCE, 412 :1805-1820 DOI Author Url Publisher Url

Nies A, Semukhin P. 2009. Finite automata presentable abelian groups ANNALS OF PURE AND APPLIED LOGIC, 161 :458-467 DOI Author Url Publisher Url

Semukhin P. 2009. PRIME MODELS OF FINITE COMPUTABLE DIMENSION JOURNAL OF SYMBOLIC LOGIC, 74 :336-348 DOI Author Url Publisher Url

Khoussainov B, Semukhin P, Stephan F. 2007. Applications of Kolmogorov complexity to computable model theory JOURNAL OF SYMBOLIC LOGIC, 72 :1041-1054 DOI Author Url Publisher Url

Hirschfeldt DR, Khoussainov B, Semukhin P. 2006. An uncountably categorical theory whose only computably presentable model is saturated Notre Dame Journal of Formal Logic, 47 :63-71 DOI Publisher Url

Khoussainov B, Slaman T, Semukhin P. 2006. Pi(0)(1)-presentations of algebras ARCHIVE FOR MATHEMATICAL LOGIC, 45 :769-781 DOI Author Url Publisher Url

Semukhin PM. 2005. The degree spectra of definable relations on boolean algebras Siberian Mathematical Journal, 46 :740-750 DOI Publisher Url

Conference publication

Bell PC, Niskanen R, Potapov I, Semukhin P. 2023. On the Identity and Group Problems for Complex Heisenberg Matrices Reachability Problems - 17th International Conference, RP 2023, Nice, France, October 11-13, 2023, Proceedings, Reachability Problems: 17th International Conference, RP 2023 14235 :42-45 DOI Publisher Url Public Url

Semukhin P, Kiefer S, Widdershoven C. 2021. Linear-Time Model Checking Branching Processes LIPIcs : Leibniz International Proceedings in Informatics, 32nd International Conference on Concurrency Theory (CONCUR 2021) 203 :6:1-6:16 DOI Publisher Url Public Url

Bell PC, Semukhin P. 2021. Decision Questions for Probabilistic Automata on Small Alphabets Leibniz International Proceedings in Informatics, LIPIcs, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021) 202 DOI Publisher Url Public Url

Bell PC, Semukhin P. 2020. Decidability of cutpoint isolation for letter-monotonic probabilistic finite automata Konnov I, Kovacs L. The 31st International Conference on Concurrency Theory (CONCUR 2020) Public Url

Bell PC, Semukhin P. 2020. Decidability of cutpoint isolation for probabilistic finite automata on letter-bounded inputs Leibniz International Proceedings in Informatics, LIPIcs, 171 :221-2216 DOI Author Url

Bell PC, Potapov I, Semukhin P. 2019. On the mortality problem: From multiplicative matrix equations to linear recurrence sequences and beyond Leibniz International Proceedings in Informatics, LIPIcs, 138 DOI Author Url

Semukhin P, Colcombet T, Ouaknine J, Worrell J. 2019. On Reachability Problems for Low-Dimensional Matrix Semigroup LIPIcs : Leibniz International Proceedings in Informatics, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) 132 :44:1-44:15 DOI Publisher Url Public Url

Potapov I, Semukhin P. 2017. Membership problem in GL(2, Z) extended by singular matrices Leibniz International Proceedings in Informatics, LIPIcs, 83 DOI

Potapov I, Semukhin P. 2017. Decidability of the Membership Problem for 2 x 2 integer matrices PROCEEDINGS OF THE TWENTY-EIGHTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) :170-186 DOI Author Url Publisher Url

Potapov I, Semukhin P. 2016. Vector reachability problem in SL (2, ℤ) Leibniz International Proceedings in Informatics, LIPIcs, 58 DOI

Samei R, Semukhin P, Yang B, Zilles S. 2014. Sample compression for multi-label concept classes Journal of Machine Learning Research, 35 :371-393

Diekert V, Potapov I, Semukhin P. Decidability of membership problems for flat rational subsets of GL(2, Q) and singular matrices. ISSAC '20: International Symposium on Symbolic and Algebraic Computation, Kalamata, Greece, July 20-23, 2020, DOI Author Url Publisher Url Public Url

preprint

Bell PC, Niskanen R, Potapov I, Semukhin P. 2023. On the Identity and Group Problems for Complex Heisenberg Matrices DOI Author Url

Kiefer S, Semukhin P, Widdershoven C. 2021. Linear-Time Model Checking Branching Processes Author Url

Bell PC, Semukhin P. 2021. Decision Questions for Probabilistic Automata on Small Alphabets Author Url Publisher Url

Bell PC, Semukhin P. 2020. Decidability of cutpoint isolation for probabilistic finite automata on letter-bounded inputs arXiv DOI

Diekert V, Potapov I, Semukhin P. 2019. Decidability of membership problems for flat rational subsets of $\mathrm{GL}(2,\mathbb{Q})$ and singular matrices arXiv DOI

Bell PC, Potapov I, Semukhin P. 2019. On the Mortality Problem: from multiplicative matrix equations to linear recurrence sequences and beyond arXiv DOI

Potapov I, Semukhin P. 2016. Decidability of the Membership Problem for $2\times 2$ integer matrices arXiv DOI

Chapters

Bell PC, Niskanen R, Potapov I, Semukhin P. 2023. On the Identity and Group Problems for Complex Heisenberg Matrices 14235 LNCS :42-55 DOI Publisher Url

Samei R, Semukhin P, Yang B, Zilles S. 2012. Sauer's bound for a notion of teaching complexity 7568 LNAI :96-110 DOI Publisher Url

Case J, Jain S, Ong YS, Semukhin P, Stephan F. 2011. Automatic learners with feedback queries 6735 LNCS :31-40 DOI Publisher Url

Case J, Jain S, Le TD, Ong YS, Semukhin P, Stephan F. 2011. Automatic Learning of Subclasses of Pattern Languages Dediu AH, Inenaga S, MartinVide C. 6638 :192-+ SPRINGER-VERLAG BERLIN 978-3-642-21253-6 DOI Author Url Publisher Url

Jain S, Luo Q, Semukhin P, Stephan F. 2009. Uncountable Automatic Classes and Learning Gavalda R, Lugosi G, Zeugmann T, Zilles S. 5809 :293-+ SPRINGER-VERLAG BERLIN 978-3-642-04413-7 DOI Author Url Publisher Url

Nies A, Semukhin P. 2007. Finite automata presentable abelian groups Artemov SN, Nerode A. 4514 :422-+ SPRINGER-VERLAG BERLIN 978-3-540-72732-3 DOI Author Url Publisher Url