RAE.RU
Энциклопедия
ИЗВЕСТНЫЕ УЧЕНЫЕ
FAMOUS SCIENTISTS
Биографические данные и фото 17193 выдающихся ученых и специалистов
Логин   Пароль  
Регистрация Забыли пароль?
 

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

Научная тема: « КОМБИНАТОРНЫЕ ХАРАКТЕРИЗАЦИИ ФОРМАЛЬНЫХ ЯЗЫКОВ »

Научная биография   « Шур Арсений Михайлович »

Членство в Российской Академии Естествознания

Специальность: 01.01.06

Год: 2010

Отрасль науки: Физико-математические науки

Основные научные положения, сформулированные автором на основании проведенных исследований:

В диссертации получены решения (полные или ча­стичные) пятнадцати проблем, сформулированных в программе исследова­ний. Все результаты диссертации являются новыми.

Список опубликованных работ

[1] Р. М. Колпаков. Об оценке числа бесповторных слов // Дискр. анализ и исслед. операций. Сер. 1. 2006. Т.13, №2. С. 21-37.

[2] A. Aberkane, J.D. Currie. The Thue-Morse word contains circular (5/2)+-power-free words of every length // Theor. Comput. Sci. 2005. Vol. 332. P. 573-581.

[3] A. Aberkane, J. D. Currie. Attainable lengths for circular binary words avoiding k-powers // Bull. Belg. Math. Soc. Simon Stevin. 2005. Vol. 12, №4. P. 525-534.

[4] J.-P. Allouche, J. Shallit. Automatic Sequences: Theory, Applications, Generalizations. Cambridge Univ. Press, 2003. - 588p.

[5] J. Balogh, B. Bollobas. Hereditary properties of words // RAIRO Inform. Theor. Appl. 2005. Vol. 39. P. 49-65.

[6] J. Balogh, B. Bollobas, D. Weinreich. The speed of hereditary properties of graphs // J. Comb. Theory, Ser. B. 2000. Vol. 79. P. 131-156.

[7] J. Balogh, B. Bollobas, D. Weinreich. The penultimate rate of growth for graph properties // European J. Comb. 2001. Vol. 22. P. 277-289.

[8] J. Berstel. Growth of repetition-free words - a review // Theor. Comput. Sci. 2005. Vol. 340(2). P. 280-290.

[9] J. Berstel, P. Seebold. A characterization of overlap-free morphisms // Discrete Appl. Math. 1993. Vol. 46(3). P. 275-281.

[10] A. Carpi. On Dejean´s conjecture over large alphabets // Theor. Comput. Sci. 2007. Vol. 385. P. 137-151.

[11] N. Chomsky, M. Schutzenberger. The algebraic theory of context-free languages // Computer Programming and Formal System. Amsterdam: North-Holland, 1963. P. 118-161.

[12] J. D. Currie. There are ternary circular square-free words of length n for n ^ 18 // Electron. J. Combin. 2002. Vol. 9. #N10.

[13] J. D. Currie, N. Rampersad. Dejean´s conjecture holds for n ^ 27 // RAIRO Inform. Theor. Appl. 2009. Vol. 43. P. 775-778.

[14] J. D. Currie, N. Rampersad. A proof of Dejean´s conjecture // 2009. Available at http://arxiv.org/PS_cache/arxiv/pdf/0905/0905.1129v3.pdf

[15] F. Dejean. Sur un Theoreme de Thue // J. Comb. Theory, Ser. A. 1972. Vol. 13. P. 90-99.

[16] A. Ehrenfeucht, K.P. Lee, G. Rozenberg. Subword complexities of various classes of deterministic developmental languages without interactions // Theor. Comput. Sci. 1975. Vol. 1. P. 59-75.

[17] A. Ehrenfeucht, K.P. Lee, G. Rozenberg. Subword complexities of various classes of deterministic developmental languages with interactions // Int. J. Comput. Information Sci. 1975. Vol. 4. P. 219-236.

[18] A. Ehrenfeucht, G. Rozenberg. On subword complexities of homomorphic images of languages // RAIRO Inform. Theor. 1982. Vol. 16. P. 303-316.

[19] A. Ehrenfeucht, G. Rozenberg. On the size of the alphabet and the subword complexity of square-free DOL languages // Semigroup Forum. 1983. Vol. 26(3-4). P. 215-223.

[20] R. Fagin. Probabilities on Finite Models // J. Symbolic Logic. 1976. Vol. 41(1). P. 50-58.

[21] P. Flajolet. Analytic models and ambiguity of context-free languages // Theor. Comput. Sci. 1987. Vol. 49. P. 283-309.

