Profile photo

Арсений Михайлович Шур

Full Professor

  • Department of Algebra and Fundamental Informatics

Research interests

English language proficiency: С1

  • Combinatorics and Algorithmics of Strings and Related Objects;
  • Combinatorics on words, stringology, related aspects of formal languages, automata, trees, and graphs.

Supervisor’s specific requirements to prospective PhD students:

  • Strong background in discrete mathematics and theoretical computer science: algorithms and complexity, formal languages and automata, graphs, combinatorics and discrete probability
  • Programming skills are appreciated.

Qualifications

Mathematics and Physics, Doctor

11 Mar 2011 → …

30 Dec 2013 → … Full Professor, Full Professor
21 Jul 2004 → … Assistant Professor, Assistant Professor

Research outputs

On minimal critical exponent of balanced sequences

Dvořáková, L., Pelantová, E., Opočenská, D. & Shur, A. M., 24 Jun 2022, In: Theoretical Computer Science. 922, p. 158-169 12 p.

Computing The Maximum Exponent in a Stream

Merkurev, O. & Shur, A. M., Mar 2022, In: Algorithmica. 84, 3, p. 742-756 15 p.

Abelian Repetition Threshold Revisited

Petrova, E. A. & Shur, A. M., 2022, Computer Science – Theory and Applications - 17th International Computer Science Symposium in Russia, CSR 2022, Proceedings. Kulikov, A. S. & Raskhodnikova, S. (eds.). Springer, p. 302-319 18 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 13296 LNCS).

Branching densities of cube-free and square-free words

Petrova, E. A. & Shur, A. M., Apr 2021, In: Algorithms. 14, 4, 19 p., 126.

Transition Property for Cube-Free Words

Petrova, E. A. & Shur, A. M., Apr 2021, In: Theory of Computing Systems. 65, 3, p. 479-496 18 p.

Branching Frequency and Markov Entropy of Repetition-Free Languages

Petrova, E. A. & Shur, A. M., 2021, Developments in Language Theory - 25th International Conference, DLT 2021, Proceedings. Moreira, N. & Reis, R. (eds.). Springer, p. 328-341 14 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 12811 LNCS).

WORDS SEPARATION AND POSITIVE IDENTITIES IN SYMMETRIC GROUPS

Karpova, O. & Shur, A. M., 2021, In: Journal of Automata, Languages and Combinatorics. 26, 1-2, p. 67-89 23 p.

Palindromic k-factorization in pure linear time

Rubinchik, M. & Shur, A. M., 1 Aug 2020, 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020. Esparza, J. & Kral, D. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, MFCS-2020-81. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 170).

String periods in the order-preserving model

Gourdel, G., Kociumaka, T., Radoszewski, J., Rytter, W., Shur, A. & Waleń, T., Feb 2020, In: Information and Computation. 270, 22 p., 104463.

Subword complexity and power avoidance

Shallit, J. & Shur, A., 5 Nov 2019, In: Theoretical Computer Science. 792, p. 96-116 21 p.

Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams

Gawrychowski, P., Merkurev, O., Shur, A. M. & Uznański, P., Sept 2019, In: Algorithmica. 81, 9, p. 3630-3654 25 p.

Searching long repeats in streams

Shur, A. M. & Merkurev, O., 1 Jun 2019, 30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019. Pisanti, N. & Pissis, S. P. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 31. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 128).

Comparison of LZ77-type parsings

Kosolobov, D. & Shur, A. M., 1 Jan 2019, In: Information Processing Letters. 141, p. 25-29 5 p.

Searching Runs in Streams

Merkurev, O. & Shur, A. M., 1 Jan 2019, String Processing and Information Retrieval - 26th International Symposium, SPIRE 2019, Proceedings. Brisaboa, N. R. & Puglisi, S. J. (eds.). Springer Verlag, p. 203-220 18 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 11811 LNCS).

Transition property for cube-free words

Petrova, E. A. & Shur, A. M., 1 Jan 2019, Computer Science – Theory and Applications - 14th International Computer Science Symposium in Russia, CSR 2019, Proceedings. Kucherov, G. & van Bevern, R. (eds.). Springer Verlag, Vol. 11532. p. 311-324 14 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 11532 LNCS).

Square-Free Partial Words with Many Wildcards

Gasnikov, D. & Shur, A. M., 1 Aug 2018, In: International Journal of Foundations of Computer Science. 29, 5, p. 845-860 16 p.

String periods in the order-preserving model

Gourdel, G., Kociumaka, T., Radoszewski, J., Rytter, W., Shur, A. & Walen, T., 2 Feb 2018, 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018. Niedermeier, R. & Vallee, B. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Vol. 96. 16 p. 38. (Leibniz International Proceedings in Informatics; vol. 96).

EERTREE: An efficient data structure for processing palindromes in strings

Rubinchik, M. & Shur, A. M., 1 Feb 2018, In: European Journal of Combinatorics. 68, p. 249-265 17 p.

Математика, механика и компьютерные науки : Подготовка к вступительным экзаменам в магистратуру : задачник: учебное пособие

Ананичев, Д. С., Арестов, В. В., Асанов, М. О., Гальперин, А. Л., Глазырина, П. Ю., Гурьянова, К. Н., Иванов, А. О., Коврижных, А. Ю., Коврижных, О. О., Меленцова, Ю. А., Охезин, С. П., Рекант, М. А., Стихина, Т. К., Шнейдер, А. Е., Шур, А. М. & Коврижных, А. Ю. (ed.), 2018, Екатеринбург: Издательство Уральского университета. 140 p.

Lower bounds on words separation: Are there short identities in transformation semigroups?

Bulatov, A., Karpova, O., Shur, A. M. & Startsev, K., 25 Aug 2017, In: Electronic Journal of Combinatorics. 24, 3, P3.35.

