CV and Publications

Последнее изменение: 22/08/2022 08:46:34

Curriculum Vitae

Publication List

Refereed Conference Proceedings

  1. E. A. Petrova, A. M. Shur. Abelian Repetition Threshold Revisited. Proc. CSR 2022: Springer, 2022. 302--319. (LNCS Vol. 13296)
  2. E. A. Petrova, A. M. Shur. Branching frequency and Markov entropy of repetition-free languages. Proc. DLT 2021: Springer, 2021.328-341. (LNCS Vol. 12811)
  3. M. Rubinchik, A. M. Shur. Palindromic k-factorization in pure linear time. Proc. MFCS 2020: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2020. 81:1-81:14. (LIPIcs Vol. 170)
  4. E. A. Petrova, A. M. Shur. Transition property for cube-free words. Proc. CSR 2019: Springer, 2019. 311-324. (LNCS Vol. 11532)
  5. O. Merkurev, A. M. Shur. Searching Runs in Streams. SPIRE 2019: Springer, 2019. 203-220. (LNCS Vol. 11811)
  6. E. A. Petrova, A. M. Shur. Transition Property for Cube-Free Words. CSR 2019: Springer, 2019. 311-324. (LNCS Vol. 11532)
  7. O. Merkurev, A. M. Shur. Searching Long Repeats in Streams. CPM 2019: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2019. 31:1-31:14 (LIPIcs Vol. 128)
  8. G. Gourdel, T. Kociumaka, J. Radoszewski, W. Rytter, A. M. Shur, T. Walen. String Periods in the Order-Preserving Model. STACS 2018: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. 38:1-38:16 (LIPIcs Vol. 96)
  9. M. Rubinchik, A. M. Shur. Counting Palindromes in Substrings. SPIRE 2017: Springer, 2017. 290-303. (LNCS Vol. 10508)
  10. E. A. Petrova, A. M. Shur. On the Tree of Binary Cube-Free Words. DLT 2017: Springer, 2017. 296-307. (LNCS Vol. 10396)
  11. K. Borozdin, D. Kosolobov, M. Rubinchik, A. M. Shur. Palindromic Length in Linear Time. CPM 2017: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. 23:1-23:12 (LIPIcs Vol. 78)
  12. J. Kärkkäinen, D. Kempa, Y. Nakashima, S. J. Puglisi, A. M. Shur. On the Size of Lempel-Ziv and Lyndon Factorizations. STACS 2017: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. 45:1-45:13 (LIPIcs Vol. 66)
  13. D. Gasnikov, A. M. Shur. Ternary square-free partial words with many wildcards. Proc. DLT 2016: Springer, 2016. 177-189 (LNCS Vol. 9840)
  14. P. Gawrychowski, O. Merkurev, A. Shur, and P. Uznanski. Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams. Proc. CPM 2016: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. 18:1-18:13. (LIPIcs Vol. 54)
  15. M. Rubinchik, A. M. Shur. EERTREE: An efficient data structure for processing palindromes in strings. Proc. IWOCA 2015: Springer, 2016. 321-333. (LNCS Vol. 9538)
  16. E. A. Petrova, A. M. Shur. On the Tree of Ternary Square-Free Words. Proc. WORDS 2015: Springer, 2015. 223-236. (LNCS Vol. 9304)
  17. D. Kosolobov, M. Rubinchik, A. M. Shur. Palk is linear recognizable online. Proc. SOFSEM 2015: Springer, 2015. 289-301. (LNCS Vol. 8939)
  18. M. Rubinchik, A. M. Shur. On the number of distinct subpalindromes in words. Proc. RuFiDiM 2014: Petrozavodsk, Inst. Appl. Math. Research, 2014. 96-98
  19. A. M. Shur, A. Yakaryilmaz. Quantum, stochastic, and pseudo stochastic languages with few states. Proc. UCNC 2014: Springer, 2014. 327-339. (LNCS Vol. 8553)
  20. D. Kosolobov, M. Rubinchik, A. M. Shur. Finding distinct subpalindromes online. Proc. PSC 2013: Prague, Czech Technical University, 2013. 63-69
  21. A. M. Shur. Languages with a finite antidictionary: growth-preserving transformations and available orders of growth. Proc. DLT 2013: Springer, 2013. 445-457. (LNCS Vol. 7907)
  22. L. A. Idiatulina, A. M. Shur. Periodic partial words and random bipartite graphs. Proc. RuFiDiM 2012: Turku, TUCS Lecture Notes 17 (2012). 25-28
  23. A. V. Samsonov, A. M. Shur. Binary patterns in binary cube-free words: avoidability and growth. Proc. 14th Mons Days of Theoretical Computer Science: Louvain-la-Nueve, Catholic Univ. Louvain, 2012. 7pp
  24. I. N. Tunev, A. M. Shur. On two stronger versions of Dejean's conjecture. Proc. MFCS 2012: Springer, 2012. 800-812. (LNCS Vol. 7464)
  25. E. A. Petrova, A. M. Shur. Constructing premaximal ternary square-free words of any level. Proc. MFCS 2012: Springer, 2012. 752-763. (LNCS Vol. 7464)
  26. N. Rampersad, J. Shallit, A. Shur. Fife's theorem for (7/3)-powers. Proc. WORDS 2011. EPTCS Vol.63 (2011), 189-198
  27. I. A. Gorbunova, A. M. Shur. On Pansiot words avoiding 3-repetitions. Proc. WORDS 2011. EPTCS Vol.63 (2011), 138-146
  28. E. A. Petrova, A. M. Shur. Constructing premaximal binary cube-free words of any level. WORDS 2011. EPTCS Vol.63 (2011), 168-178
  29. A. M. Shur. Growth properties of power-free languages. Proc. DLT 2011: Springer, 2011. 28-43. (LNCS Vol. 6795)
  30. A. N. Plyushchenko, A. M. Shur. On Brzozovski's conjecture for the free Burnside semigroup satisfying x^2 = x^3. Proc. DLT 2011: Springer, 2011. 362-373. (LNCS Vol. 6795).
  31. K. M. Likhomanov, A. M. Shur. Two combinatorial criteria for BWT images. Proc. CSR 2011: Springer, 2011. 385-396. (LNCS Vol. 6651)
  32. A. V. Samsonov, A. M. Shur. On Abelian repetition threshold. Proc. 13th Mons Days of Theoretical Computer Science: Amiens, Univ. de Picardie Jules Verne, 2010. 1-11.
  33. A. M. Shur. On the existence of minimal β-powers. Proc. DLT 2010: Springer, 2010. 411-422. (LNCS Vol. 6224)
  34. A. M. Shur. Growth of power-free languages over large alphabets. Proc. CSR 2010: Springer, 2010. 350-361. (LNCS Vol. 6072)
  35. A. M. Shur. Two-sided bounds for the growth rates of power-free languages. Proc. DLT 2009: Springer, 2009. 466-477. (LNCS Vol. 5583)
  36. A. M. Shur. Combinatorial complexity of regular languages. Proc. CSR 2008: Springer, 2008. 289-301. (LNCS Vol. 5010)
  37. A. M. Shur, I. A. Gorbunova. On the growth rates of complexity of threshold languages. Proc. 12th Mons Days of Theoretical Computer Science: Mons, Univ. de Mons-Hainaut, 2008. 10pp
  38. A. N. Plyushchenko, A. M. Shur. Almost overlap-free words and the word problem for the free Burnside semigroup satisfying x^2 = x^3. Proc. WORDS 2007: Marseille, Institut de Mathematiques de Luminy, 2007. 245-253
  39. A. M. Shur. Factorial languages of low combinatorial complexity. Proc. DLT 2006: Springer, 2006. 397-407. (LNCS Vol. 4036)
  40. A. M. Shur. Comparing complexity functions of a language and its extendable part. Proc. 11th Mons Days of Theoretical Computer Science: Rennes, IRISA-Rennes, 2006. 323-327
  41. A. M. Shur, Y. V. Gamzova. Periods' interaction property for partial words. Proc. WORDS 2003: Turku, TUCS Gen. Publ. 27 (2003). 75-82
  42. A. M. Shur, Y. V. Konovalova. On the periods of partial words. Proc. MFCS 2001: Springer, 2001. 657-665. (LNCS Vol. 2136)
  43. E. V. Sukhanov, A. M. Shur. Galois connection in avoidability theory. In: S. Kublanovsky, A. Mikhalev, J. Ponizovsky, P. Higgins eds., Semigroups with applications, including semigroup rings. International conference in honour of E.S. Lyapin, St.-Petersburg, 1995. St.-Petersburg: Severny Ochag, 1999, 397-400.

