Тип работы:
 Предмет:
 Язык работы:


О комбинаторных свойствах бесповторных языков Список литературы

Работа №103971

Тип работы

Авторефераты (РГБ)

Предмет

математика

Объем работы19
Год сдачи2016
Стоимость2000 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено
63
Не подходит работа?

Узнай цену на написание


Общая характеристика работы
Список литературы

Актуальность темы. Комбинаторика слов, относительно молодая и активно развивающаяся дисциплина, возникшая на рубеже XIX и XX веков, представляет собой важное направление на стыке современной дискретной математики и теоретических компьютерных наук, изучающее свойства символьных последовательностей (слов). Методы и результаты, разработанные и полученные в комбинаторике слов, широко применимы во многих областях, например, в теории групп, теории кодирования, теории игр, биоинформатике, сжатии данных.
Одним из основных объектов исследований в комбинаторике слов являются бесповторные языки — множества слов, не содержащих внутри себя повторяющихся фрагментов, или, как говорят, избегающих определённые структурные элементы. Норвежский математик Аксель Туэ в начале XX века занимался конструированием и изучением нескольких конкретных бесповторных языков, и принято считать, что именно с этих работ комбинаторика слов берёт своё начало как самостоятельная дисциплина. Туэ рассматривал, например, бескубный язык над двухбуквенным (бинарным) алфавитом и бесквадратный язык над трёхбуквенным (тернарным) алфавитом — эти языки состоят из слов, не содержащих трёх и двух идущих подряд одинаковых фрагментов, соответственно, — и получил ряд нетривиальных результатов, касающихся, в первую очередь, вопроса о конечности или бесконечности того или иного языка.

Возникли сложности?

Нужна помощь преподавателя?

Помощь в написании работ!
ДИПЛОМНЫЕ МАГИСТЕРСКИЕ ДИССЕРТАЦИИ
КУРСОВЫЕ СТАТЬИ ВКР

