Шур Арсений Михайлович: Список публикаций

Последнее изменение: 20/05/2020 08:26:52

Список публикаций

Статьи в трудах конференций

  1. O. Merkurev, A. M. Shur. Searching Runs in Streams. SPIRE 2019: Springer, 2019. 203-220. (LNCS Vol. 11811)
  2. E. A. Petrova, A. M. Shur. Transition Property for Cube-Free Words. CSR 2019: Springer, 2019. 311-324. (LNCS Vol. 11532)
  3. 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)
  4. 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)
  5. M. Rubinchik, A. M. Shur. Counting Palindromes in Substrings. SPIRE 2017: Springer, 2017. 290-303. (LNCS Vol. 10508)
  6. E. A. Petrova, A. M. Shur. On the Tree of Binary Cube-Free Words. DLT 2017: Springer, 2017. 296-307. (LNCS Vol. 10396)
  7. 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)
  8. 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)
  9. D. Gasnikov, A. M. Shur. Ternary square-free partial words with many wildcards. Proc. DLT 2016: Springer, 2016. 177-189 (LNCS Vol. 9840)
  10. 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)
  11. 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)
  12. E. A. Petrova, A. M. Shur. On the Tree of Ternary Square-Free Words. Proc. WORDS 2015: Springer, 2015. 223-236. (LNCS Vol. 9304)
  13. D. Kosolobov, M. Rubinchik, A. M. Shur. Palk is linear recognizable online. Proc. SOFSEM 2015: Springer, 2015. 289-301. (LNCS Vol. 8939)
  14. M. Rubinchik, A. M. Shur. On the number of distinct subpalindromes in words. Proc. RuFiDiM 2014: Petrozavodsk, Inst. Appl. Math. Research, 2014. 96-98
  15. A. M. Shur, A. Yakaryilmaz. Quantum, stochastic, and pseudo stochastic languages with few states. Proc. UCNC 2014: Springer, 2014. 327-339. (LNCS Vol. 8553)
  16. D. Kosolobov, M. Rubinchik, A. M. Shur. Finding distinct subpalindromes online. Proc. PSC 2013: Prague, Czech Technical University, 2013. 63-69
  17. 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)
  18. L. A. Idiatulina, A. M. Shur. Periodic partial words and random bipartite graphs. Proc. RuFiDiM 2012: Turku, TUCS Lecture Notes 17 (2012). 25-28
  19. 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
  20. I. N. Tunev, A. M. Shur. On two stronger versions of Dejean's conjecture. Proc. MFCS 2012: Springer, 2012. 800-812. (LNCS Vol. 7464)
  21. 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)
  22. N. Rampersad, J. Shallit, A. Shur. Fife's theorem for (7/3)-powers. Proc. WORDS 2011. EPTCS Vol.63 (2011), 189-198
  23. I. A. Gorbunova, A. M. Shur. On Pansiot words avoiding 3-repetitions. Proc. WORDS 2011. EPTCS Vol.63 (2011), 138-146
  24. E. A. Petrova, A. M. Shur. Constructing premaximal binary cube-free words of any level. WORDS 2011. EPTCS Vol.63 (2011), 168-178
  25. A. M. Shur. Growth properties of power-free languages. Proc. DLT 2011: Springer, 2011. 28-43. (LNCS Vol. 6795)
  26. 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).
  27. K. M. Likhomanov, A. M. Shur. Two combinatorial criteria for BWT images. Proc. CSR 2011: Springer, 2011. 385-396. (LNCS Vol. 6651)
  28. 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.
  29. A. M. Shur. On the existence of minimal β-powers. Proc. DLT 2010: Springer, 2010. 411-422. (LNCS Vol. 6224)
  30. A. M. Shur. Growth of power-free languages over large alphabets. Proc. CSR 2010: Springer, 2010. 350-361. (LNCS Vol. 6072)
  31. A. M. Shur. Two-sided bounds for the growth rates of power-free languages. Proc. DLT 2009: Springer, 2009. 466-477. (LNCS Vol. 5583)
  32. A. M. Shur. Combinatorial complexity of regular languages. Proc. CSR 2008: Springer, 2008. 289-301. (LNCS Vol. 5010)
  33. 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
  34. 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
  35. A. M. Shur. Factorial languages of low combinatorial complexity. Proc. DLT 2006: Springer, 2006. 397-407. (LNCS Vol. 4036)
  36. 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
  37. A. M. Shur, Y. V. Gamzova. Periods' interaction property for partial words. Proc. WORDS 2003: Turku, TUCS Gen. Publ. 27 (2003). 75-82
  38. A. M. Shur, Y. V. Konovalova. On the periods of partial words. Proc. MFCS 2001: Springer, 2001. 657-665. (LNCS Vol. 2136)
  39. 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.