[22] I. Goulden, D.M. Jackson. An inversion theorem for cluster

decompositions of sequences with distinguished subsequences // J. London Math. Soc. 1979. Vol. 20. P. 567-576.

[23] M. Gromov. Groups of polynomial growth and expanding maps // Inst. Hautes Etudes Sci. Publ. Math. 1981. Vol. 53. P. 53-78.

[24] R. M. Jungers, V. Y. Protasov, V.D. Blondel. Overlap-free words and spectra of matrices // Theor. Comput. Sci. 2009. Vol. 410. P. 3670-3684.

[25] J. Karhumaki, J. Shallit. Polynomial versus exponential growth in repetition-free binary words // J. Combin. Theory. Ser. A 2004. Vol. 104. P. 335-347.

[26] R. Kolpakov. Efficient lower bounds on the number of repetition-free words II J. Int. Sequences. 2007. Vol. 10. #07.3.2 (electronic).

[27] T. Kotek, J. A. Makowsky. Definability of combinatorial functions and their linear recurrence relations // Preprint. 2010. Available online at http://www.cs.technion.ac.il/^tkotek/pubfiles/YG70.pdf

[28] G. Krause, T. H. Lenagan. Growth of Algebras and Gelfand-Kirillov Dimension. Research Notes in Math. Vol. 116. London: Pitman, 1985. - 212pp.

[29] M. Li, P. Vitanyi. An Introduction to Kolmogorov Complexity and Its Applications. 3rd Ed. Berlin: Springer, 2008. - xxiii+792pp.

[30] M. Mohammad-Noori, J.D. Currie. Dejean´s conjecture and Sturmian words j! European. J. Combin. 2007. Vol. 28. P. 876-890.

[31] M. Morse, G.A. Hedlund. Symbolic dynamics // Amer. J. Math. 1938. Vol. 60. P. 815-866.

[32] M. Morse, G. A. Hedlund. Symbolic dynamics II. Sturmian trajectories // Amer. J. Math. 1940. Vol. 62. P. 1-42.

[33] J. Moulin-Ollagnier. Proof of Dejean´s Conjecture for Alphabets with 5, 6, 7, 8, 9, 10 and 11 Letters // Theor. Comput. Sci. 1992. Vol. 95. P. 187-205.

[34] J. Noonan, D. Zeilberger. The Goulden-Jackson Cluster Method: Extensions, Applications, and Implementations // J. Difference Eq. Appl. 1999. Vol. 5. P. 355-377.

[35] P. Ochem, T. Reix. Upper bound on the number of ternary square-free words lj Proc. Workshop on words and automata (WOWA´06). S.-Petersburg, 2006. #8 (electronic).

[36] J.-J. Pansiot. A propos d´une conjecture de F. Dejean sur les repetitions dans les mots // Discr. Appl. Math. 1984. Vol. 7. P. 297-311.

[37] J.-J. Pansiot. Complexite des facteurs des mots infinis engendres par morphismes iteres // Proc. 11th Int. Colloq. on Automata, Languages and Programming. Heidelberg: Springer, 1984. P. 380-389. (LNCS Vol.

172).

[38] M. Rao. Last Cases of Dejean´s Conjecture // Proc. 7th Int. Conf. on Words. Salerno, Italy. 2009. #115.

[39] A. Salomaa, M. Soittola. Automata-theoretic aspects of formal power series. Texts and Monographs in Computer Science. NY: Springer, 1978. -168pp.

[40] E. R. Scheinerman, J. S. Zito. On the size of hereditary classes of graphs II J. Comb. Theory, Ser. B. 1994. Vol. 61. P. 16-39.

[41] P. Seebold. Overlap-free sequences // Automata on Infinite Words. Ecole de Printemps d´Informatique Theorique, Le Mont Dore, 1984. P. 207-215. Heidelberg: Springer, 1984. (LNCS Vol. 192).

[42] A. Thue. Uber unendliche Zeichenreihen // Kra. Vidensk. Selsk. Skrifter. I. Mat.-Nat. Kl. №7. Christiana, 1906. P. 1-22.

[43] A. Thue. Uber die gegenseitige Lage gleicher Teile gewisser Zeichentreihen II Norske Vid. Selsk. Skr. I, Mat. Nat. Kl. №1. Christiana, 1912. P. 1-67.

[44] E.B. Суханов, A.M. Шур. Об одном классе формальных языков // Алгебра и логика. 1998. Т.37, №4. С. 478-492.

[45] А. М. Шур. Синтаксические полугруппы избегаемых языков // Сиб. мат. журнал. 1998. Т.39, №3. С. 683-702.

