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

Последнее изменение: 25/08/2016 12:56:00
 

Сборники трудов конференций

  1. (with D. Gasnikov) Ternary square-free partial words with many wildcards. Proc. DLT 2016: Springer, 2016. 177-189 (LNCS Vol. 9840)
  2. (with P. Gawrychowski, O. Merkurev, 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)
  3. (with M. Rubinchik) EERTREE: An efficient data structure for processing palindromes in strings. Proc. IWOCA 2015: Springer, 2016. 321-333. (LNCS Vol. 9538)
  4. (with E. Petrova) On the Tree of Ternary Square-Free Words. Proc. WORDS 2015: Springer, 2015. 223-236. (LNCS Vol. 9304)
  5. (with D. Kosolobov and M. Rubinchik) Pal^k is linear recognizable online. Proc. 41th Int. Conf. on Theory and Practice of Computer Science (SOFSEM 2015). Springer, 2015. 289-301. (LNCS Vol. 8939)
  6. (with M. Rubinchik) On the number of distinct subpalindromes in words. Proc. 3rd Russian Finnish Symp. on Discrete Mathematics. Inst. Appl. Math. Research, Petrozavodsk, 2014. 96-98.
  7. (with A. Yakaryilmaz) Quantum, Stochastic, and Pseudo Stochastic Languages with Few States. Proc. UCNC 2014. Springer, 2014. 327–339. (LNCS Vol. 8553).
  8. (with D. Kosolobov and M. Rubinchik) Finding Distinct Subpalindromes Online. Proc. Prague Stringology Conf. 2013. Prague: Czech Technical University, 2013. 63-69.
  9. Languages with a Finite Antidictionary: Growth-Preserving Transformations and Available Orders of Growth. Proc. 17th Int. Conf. on Developments in Language Theory. Berlin: Springer, 2013. 445-457. (LNCS Vol. 7907)
  10. (with L. Idiatulina) Periodic partial words and random bipartite graphs. Proc. 2nd Russian Finnish Symp. on Discrete Mathematics, Turku, 2012. 25-28. (TUCS Lecture Notes No. 17)
  11. (with A. Samsonov) Binary patterns in binary cube-free words: avoidability and growth. Proc. 14th Mons Days of Theoretical Computer Science. Catholic Univ. Louvain, Louvain-la-Nueve, 2012. 7pp. (Electronic).
  12. (with I. Tunev) On two stronger versions of Dejean's conjecture. Mathematical foundations of computer science. Berlin: Springer, 2012. 800-812. (LNCS Vol. 7464).
  13. (with E. Petrova) Constructing premaximal ternary square-free words of any level. Mathematical foundations of computer science. Berlin: Springer, 2012. 752-763. (LNCS Vol. 7464).
  14. (with N. Rampersad and J. Shallit) Fife's theorem for (7/3)-powers. Proc. 8th Int. Conf. WORDS 2011. EPTCS Vol.63 (2011), 189–198.
  15. (with I. Gorbunova) On Pansiot words avoiding 3-repetitions. Proc. 8th Int. Conf. WORDS 2011. EPTCS Vol.63 (2011), 138–146.
  16. (with E. Petrova) Constructing premaximal binary cube-free words of any level. Proc. 8th Int. Conf. WORDS 2011. EPTCS Vol.63 (2011), 168–178.
  17. Growth properties of power-free languages. Proc. 15th Int. Conf. on Developments in Language Theory. Berlin: Springer, 2011. 28-43. (LNCS Vol. 6795).
  18. (with A. Plyushchenko) On Brzozovski's conjecture for the free Burnside semigroup satisfying $x^2=x^3$. Proc. 15th Int. Conf. on Developments in Language Theory. Berlin: Springer, 2011. 362-373. (LNCS Vol. 6795).
  19. (with K. Likhomanov) Two combinatorial criteria for BWT images. Proc. 6th International Computer Science Symposium in Russia. Berlin: Springer, 2011. 385-396. (LNCS Vol. 6651).
  20. (with A. Samsonov) On Abelian repetition threshold. Proc. 13th Mons Days of Theoretical Computer Science. Univ. de Picardie Jules Verne, Amiens, 2010. 1--11.
  21. On the existence of minimal $\beta$-powers. Proc. 14th Int. Conf. on Developments in Language Theory. Berlin: Springer, 2010. 411-422. (LNCS Vol. 6224).
  22. Growth of power-free languages over large alphabets. Proc. 5th International Computer Science Symposium in Russia. Berlin: Springer, 2010. 350-361. (LNCS Vol. 6072).
  23. Two-sided bounds for the growth rates of power-free languages. Proc. 13th Int. Conf. on Developments in Language Theory. Berlin: Springer, 2009. 466-477. (LNCS Vol. 5583).
  24. Combinatorial complexity of regular languages. Proc. 3rd International Computer Science Symposium in Russia. Berlin: Springer, 2008. 289-301. (LNCS Vol. 5010).
  25. (with I.Gorbunova) On the growth rates of complexity of threshold languages. In: 12th Mons Days of Theoretical Computer Science, Int. Proc. Univ. de Mons-Hainaut, Mons, 2008, 10pp.
  26. (with A. Plyushchenko) Almost overlap-free words and the word problem for the free Burnside semigroup satisfying $x^2=x^3$. Proc. 6th Int. Conf. WORDS, 2007, 245-253, Institut de mathématiques de Luminy, Marseille, France, 2007.
  27. Factorial languages of low combinatorial complexity. Proc. 10th Int. Conf. on Developments in Language Theory. Berlin: Springer, 2006. 397-407. (LNCS Vol. 4036).
  28. Comparing complexity functions of a language and its extendable part. In: 11th Mons Days of Theoretical Computer Science, Int. Proc. 323-327, IRISA-Rennes, Univ. Rennes, Rennes, 2006.
  29. (with Yu. Gamzova) Periods' interaction property for partial words. Proc. 4th Int. Conf. WORDS, Turku, 2003. 75-82. (TUCS Gen. Publ., Vol. 27).
  30. (with Yu. Konovalova) On the periods of partial words. Proc. 26th Int. Symp. Mathematical Foundations of Computer Science. Berlin: Springer, 2001. 657-665. (LNCS Vol. 2136).
  31. (with E. Sukhanov) 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. (with C. Guo and J. Shallit) Palindromic rich words and run-length encodings. Inform. Process. Lett. Vol. 116(12) (2016), 735-738
  2. (with M. Rubinchik) The number of distinct subpalindromes in random words. Fundamenta Informaticae. 2016. Vol. 145(3). P. 371-384.
  3. (with A. Yakaryilmaz) More on quantum, stochastic, and pseudo stochastic languages with few states. Natural Computing. 2016. Vol. 15(1). P. 129-141.
  4. (with C.F. Du and J. Shallit) Optimal bounds for the similarity density of the Thue-Morse word with overlap-free and 7/3-power-free infinite binary words. Internat. J. Foundations of Comput. Sci. 2015. Vol. 26(8). P. 1147-1166.
  5. Generating square-free words efficiently. Theoretical Computer Science. 2015. Vol. 601. P. 67-72.
  6. (with W. Rytter) Searching for Zimin patterns. Theoretical Computer Science. 2015. Vol. 571. P. 50-57.
  7. Languages with a finite antidictionary: some growth questions. Internat J. Foundations of Comput. Sci. 2014. Vol. 25(8). P. 937-954.
  8. (with R. Mercaş, P. Ochem, and A. Samsonov) Binary patterns in binary cube-free words: Avoidability and growth. RAIRO - Theoretical Informatics and Applications. 2014. Vol. 48(4). P. 369-389.
  9. (with L. Idiatulina) Periodic partial words and random bipartite graphs. Fundamenta Informaticae. 2014. Vol. 132(1). P. 15-31.
  10. Growth of power-free languages over large alphabets. Theory of Computing Systems. 2014. Vol. 54(2). P.224-243.
  11. (with I. Gorbunova) On Pansiot words avoiding 3-repetitions. Internat. J. Foundations of Comp. Sci. 2012. Vol. 23(8). P. 1583-1594.
  12. (with E. Petrova) Constructing premaximal binary cube-free words of any level. Internat. J. Foundations of Comp. Sci. 2012. Vol. 23(8). P. 1595-1610.
  13. Growth properties of power-free languages. Computer Science Review. 2012. Vol. 6. P. 187-208.
  14. Deciding context equivalence of binary overlap-free words in linear time. Semigroup Forum. 2012. Vol.84(3). P. 447-471.
  15. (with A. Samsonov) On Abelian repetition threshold. RAIRO Inform. Theor. Appl. 2012. Vol. 46. P. 147-163.
  16. On the existence of minimal β-powers. Internat. J. Foundations of Comp. Sci., 2011. Vol. 22(7). P. 1683-1696.
  17. (with A. Plyushchenko) Almost overlap-free words and the word problem for the free Burnside semigroup satisfying $x^2=x^3$. Int. J. Algebra and Comput. 2011. Vol. 21(6). P. 973–1006. DOI: 10.1142/S0218196711006558.
  18. On ternary square-free circular words. Electronic J. Combinatorics. 2010. Vol. 17(1). Article No. R140.
  19. Growth rates of complexity of power-free languages. Theor. Comput. Sci. 2010. Vol. 411. P. 3209-3223.
  20. Рост языков с ограничениями на степени подслов: численные и асимптотические оценки. Доклады РАН. 2010. Т.432, №3. 315-317.
  21. О вычислении параметров и типов поведения комбинаторной сложности регулярных языков. Труды ИММ УрО РАН. 2010. Т.16, №2. 270-287. PDF
  22. (with I.A.Gorbunova) On the growth rates of complexity of threshold languages. RAIRO Inform. Theor. Appl. 2010. Vol. 44. P. 175-192.
  23. Языки с конечным антисловарем: индексы роста и свойства автоматов. Известия УрГУ, 74 (2010) 220-245. PDF
  24. Индексы роста языков ограниченной экспоненты. Известия вузов, Математика. 2009(9), 82–88.
  25. Polynomial languages with finite antidictionaries. RAIRO Theor. Inform. and Appl., 43(2) (2009), 269-280.
  26. On intermediate factorial languages. Discrete Applied Mathematics 157(7) (2009), 1669-1675.
  27. Comparing complexity functions of a language and its extendable part. RAIRO Theor. Inf. Appl. 42 (2008) 647-655.
  28. Rational approximations of polynomial factorial languages. Int. J. Foundat. Comp. Sci., 18 (2007). 655-665.
  29. Комбинаторная сложность рациональных языков. Дискр. анализ и исслед. операций, Сер. 1. 12(2) (2005), 78-99. PDF
  30. (с Ю.В. Гамзовой) Частичные слова и свойство взаимодействия периодов. Известия РАН, сер. матем. 68(2) (2004), 191-214.
  31. Структура множества бескубных Z-слов в двухбуквенном алфавите. Известия РАН, сер. матем. 64(4) (2000), 201-224.
  32. (с Е.В. Сухановым) Об одном классе формальных языков. Алгебра и логика, 37(4) (1998), 478-492.
  33. Синтаксические полугруппы избегаемых языков. Сиб. Мат. журнал, 39(3) (1998), 683-702.
  34. Бинарная избегаемость и слова Туэ-Морса. Доклады РАН, 348(5) (1996), 598-599.
  35. Overlap-free words and Thue-Morse sequences. Int. J. Algebra and Comput. 6(3) (1996), 353-367.
  36. Binary words avoided by the Thue-Morse sequence. Semigroup Forum 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. 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
  2. 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
  3. 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
  4. А.М. Шур. Комбинаторные характеризации формальных языков. Дисс... доктора физ.-мат. наук. Екатеринбург, 2010. 286с.