Журнальные статьи

  1. 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
  2. J. O. Shallit, A. M. Shur. Subword complexity and power avoidance. Theoretical Computer Science Vol. 792 (2019), 96-116
  3. 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
  4. D. Kosolobov, A. M. Shur. Comparison of LZ77-type parsings. Inform. Process. Lett. Vol. 141 (2019), 25-29
  5. D. Gasnikov, A. M. Shur. Square-Free Partial Words with Many Wildcards. Internat. J. Foundat. Comput. Sci. Vol. 29(5) (2018), 845-860
  6. M. Rubinchik, A. M. Shur. EERTREE: An efficient data structure for processing palindromes in strings. European J. Combinatorics Vol. 68 (2018), 249-265
  7. 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
  8. C. Guo, J. Shallit, A. M. Shur. Palindromic rich words and run-length encodings. Inform. Process. Lett. Vol. 116(12) (2016), 735-738
  9. M. Rubinchik, A. M. Shur. The number of distinct subpalindromes in random words. Fundamenta Informaticae Vol. 145(3) (2016), 371-384
  10. A. M. Shur, A. Yakaryilmaz. More on quantum, stochastic, and pseudo stochastic languages with few states. Natural Computing Vol. 15(1) (2016), 129-141
  11. 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
  12. A. M. Shur. Generating square-free words efficiently. Theoretical Computer Science Vol. 601 (2015), 67-72
  13. W. Rytter, A. M. Shur. Searching for Zimin patterns. Theoretical Computer Science Vol. 571 (2015), 50-57
  14. A. M. Shur. Languages with a finite antidictionary: some growth questions. Internat J. Foundat. Comput. Sci. Vol. 25(8) (2014), 937-954
  15. 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.
  16. L. A. Idiatulina, A. M. Shur. Periodic partial words and random bipartite graphs. Fundamenta Informaticae Vol. 132(1) (2014), 15-31
  17. A. M. Shur. Growth of power-free languages over large alphabets. Theory of Computing Systems Vol. 54(2) (2014), 224-243
  18. I. A. Gorbunova, A. M. Shur. On Pansiot words avoiding 3-repetitions. Internat. J. Foundat. Comput. Sci. Vol. 23(8) (2012), 1583-1594.
  19. 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
  20. A. M. Shur. Growth properties of power-free languages. Computer Science Review Vol. 6(5-6) (2012), 187-208
  21. A. M. Shur. Deciding context equivalence of binary overlap-free words in linear time. Semigroup Forum Vol. 84(3) (2012), 447-471
  22. A. V. Samsonov, A. M. Shur. On Abelian repetition threshold. RAIRO Inform. Theor. Appl. Vol. 46 (2012), 147-163
  23. A. M. Shur. On the existence of minimal β-powers. Internat. J. Foundat. Comput. Sci. Vol. 22(7) (2011), 1683-1696.
  24. 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
  25. A. M. Shur. On ternary square-free circular words. Electronic J. Combinatorics Vol. 17(1) (2010), R140
  26. A. M. Shur. Growth rates of complexity of power-free languages. Theor. Comput. Sci. Vol. 411 (2010), 3209-3223
  27. A. M. Shur. Growth of power-free languages: Numerical and asymptotic bounds. Dokl. Math. Vol. 81(3) (2010), 406–409
  28. 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
  29. A. M. Shur, I. A. Gorbunova. On the growth rates of complexity of threshold languages. RAIRO Inform. Theor. Appl. Vol. 44 (2010), 175-192
  30. 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
  31. A. M. Shur. Growth rates of power-free languages. Russian Mathematics (Iz VUZ), Vol. 53(9) (2009), 73–78.
  32. A. M. Shur. Polynomial languages with finite antidictionaries. RAIRO Theor. Inform. and Appl., Vol. 43(2) (2009), 269-280
  33. A. M. Shur. On intermediate factorial languages. Discrete Applied Mathematics Vol. 157(7) (2009), 1669-1675
  34. A. M. Shur. Comparing complexity functions of a language and its extendable part. RAIRO Theor. Inf. Appl. Vol. 42 (2008), 647-655
  35. A. M. Shur. Rational approximations of polynomial factorial languages. Int. J. Foundat. Comput. Sci., Vol. 18 (2007), 655-665
  36. A. M. Shur. Combinatorial complexity of rational languages. Diskretn. Anal. Issled. Oper. Ser. 1. 2005. Vol. 12(2). 78-99. In Russian. PDF
  37. A. M. Shur, Y. V. Gamzova. Partial words and the interaction property of periods. Izv. Math. Vol. 68(2) (2004), 405-428
  38. 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
  39. E. V. Sukhanov, A. M. Shur. A class of formal languages. Algebra and Logic. Vol. 37(4) (1998), 270–277
  40. A. M. Shur. Syntactic semigroups of avoidable languages. Siberian Math. J. Vol. 39(3) (1998), 594-610
  41. A. M. Shur. Binary avoidability and Thue-Morse words. Dokl. Math. Vol. 53(3) (1996), 405-406
  42. A. M. Shur. Overlap-free words and Thue-Morse sequences. Int. J. Algebra and Comput. Vol. 6(3) (1996), 353-367
  43. A. M. Shur. Binary words avoided by the Thue-Morse sequence. Semigroup Forum. Vol. 53(2) (1996), 212-219

Книги и главы книг

  1. (с Б.М. Верниковым) Графы и алгоритмы на них. Учебное пособие для студентов направления "Прикладная информатика". Екатеринбургская академия современного искусства, Екатеринбург, 2012. 160 с. ISBN 978-5-904440-21-3.
  2. (с А.П. Замятиным) Языки, грамматики, распознаватели. Учебное пособие для студентов математических специальностей. Изд-во Уральского университета, Екатеринбург, 2007. 248с. Гриф: УМО. ISBN 978-5-7996-0273-0.
  3. Комбинаторика слов. Учебное пособие для студентов математических специальностей. Изд-во Уральского университета, Екатеринбург, 2003. 96с. ISBN 978-5-7996-0168-8.
  4. (с Е.В. Сухановым) Вступительные экзамены по математике в Уральский государственный университет. В кн: Вступительные экзамены по математике в вузы Екатеринбурга. Екатеринбург, 1997. 5-14.
  5. (с В.В. Расиным, Д.С. Ананичевым, А.Г. Гейном, М.В. Волковым, С.П. Хоменко и В.П. Ивановой) Вступительные экзамены по математике в Уральский государственный университет. Изд-во Уральского университета, Екатеринбург, 2003. 44с.

Другое

  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
  5. А.М. Шур. Комбинаторные характеризации формальных языков. Дисс... доктора физ.-мат. наук. Екатеринбург, 2010. 286с.