[46] А. М. Шур. Структура множества бескубных Z-слов в двухбуквен-ном алфавите // Изв. РАН. Сер. матем. 2000. Т.64, №4. С. 201-224.

[47] A.M. Шур. Комбинаторная сложность рациональных языков // Дискр. анализ и исслед. операций, Сер. 1. 2005. Т.12, №2. С. 78-99.

[48] А. М. Шур. Индексы роста языков ограниченной экспоненты // Изв. вузов. Математика. 2009. №9. С. 82-88.

[49] А. М. Шур. Языки с конечным антисловарем: индексы роста и свой-ства графов Ij Известия УрГУ, Сер. Математика, Механика, Инфор-матика. 2010. Т.12 (74). С. 220-245.

[50] А. М. Шур. О вычислении параметров и типов поведения комбина-торной сложности регулярных языков // Труды ИММ УрО РАН. 2010. Т.16, №2. С. 270-287.

[51] A.M. Шур. Рост языков с ограничениями на степени подслое: чис-ленные и асимптотические оценки // Докл. РАН. 2010. Т.432, №3. С. 315-317.

[52] A.M. Shur. Overlap-free words and Thue-Morse sequences // Int. J. Alg. and Сотр. 1996. Vol. 6. P. 353-367.

[53] A. M. Shur. Binary words avoided by the Thue-Morse sequence // Semigroup Forum. 1996. Vol. 53. P. 212-219.

[54] A.M. Shur. Factorial Languages of Low Combinatorial Complexity // Proc. 10th Int. Conf. on Developments in Language Theory. Berlin: Springer, 2006. P. 397-407. (LNCS Vol. 4036).

[55] A. M. Shur. Comparing complexity functions of a language and its extendable part // Proc. 11th Mons Days of Theoretical Computer Science. IRISA-Rennes, Rennes, 2006. P. 784-788.

[56] A.M. Shur. Rational approximations of polynomial factorial languages // Int. J. Foundat. Comput. Sci. 2007. Vol. 18. P. 655-665.

[57] A. M. Shur. Combinatorial complexity of regular languages // Proc. 3rd International Computer Science Symposium in Russia. Berlin: Springer, 2008. P. 289-301. (LNCS Vol. 5010).

[58] A. M. Shur. Comparing complexity functions of a language and its extendable part // RAIRO Inform. Theor. Appl. 2008. Vol. 42. P. 647-655.

[59] A. M. Shur, I. A. Gorbunova. On the growth rates of complexity of threshold languages // Proc. 12th Mons Days of Theoretical Computer Science. Univ. de Mons-Hainaut, Mons, 2008. P. 1-10.

A.M. Shur. Polynomial languages with finite antidictionaries // RAIRO Inform. Theor. Appl. 2009. Vol. 43. P. 269-280.

A. M. Shur. On intermediate factorial languages // Discr. Appl. Math. 2009. Vol. 157. P. 1669-1675.

A.M. Shur. Two-sided bounds for the growth rates of power-free languages lj Proc. 13th Int. Conf. on Developments in Language Theory. Berlin: Springer, 2009. P. 466-477. (LNCS Vol. 5583).

A. M. Shur, I. A. Gorbunova. On the growth rates of complexity of threshold languages // RAIRO Inform. Theor. Appl. 2010. Vol. 44. P. 175-192.

A.M. Shur. Growth rates of complexity of power-free languages // Theor. Comput. Sci. 2010. Vol. 411. P. 3209-3223.

A.M. Shur. Growth of power-free languages over large alphabets // Proc. 5th International Computer Science Symposium in Russia. Berlin: Springer, 2010. P. 350-361. (LNCS Vol. 6072).

A. M. Shur. On the existence of minimal [5-powers // Proc. 14th Int. Conf. on Developments in Language Theory. Berlin: Springer, 2010. P. 411-422. (LNCS Vol. 6224).

A. M. Shur. On ternary square-free circular words // Electronic J. Combinatorics. 2010. Vol. 17 (to appear). 11PP. Available at http://arxiv.org/PS_cache/arxiv/pdf/1009/1009.5759vl.pdf

A.V. Samsonov, A.M. Shur. On Abelian repetition threshold // Proc. 13th Mons Days of Theoretical Computer Science. Univ. de Picardie Jules Verne, Amiens, 2010. P. 1-11.

Комментарии:

Если вы считаете, что какое-то сообщение нарушает Правила, оскорбляет Вас как личность, несёт заведомо ложную информацию, и должно быть удалено, сообщите нам по адресу sergey@rae.ru

Ваше имя
Текст комментария
Введите число с изображения

Антиспам защита

При добавлении комментария Вы соглашаетесь с пользовательским соглашением