Refereed Journal Articles

  1. L. Dvorakova, E. Pelantova, D. Opocenska, A. M. Shur. On minimal critical exponent of balanced sequences. Theoretical Computer Science Vol. 922 (2022), 158--169
  2. O. Merkurev, A. M. Shur. Computing the maximum exponent in a stream. Algorithmica Vol. 84(3) (2022), 742-756
  3. O. Karpova, A. M. Shur. Words separation and positive identities in symmetric groups. J. Autom. Lang. Comb. Vol. 26(1-2) (2021), 67-89
  4. E. A. Petrova, A. M. Shur. Transition property for cube-free words. Theory Comput. Syst. Vol. 65(3) (2021), 479-496
  5. E. A. Petrova, A. M. Shur. Branching densities of cube-free and square-free words. Algorithms Vol. 14(4) (2021), 126
  6. G. Gourdel, T. Kociumaka, J. Radoszewski, W. Rytter, A. M. Shur, T. Walen. String periods in the order-preserving model. Information and Computation Vol. 270 (2020), 104463
  7. J. O. Shallit, A. M. Shur. Subword complexity and power avoidance. Theoretical Computer Science Vol. 792 (2019), 96-116
  8. P. Gawrychowski, O. Merkurev, A. Shur, and P. Uznanski. Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams. Algorithmica Vol. 81(9) (2019), 3630-3654
  9. D. Kosolobov, A. M. Shur. Comparison of LZ77-type parsings. Inform. Process. Lett. Vol. 141 (2019), 25-29
  10. D. Gasnikov, A. M. Shur. Square-Free Partial Words with Many Wildcards. Internat. J. Foundat. Comput. Sci. Vol. 29(5) (2018), 845-860
  11. M. Rubinchik, A. M. Shur. EERTREE: An efficient data structure for processing palindromes in strings. European J. Combinatorics Vol. 68 (2018), 249-265
  12. A. A. Bulatov, O. Karpova, A. M. Shur, K. Startsev. Lower bounds on words separation: are there short identities in transformation semigroups? Electronic J. Combinatorics Vol. 24(3) (2017), P3.35
  13. C. Guo, J. Shallit, A. M. Shur. Palindromic rich words and run-length encodings. Inform. Process. Lett. Vol. 116(12) (2016), 735-738
  14. M. Rubinchik, A. M. Shur. The number of distinct subpalindromes in random words. Fundamenta Informaticae Vol. 145(3) (2016), 371-384
  15. A. M. Shur, A. Yakaryilmaz. More on quantum, stochastic, and pseudo stochastic languages with few states. Natural Computing Vol. 15(1) (2016), 129-141
  16. C. F. Du, J. Shallit, A. M. Shur. Optimal bounds for the similarity density of the Thue-Morse word with overlap-free and 7/3-power-free infinite binary words. Internat. J. Foundat. Comput. Sci. Vol. 26(8) (2015), 1147-1166
  17. A. M. Shur. Generating square-free words efficiently. Theoretical Computer Science Vol. 601 (2015), 67-72
  18. W. Rytter, A. M. Shur. Searching for Zimin patterns. Theoretical Computer Science Vol. 571 (2015), 50-57
  19. A. M. Shur. Languages with a finite antidictionary: some growth questions. Internat J. Foundat. Comput. Sci. Vol. 25(8) (2014), 937-954
  20. R. Mercaş, P. Ochem, A. V. Samsonov, A. M. Shur. Binary patterns in binary cube-free words: Avoidability and growth. RAIRO Theor. Inf. and Applic. Vol. 48(4) (2014), 369-389.
  21. L. A. Idiatulina, A. M. Shur. Periodic partial words and random bipartite graphs. Fundamenta Informaticae Vol. 132(1) (2014), 15-31
  22. A. M. Shur. Growth of power-free languages over large alphabets. Theory of Computing Systems Vol. 54(2) (2014), 224-243
  23. I. A. Gorbunova, A. M. Shur. On Pansiot words avoiding 3-repetitions. Internat. J. Foundat. Comput. Sci. Vol. 23(8) (2012), 1583-1594.
  24. E. A. Petrova, A. M. Shur. Constructing premaximal binary cube-free words of any level. Internat. J. Foundat. Comput. Sci. Vol. 23(8) (2012), 1595-1610
  25. A. M. Shur. Growth properties of power-free languages. Computer Science Review Vol. 6(5-6) (2012), 187-208
  26. A. M. Shur. Deciding context equivalence of binary overlap-free words in linear time. Semigroup Forum Vol. 84(3) (2012), 447-471
  27. A. V. Samsonov, A. M. Shur. On Abelian repetition threshold. RAIRO Inform. Theor. Appl. Vol. 46 (2012), 147-163
  28. A. M. Shur. On the existence of minimal β-powers. Internat. J. Foundat. Comput. Sci. Vol. 22(7) (2011), 1683-1696.
  29. A. N. Plyushchenko, A. M. Shur. Almost overlap-free words and the word problem for the free Burnside semigroup satisfying $x^2=x^3$. Int. J. Algebra and Comput. Vol. 21(6) (2011), 973–1006
  30. A. M. Shur. On ternary square-free circular words. Electronic J. Combinatorics Vol. 17(1) (2010), R140
  31. A. M. Shur. Growth rates of complexity of power-free languages. Theor. Comput. Sci. Vol. 411 (2010), 3209-3223
  32. A. M. Shur. Growth of power-free languages: Numerical and asymptotic bounds. Dokl. Math. Vol. 81(3) (2010), 406–409
  33. A. M. Shur. Calculating parameters and behaviour types of combinatorial complexity for regular languages. Proc. Inst. Mathematics and Mechanics of Ural Branch of Russian Academy of Sciences Vol. 16(2) (2010), 270-287. In Russian, with English abstract. PDF
  34. A. M. Shur, I. A. Gorbunova. On the growth rates of complexity of threshold languages. RAIRO Inform. Theor. Appl. Vol. 44 (2010), 175-192
  35. A. M. Shur. Languages with finite antidictionaries: growth index and properties of automata. Proc. Ural State Univ. Vol. 74 (2010), 220-245. In Russian, with English abstract. PDF
  36. A. M. Shur. Growth rates of power-free languages. Russian Mathematics (Iz VUZ), Vol. 53(9) (2009), 73–78.
  37. A. M. Shur. Polynomial languages with finite antidictionaries. RAIRO Theor. Inform. and Appl., Vol. 43(2) (2009), 269-280
  38. A. M. Shur. On intermediate factorial languages. Discrete Applied Mathematics Vol. 157(7) (2009), 1669-1675
  39. A. M. Shur. Comparing complexity functions of a language and its extendable part. RAIRO Theor. Inf. Appl. Vol. 42 (2008), 647-655
  40. A. M. Shur. Rational approximations of polynomial factorial languages. Int. J. Foundat. Comput. Sci., Vol. 18 (2007), 655-665
  41. A. M. Shur. Combinatorial complexity of rational languages. Diskretn. Anal. Issled. Oper. Ser. 1. 2005. Vol. 12(2). 78-99. In Russian. PDF
  42. A. M. Shur, Y. V. Gamzova. Partial words and the interaction property of periods. Izv. Math. Vol. 68(2) (2004), 405-428
  43. A. M. Shur. The structure of the set of cube-free Z-words over a two-letter alphabet. Izv. Math. Vol. 64(4) (2000), 847-871
  44. E. V. Sukhanov, A. M. Shur. A class of formal languages. Algebra and Logic. Vol. 37(4) (1998), 270–277
  45. A. M. Shur. Syntactic semigroups of avoidable languages. Siberian Math. J. Vol. 39(3) (1998), 594-610
  46. A. M. Shur. Binary avoidability and Thue-Morse words. Dokl. Math. Vol. 53(3) (1996), 405-406
  47. A. M. Shur. Overlap-free words and Thue-Morse sequences. Int. J. Algebra and Comput. Vol. 6(3) (1996), 353-367
  48. A. M. Shur. Binary words avoided by the Thue-Morse sequence. Semigroup Forum. Vol. 53(2) (1996), 212-219

