|
Архив семинара:
|
26.02.2013, 14.00, в зале заседаний Ученого совета ИПС
Антонина Николаевна Непейвода
Об усилении хигманова вложения при построении регулярных приближений циклов
В докладе рассматривается бинарное отношение на словах в последовательности, порожденной системой переписывания префиксов, впервые описанное В.Ф.Турчиным в 1988 году для задачи приближения циклов. Приводится новое простое доказательство того, что в каждой последовательности, порожденной системой переписывания префиксов, найдется пара элементов, удовлетворяющих отношению Турчина, и оценка максимальной длины отрезка последовательности, не содержащей таких пар. Показывается связь между отношением Турчина и отношением Хигмана на последовательностях слов, порожденных системой переписывания префиксов.
(Загрузить слайды)
|