Palindromic length in linear time

Borozdin, K., Kosolobov, D., Rubinchik, M. & Shur, A. M., 1 Jul 2017, 28th Annual Symposium on Combinatorial Pattern Matching, CPM 2017. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Vol. 78. 23

On the size of Lempel-Ziv and Lyndon factorizations

Kärkkäinen, J., Kempa, D., Nakashima, Y., Puglisi, S. J. & Shur, A. M., 1 Mar 2017, 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Vol. 66. 45

Counting palindromes in substrings

Rubinchik, M. & Shur, A. M., 2017, String Processing and Information Retrieval - 24th International Symposium, SPIRE 2017, Proceedings. Springer Verlag, Vol. 10508 LNCS. p. 290-303 14 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 10508 LNCS).

On the tree of binary cube-free words

Petrova, E. A. & Shur, A. M., 2017, Developments in Language Theory - 21st International Conference, DLT 2017, Proceedings. Springer Verlag, Vol. 10396 LNCS. p. 296-307 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 10396 LNCS).

Palindromic rich words and run-length encodings

Guo, C., Shallit, J. & Shur, A. M., 1 Dec 2016, In: Information Processing Letters. 116, 12, p. 735-738 4 p.

Tight tradeoffs for real-time approximation of longest palindromes in streams

Gawrychowski, P., Merkurev, O., Shur, A. M. & Uznański, P., 1 Jun 2016, 27th Annual Symposium on Combinatorial Pattern Matching, CPM 2016. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Vol. 54. p. 18.1-18.13

More on quantum, stochastic, and pseudo stochastic languages with few states

Shur, A. M. & Yakaryılmaz, A., 1 Mar 2016, In: Natural Computing. 15, 1, p. 129-141 13 p.

Special Issue Developments in Language Theory (DLT 2014) Preface

Shur, A., Feb 2016, In: International Journal of Foundations of Computer Science. 27, 2, p. 101-102 2 p.

EERTREE: An efficient data structure for processing palindromes in strings

Rubinchik, M. & Shur, A. M., 2016, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Verlag, Vol. 9538. p. 321-333 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 9538).

Ternary square-free partial words with many wildcards

Gasnikov, D. & Shur, A. M., 2016, Developments in Language Theory - 20th International Conference, DLT 2016, Proceedings. Springer Verlag, Vol. 9840. p. 177-189 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 9840).

The Number of Distinct Subpalindromes in Random Words

Rubinchik, M. & Shur, A. M., 2016, In: Fundamenta Informaticae. 145, 3, p. 371-384 14 p.

Optimal Bounds for the Similarity Density of the Thue-Morse Word with Overlap-Free and 7/3 -Power-Free Infinite Binary Words

Du, C. F., Shallit, J. & Shur, A. M., 1 Dec 2015, In: International Journal of Foundations of Computer Science. 26, 8, p. 1147-1165 19 p.

Searching for Zimin patterns

Rytter, W. & Shur, A. M., 16 Mar 2015, In: Theoretical Computer Science. 571, C, p. 50-57 8 p.

Generating square-free words efficiently

Shur, A. M., 1 Jan 2015, In: Theoretical Computer Science. 601, p. 67-72 6 p.

On the Tree of Ternary Square-Free Words

Petrova, E. A. & Shur, A. M., 2015, COMBINATORICS ON WORDS, WORDS 2015. Manea, F. & Nowotka, D. (eds.). Springer Verlag, Vol. 9304. p. 223-236 14 p. (Lecture Notes in Computer Science; vol. 9304).

Pal(k) is Linear Recognizable Online

Kosolobov, D., Rubinchik, M. & Shur, A. M., 2015, SOFSEM 2015: THEORY AND PRACTICE OF COMPUTER SCIENCE. Italiano, GF., MargariaSteffen, T., Pokorny, J., Quisquater, JJ. & Wattenhofer, R. (eds.). Springer Verlag, Vol. 8939. p. 289-301 13 p. (Lecture Notes in Computer Science; vol. 8939).

Projects

Вновь создаваемый ключевой центр превосходства «Научно-образовательный математический центр» (Проект развития САЕ ИЕНиМ)

Маслова, Н. В., Асанов, М. О., Шеврин, Л. Н., Добросердова, А. Б., Шушпанов, М. П., Попович, А. Л., Верников, Б. М., Гусев, С. В., Волков, М. В., Шур, А. М., Осипов, А. В., Бабенко, А. Г., Гомоюнов, М. И., Юферева, О. О., Махнев, А. А., Хачай, О. Ю., Акопян, Р. Р., Верников, Б. М., Авербух, Ю. В., Баранский, В. А., Белоусов, И. Н., Зенков, В. И., Зиновьева, М. Р., Осипов, А. В., Паюченко, Н. С. & Сеньчонок, Т. А.

19/07/2017 → …

Математические аспекты фундаментальной информатики

Волков, М. В., Ананичев, Д. С., Берлинков, М. В., Булатов, А. А., Гамзова, Ю. В., Глазырин, Н. Ю., Гусев, В. В., Косолобов, Д. А., Крохин, А. А., Мартюгин, П. В., Масленникова, М. И., Мелентьев, А. А., Михайлова, И. А., Петрова, Е. А., Плющенко, А. Н., Прибавкина, Е. В., Рубинчик, М. В., Скворцов, Е. С., Хворост, А. А., Шур, А. М., Пупырев, С. Н., Незнахина, Е. Д., Шушпанов, М. П., Гейн, А. А., Прохорова, М. Ф., Ли, Э. В. Х., Осипов, В. В., Шабана, Х. М. Д., Браславский, П. И., Гейн, А. Г., Кобякова, Н. Н. & Форгани, М.

03/12/2013 → …

ID: 61788