Books and Chapters

  1. (with B. Vernikov) Graphs and Graph Algorithms. Textbook for students in applied informatics. Ekaterinburg Academy of Modern Art, Ekaterinburg, 2012. 160pp. ISBN 978-5-904440-21-3.
  2. (with A. Zamyatin) Languages, Grammars, Acceptors. Textbook for students of mathematical departments. Ural University, Ekaterinburg, 2007. 248pp. ISBN 978-5-7996-0273-0.
  3. Combinatorics of Words. Textbook for students of mathematical departments. Ural University, Ekaterinburg, 2003. 96pp. ISBN 978-5-7996-0168-8.
  4. (with E. Sukhanov) Problems of entrance exams in mathematics at Ural State University. In: Problems of entrance exams in mathematics at higher education institutions of Ekaterinburg. Ekaterinburg, 1997. 5-14.
  5. (with V. Rasin, D. Ananichev, A. Gein, M. Volkov, S. Homenko, and V. Ivanova) Entrance exams in mathematics at Ural State University. Ural University, Ekaterinburg, 2003. 44pp.

Edited Volumes

  1. Special Issue Developments in Language Theory (DLT 2014). Guest Editor: Arseny Shur. International Journal of Foundations of Computer Science Vol. 27(2) (2016)
  2. Arseny M. Shur, Mikhail V. Volkov (Eds.): Developments in Language Theory - 18th International Conference, DLT 2014, Ekaterinburg, Russia, August 26-29, 2014. Proceedings. Springer, 2014. (LNCS Vol. 8633). ISBN 978-3-319-09697-1
  3. Andrei A. Bulatov, Arseny M. Shur (Eds.): Computer Science - Theory and Applications - 8th International Computer Science Symposium in Russia, CSR 2013, Ekaterinburg, Russia, June 25-29, 2013. Proceedings. Berlin: Springer, 2013. (LNCS Vol. 7913). ISBN 978-3-642-38535-3
  4. Alexander S. Kulikov, Arseny M. Shur (Eds.): Algorithms & Complexity. Abstracts of Reports and Other Materials of the 6th School "Computer Science Days in Ekaterinburg", Ekaterinburg, Russia, June 29 - July 01, 2013. ISBN 978-5-7996-0922-1