[1] Aberkane A., Currie J. D. Attainable lengths for circular binary words avoiding k-powers // Bull. Belg. Math. Soc. Simon Stevin.— 2005. — Vol. 12, no. 4.— P. 525-534.
[2] Aberkane A., Currie J. D. The Thue-Morse word contains circular (5/2)+-power-free words of every length // Theoret. Comput. Sci. — 2005. — Vol. 332. — P. 573-581.
[3] Allouche J.-P., Shallit J. Automatic Sequences: Theory, Applications, Generalizations.-- Cambridge University Press, 2003.
[4] Badkobeh G., Chairungsee S., Crochemore M. Hunting Redundancies in Strings // Proc. 15th Developments in Language Theory. DLT 2011.— Vol. 6795 of LNCS. Berlin : Springer, 2011.— P. 1{14.
[5] Badkobeh G., Crochemore M. Finite-Repetition threshold for infinite ternary words // Proc. 8th Internat. Conf. Words (WORDS 2011). - Vol. 63 of EPTCS. - 2011. - P. 37-43.
[6] Badkobeh G., Crochemore M. Fewest Repetitions in Infinite Binary Words // RAIRO Inform. Theor. App. — 2012. — Vol. 46, no. 1. — P. 1-31.
[7] Badkobeh G., Crochemore M., Rao M. Finite Repetition Threshold for Large Alphabets // Proc. 14th Mons Days of Theoretical Computer Science, 2012.
[8] Bean D. A., Ehrenfeucht A., McNulty G. Avoidable patterns in strings of symbols // Pacific J. Math. - 1979. - Vol. 85. - P. 261-294.
[9] Brandenburg F.-J. Uniformly growing k-th power-free homomorphisms // Theoret. Comput. Sci. — 1983. - Vol. 23. - P. 69-82.
[10] Carpi A. On Dejean’s conjecture over large alphabets // Theoret. Comput. Sci. — 2007. — Vol. 385. {{ P. 137{151.
[11] Cassaigne J. Unavoidable binary patterns // Acta Informatica. — 1993. Vol. 30. P. 385-395.
[12] Cassaigne J. Counting overlap-free binary words // STACS 93, Proc. 10th Symp. Theoretical Aspects of Comp. Sci. / Ed. by P. Enjalbert, A. Finkel, K. W. Wagner. — Springer-Verlag, 1993. Vol. 665 of LNCS. - P. 216-225.
[13] Crochemore M. Sharp characterizations of squarefree morphisms // Theoret. Comput. Sci. — 1982.-Vol. 18. — P. 221-226.
[14] Currie J. D. On the structure and extendibility of k-power free words // European J. Combina¬torics. — 1995. — Vol. 16. — P. 111-124.
[15] Currie J. D., Rampersad N. Dejean’s conjecture holds for n > 27 // RAIRO Inform. Theor. App. — 2009. Vol. 43. P. 775 778.
[16] Currie J. D., Rampersad N. A proof of Dejean’s conjecture // Math. Comp. — 2011.— Vol. 80.— P. 1063 1070.
[17] Currie J. D., Shelton R. O. The set of k-power free words over E is empty or perfect // European J. Combinatorics. 2003. Vol. 24. P. 573 580.
[18] Dejean F. Sur un théorème de Thue //J. Combin. Theory. Ser. A. — 1972. — Vol. 13. — P. 90-99.
[19] Fiorenzi F., Ochem P., Vaslet E. Bounds for the generalized repetition threshold // Theoret. Com- put. Sci.-2011.-Vol. 412. — P. 2955-2963.
[20] Goralcik P., Vanicek T. Binary patterns in binary words // Internat. J. Algebra Comput. — 1991. — Vol. 1.-- P. 387-391.
[21] Guglielmi N., Protasov V. Exact Computation of Joint Spectral Characteristics of Linear Opera¬tors // Foundations of Computational Mathematics. — 2013. Vol. 13, no. 1.— P. 37-97.
[22] Ilie L., Ochem P., Shallit J. A generalization of repetition threshold // Theoret. Comput. Sci. {{ 2005. {{ Vol. 345. {{ P. 359{369.
[23] Keranen V. Abelian squares are avoidable on 4 letters // Proc. 19th Int’l Conf. on Automata, Languages, and Programming (ICALP) / Ed. by W. Kuich. — Springer-Verlag, 1992.-- Vol. 623 of LNCS. {{ P. 41{52.
[24] Kolpakov R. Efficient lower bounds on the number of repetition-free words //J. Integer Sequences. — 2007. {{ Vol. 10. {{ P. 07.3.2.
[25] Kolpakov R., Rao M. On the number of Dejean words over alphabets of 5, 6, 7, 8, 9 and 10 letters // Theoret. Comput. Sci.— 2011. — Vol. 412. — P. 6507-6516.
[26] Kolpakov R. M. On the number of repetition-free words // J. Appl. Ind. Math. {{ 2007. {{ Vol. 1, no. 4. {{ P. 453{462.
[27] Merca§ R., Ochem P., Samsonov A., Shur A. Binary patterns in binary cube-free words: Avoidability and growth // RAIRO Inform. Théeor. App. {{ 2014. {{ Vol. 48, no. 4. {{ P. 369{389.
[28] Merca§ R., Saarela A. 3-abelian cubes are avoidable on binary alphabets // Proc. 17th Developments in Language Theory(DLT 2013). — Vol. 7907 of LNCS. — Springer, 2013. — P. 374-383.
[29] Mohammad-Noori M., Currie J. D. Dejean’s conjecture and Sturmian words // European J. Com¬binatorics. {{ 2007. {{ Vol. 28. {{ P. 876{890.
[30] Moulin-Ollagnier J. Proof of Dejean’s conjecture for alphabets with 5, 6, 7, 8, 9,10 and 11 letters // Theoret. Comput. Sci. — 1992. — Vol. 95. — P. 187-205.
[31] Ochem P. A generator of morphisms for inhnite words // RAIRO Inform. Théor. App. — 2006. — Vol. 40. {{ P. 427{441.
[32] Pansiot J.-J. A propos d’une conjecture de F. Dejean sur les répétitions dans les mots // Discrete Appl. Math. - 1984. - Vol. 7. - P. 297-311.
[33] Rampersad N., Shallit J., Wang M. Avoiding large squares in inhnite binary words // Theoret. Comput. Sci. {{ 2005. {{ Vol. 339. {{ P. 19{34.
[34] Rao M. Last Cases of Dejean’s Conjecture // Theoret. Comput. Sci. — 2011. — Vol. 412. — P. 3010¬3018.
[35] Restivo A., Salemi S. Overlap free words on two symbols // Automata on Inhnite Words. Ecole de Printemps d’Informatique Theorique, Le Mont Dore, 1984 / Ed. by M. Nivat, D. Perrin. — Vol. 192 of LNCS. — Springer-Verlag, 1985. — P. 198-206.
[36] Restivo A., Salemi S. Some decision results on non-repetitive words // Combinatorial algorithms on words / Ed. by A. Apostolico, Z. Galil. — Vol. F12 of NATO ASI series. — Springer-Verlag, 1985. — P. 289{295.
[37] Richomme G., Wlazinski F. Some results on k-power-free morphisms // Theoret. Comput. Sci.— 2002. {{ Vol. 273. {{ P. 119{142.
[38] Samsonov A. V., Shur A. M. On Abelian repetition threshold // Proc. 13th Mons Days of Theoretical
Computer Science. Univ. de Picardie Jules Verne, Amiens, 2)0I0. P. 1-11.
[39] Shallit J. Simultaneous avoidance of large squares and fractional powers in infinite binary words // Internat. J. Found. Comp. Sci.— 2004. — Vol. 15.— P. 317-327.
[40] Shelton R. Aperiodic words on three symbols. II // J. Reine Angew. Math.— 1981.— Vol. 327.— P. 1-11.
[41] Shelton R. O., Soni R. P. Aperiodic words on three symbols. III //J. Reine Angew. Math.— 1982. -- Vol. 330. -- P. 44-52.
[42] Shur A. M. Combinatorial complexity of regular languages // Proc. 3rd International Computer Science Symposium in Russia. CSR 2008.-- Vol. 5010 of LNCS. — Berlin : Springer, 2008.-- P. 289-301.
[43] Shur A. M. Two-sided bounds for the growth rates of power-free languages // Proc. 13th Int. Conf. on Developments in Language Theory. DLT 2009. — Vol. 5583 of LNCS. — Springer, 2009. — P. 466-477.
[44] Shur A. M. Growth of power-free languages over large alphabets // Proc. 5th International Computer Science Symposium in Russia. CSR 2010. — Vol. 6072 of LNCS. — Springer, 2010. — P. 350-361.
[45] Shur A. M. Growth rates of complexity of power-free languages // Theoret. Comput. Sci. — 2010. — Vol. 411.-- P. 3209-3223.
[46] Shur A. M. On ternary square-free circular words // Electronic J. Combinatorics. — 2010. — Vol. 17, no. # R140.
[47] Shur A. M. On the existence of minimal ^-powers // Proc. 14th Int. Conf. on Developments in Language Theory. DLT 2010. - Vol. 6224 of LNCS. - Springer, 2010. - P. 411-422.
[48] Shur A. M. Deciding context equivalence of binary overlap-free words in linear time // Semigroup Forum. - 2012. - Vol. 84. - P. 447-471.
[49] Shur A. M. Growth properties of power-free languages // Computer Science Review.-- 2012.— Vol. 6. - P. 187-208.
[50] Thue A. Uber unendliche Zeichenreihen // Norske vid. Selsk. Skr. Mat. Nat. Kl. — 1906. — Vol. 7. - P. 1-22.
[51] Thue A. Uber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen // Norske vid. Selsk. Skr. Mat. Nat. Kl.-- 1912.--Vol. 1.-P. 1-67.
[52] Tunev I. N., Shur A. M. On two stronger versions of Dejean’s conjecture // Proc. 37th Internat. Conf. on Mathematical Foundations of Computer Science. MFCS 2012. -- Vol. 7464 of LNCS. -¬2012.-- P. 801-813.

Работу высылаем на протяжении 30 минут после оплаты.



Подобные работы


©2025 Cервис помощи студентам в выполнении работ
.