WWW.KN.LIB-I.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Различные ресурсы
 


«Лекция 5, 16.10.2011 Лекция 5 Комбинаторные сложности и всякая всячина 1/42 Комбинаторная сложность Определение Комбинаторной сложностью бесконечного слова w называется функция pw (n), ...»

Комбинаторные сложностные характеристики

бесконечных слов

Анна (Эдуардовна) Фрид

ИМ им. С. Л. Соболева СО РАН, Новосибирск

anna.e.frid@gmail.com

Лекция 5, 16.10.2011

Лекция 5 Комбинаторные сложности и всякая всячина 1/42

Комбинаторная сложность

Определение

Комбинаторной сложностью бесконечного слова w называется

функция pw (n), равная числу его подслов длины n.

Лекция 5 Комбинаторные сложности и всякая всячина 2/42

Комбинаторная сложность

Определение Комбинаторной сложностью бесконечного слова w называется функция pw (n), равная числу его подслов длины n.

Example В слове Туэ-Морса 0110 1001 1001 0110 1001 0110 0110 1001 · · · не встречаются слова 000 и 111, поэтому pTM (3) = 6.

Лекция 5 Комбинаторные сложности и всякая всячина 2/42 Свойства функции сложности Напомним, что слово (со временем) периодическое, если имеет вид uvvvvvv · · ·.

Лекция 5 Комбинаторные сложности и всякая всячина 3/42 Свойства функции сложности Напомним, что слово (со временем) периодическое, если имеет вид uvvvvvv · · ·.

Для любого бесконечного слова над алфавитом мощности q 1 pw (n) q n ;

Лекция 5 Комбинаторные сложности и всякая всячина 3/42 Свойства функции сложности Напомним, что слово (со временем) периодическое, если имеет вид uvvvvvv · · ·.

Для любого бесконечного слова над алфавитом мощности q 1 pw (n) q n ;

Функция pw (n) не убывает;

Лекция 5 Комбинаторные сложности и всякая всячина 3/42 Свойства функции сложности Напомним, что слово (со временем) периодическое, если имеет вид uvvvvvv · · ·.

Для любого бесконечного слова над алфавитом мощности q 1 pw (n) q n ;

Функция pw (n) не убывает;

Функция pw (n) ограничена тогда и только тогда, когда слово w со временем периодично.

Лекция 5 Комбинаторные сложности и всякая всячина 3/42 Свойства функции сложности (продолжение) Минимальная сложность непериодических слов равна n + 1 (слова Штурма).

Лекция 5 Комбинаторные сложности и всякая всячина 4/42 Свойства функции сложности (продолжение) Минимальная сложность непериодических слов равна n + 1 (слова Штурма).

Сложность автоматных слов растет линейно.

Лекция 5 Комбинаторные сложности и всякая всячина 4/42 Свойства функции сложности (продолжение) Минимальная сложность непериодических слов равна n + 1 (слова Штурма).

Сложность автоматных слов растет линейно.

Сложность неподвижных точек морфизмов растет как O(n2 ), O(n log n), O(n log log n), O(n) или O(1) [Pansiot 1984].

Лекция 5 Комбинаторные сложности и всякая всячина 4/42 Свойства функции сложности (продолжение) Минимальная сложность непериодических слов равна n + 1 (слова Штурма).

Сложность автоматных слов растет линейно.

Сложность неподвижных точек морфизмов растет как O(n2 ), O(n log n), O(n log log n), O(n) или O(1) [Pansiot 1984].

Сложность морфических слов растет как O(n1+1/k ) для некоторого k или как O(n log n) (или медленнее) [Devyatov, 2008:

доказательство опубликовано частично].

Лекция 5 Комбинаторные сложности и всякая всячина 4/42 Свойства функции сложности (продолжение) Минимальная сложность непериодических слов равна n + 1 (слова Штурма).

Сложность автоматных слов растет линейно.

Сложность неподвижных точек морфизмов растет как O(n2 ), O(n log n), O(n log log n), O(n) или O(1) [Pansiot 1984].

Сложность морфических слов растет как O(n1+1/k ) для некоторого k или как O(n log n) (или медленнее) [Devyatov, 2008:





доказательство опубликовано частично].

Если сложность слова растет линейно, то ее первые разности ограничены [Cassaigne, 1996].

–  –  –

Рассмотрим продолжаемый факторный язык F например, язык подслов бесконечного слова.

Продолжаемый: u F a, b : aub F.

Факторный: замкнутый относительно взятия подслова.

–  –  –

Рассмотрим продолжаемый факторный язык F например, язык подслов бесконечного слова.

Продолжаемый: u F a, b : aub F.

Факторный: замкнутый относительно взятия подслова.

Обозначим через l(u) (r (u)) множество символов, которыми слово u может быть продолжено влево (вправо), и назовем специальным влево (вправо) слово, у которого l(u) = 1 (r (u) = 1).

–  –  –

Обозначим через F (n) множество всех слов языка F длины n, а через L(n) множество его специальных слов длины n.

Лекция 5 Комбинаторные сложности и всякая всячина 6/42 Метод специальных слов Обозначим через F (n) множество всех слов языка F длины n, а через L(n) множество его специальных слов длины n.

Тогда первые разности комбинаторной сложности:

–  –  –

Слово биспециально, если оно специально справа и слева. Множество B(n).

Лекция 5 Комбинаторные сложности и всякая всячина 7/42 Биспециальные слова Лекция 5 Комбинаторные сложности и всякая всячина 8/42 Граф биспециальности История: Cassaigne 1994,1997; Августинович 1994 (Туэ-Морс), Августинович-Фрид 1998.

Лекция 5 Комбинаторные сложности и всякая всячина 8/42 Линейная сложность Характеризации бесконечных слов с линейной комбинаторной сложностью нет.

S-adic conjecture Бесконечное слово имеет линейную комбинаторную сложность тогда и только тогда, когда каким-то образом задается морфизмами.

Лекция 5 Комбинаторные сложности и всякая всячина 9/42 Линейная сложность Характеризации бесконечных слов с линейной комбинаторной сложностью нет.

S-adic conjecture Бесконечное слово имеет линейную комбинаторную сложность тогда и только тогда, когда каким-то образом задается морфизмами.

S. Ferenczi продвинулся дальше всех Лекция 5 Комбинаторные сложности и всякая всячина 9/42 Арифметическая сложность Арифметическим замыканием бесконечного слова w = w0 w1 · · · wn · · · называется множество

–  –  –

Лекция 5 Комбинаторные сложности и всякая всячина 10/42 Арифметическая сложность Арифметическим замыканием бесконечного слова w = w0 w1 · · · wn · · · называется множество Aw = {wk wk+d wk+2d · · · wk+(n1)d |k 0, d 0}.

Арифметическая сложность aw (n) определяется как

–  –  –

Avgustinovich, Fon-Der-Flaass, Frid 2000 (2003).

Лекция 5 Комбинаторные сложности и всякая всячина 10/42 Свойства арифметической сложности Для любого бесконечного слова над алфавитом мощности q pw (n) aw (n) q n ;

Лекция 5 Комбинаторные сложности и всякая всячина 11/42 Свойства арифметической сложности Для любого бесконечного слова над алфавитом мощности q pw (n) aw (n) q n ;

Функция aw (n) не убывает;

Лекция 5 Комбинаторные сложности и всякая всячина 11/42 Свойства арифметической сложности Для любого бесконечного слова над алфавитом мощности q pw (n) aw (n) q n ;

Функция aw (n) не убывает;

Функция aw (n) ограничена тогда и только тогда, когда слово w со временем периодично.

Лекция 5 Комбинаторные сложности и всякая всячина 11/42 Свойства арифметической сложности Для любого бесконечного слова над алфавитом мощности q pw (n) aw (n) q n ;

Функция aw (n) не убывает;

Функция aw (n) ограничена тогда и только тогда, когда слово w со временем периодично.

Theorem (Ван-дер-Варден) w n a | an Aw.

Лекция 5 Комбинаторные сложности и всякая всячина 11/42 Естественные вопросы Какова арифметическая сложность слова Туэ-Морса?

Лекция 5 Комбинаторные сложности и всякая всячина 12/42 Естественные вопросы Какова арифметическая сложность слова Туэ-Морса?

Слова дракона?

Лекция 5 Комбинаторные сложности и всякая всячина 12/42 Естественные вопросы Какова арифметическая сложность слова Туэ-Морса?

Слова дракона?

Слов Штурма?

Лекция 5 Комбинаторные сложности и всякая всячина 12/42 Естественные вопросы Какова арифметическая сложность слова Туэ-Морса?

Слова дракона?

Слов Штурма?

Когда сложность минимальна?

Лекция 5 Комбинаторные сложности и всякая всячина 12/42 Естественные вопросы Какова арифметическая сложность слова Туэ-Морса?

Слова дракона?

Слов Штурма?

Когда сложность минимальна?

Когда сложность линейна?

Лекция 5 Комбинаторные сложности и всякая всячина 12/42 Естественные вопросы Какова арифметическая сложность слова Туэ-Морса?

Слова дракона?

Слов Штурма?

Когда сложность минимальна?

Когда сложность линейна?

Какой она вообще может быть?

Лекция 5 Комбинаторные сложности и всякая всячина 12/42 Арифметическая сложность некоторых слов Theorem (AFF) Арифметическая сложность слова Туэ-Морса равна 2n.

Лекция 5 Комбинаторные сложности и всякая всячина 13/42 Арифметическая сложность некоторых слов Theorem (AFF) Арифметическая сложность слова Туэ-Морса равна 2n.

Доказательство: a, b ATM одинаковой длины = a b ATM.

Лекция 5 Комбинаторные сложности и всякая всячина 13/42 Арифметическая сложность некоторых слов Theorem (AFF) Арифметическая сложность слова Туэ-Морса равна 2n.

Доказательство: a, b ATM одинаковой длины = a b ATM.

Theorem (AFF) Арифметическая сложность слова дракона равна 8n начиная с n = 14.

Лекция 5 Комбинаторные сложности и всякая всячина 13/42 Слово дракона (paperfolding word)

–  –  –

Theorem (Frid, 2005) Арифметическая сложность равномерно рекуррентного слова линейна тогда и только тогда, когда его множество подслов такое же, как у слов Теплица, порожденных периодичной (возможно, с предпериодом) последовательностью p-регулярных шаблонов Теплица, где p просто.

p-регулярный шаблон:

–  –  –

Theorem (Salimov, 2009) Существуют бесконечные слова с арифметической сложностью, растущей быстрее, чем любой полином, но медленнее, чем n для любого 1.

Лекция 5 Комбинаторные сложности и всякая всячина 18/42 Промежуточная арифметическая сложность Theorem (Salimov, 2009) Существуют бесконечные слова с арифметической сложностью, растущей быстрее, чем любой полином, но медленнее, чем n для любого 1.

Ср. с Theorem (Cassaigne, 2002) Существуют бесконечные слова с комбинаторной сложностью, растущей быстрее, чем любой полином, но медленнее, чем n для любого 1.

Лекция 5 Комбинаторные сложности и всякая всячина 18/42 Сложность Камаэ

–  –  –

Theorem (Kamae, Zamboni, 2002) Бесконечное слово w не периодично тогда и только тогда, когда pw (n) 2n для всех достаточно больших n.

Лекция 5 Комбинаторные сложности и всякая всячина 29/42 Низкая сложность Камаэ Theorem (Kamae, Zamboni, 2002) Бесконечное слово w не периодично тогда и только тогда, когда pw (n) 2n для всех достаточно больших n.

Слова со сложностью 2n: все слова Штурма, простые слова Теплица...

и другие.

Лекция 5 Комбинаторные сложности и всякая всячина 29/42 Низкая сложность Камаэ Theorem (Kamae, Zamboni, 2002) Бесконечное слово w не периодично тогда и только тогда, когда pw (n) 2n для всех достаточно больших n.

Слова со сложностью 2n: все слова Штурма, простые слова Теплица...

и другие.

Theorem (KZ 2002) Сложность Камаэ слова Туэ-Морса равна 2n.

Лекция 5 Комбинаторные сложности и всякая всячина 29/42 Низкая сложность Камаэ Theorem (Kamae, Zamboni, 2002) Бесконечное слово w не периодично тогда и только тогда, когда pw (n) 2n для всех достаточно больших n.

Слова со сложностью 2n: все слова Штурма, простые слова Теплица...

и другие.

Theorem (KZ 2002) Сложность Камаэ слова Туэ-Морса равна 2n.

Kamae, Salimov недавно разобрались со сложностью Камаэ неподвижных точек бинарных однородных морфизмов.

Лекция 5 Комбинаторные сложности и всякая всячина 29/42 Перестановки и слова Пусть a = a0, a1, a2,... и b = b0, b1, b2,... две последовательности действительных чисел, и

–  –  –

Пример: 100, 200, 197 = 90, 100, 98 = 1, 3, 2 Можно писать просто = 1 3 2, но лучше различать перестановки и их представители.

Лекция 5 Комбинаторные сложности и всякая всячина 30/42 Перестановки, порожденные словами

–  –  –

TM = aTM Естественно рассматривать перестановки, порожденные бинарными словами.

Лекция 5 Комбинаторные сложности и всякая всячина 31/42 Подперестановки или факторы

По аналогии с подсловами:

011010011001 · · · Лекция 5 Комбинаторные сложности и всякая всячина 32/42 Подперестановки или факторы

По аналогии с подсловами:

011010011001 · · · Лекция 5 Комбинаторные сложности и всякая всячина 33/42 Перестановочная сложность Denition Перестановочной сложностью tw (n) непериодического бесконечного слова w называется число подперестановок заданной длины n порожденной им бесконечной перестановки.

Лекция 5 Комбинаторные сложности и всякая всячина 34/42 Свойства перестановочной сложности Все нижеследующее верно только для бинарных слов!

Лекция 5 Комбинаторные сложности и всякая всячина 35/42 Свойства перестановочной сложности Все нижеследующее верно только для бинарных слов!

tw (n) pw (n 1).

Лекция 5 Комбинаторные сложности и всякая всячина 35/42 Свойства перестановочной сложности

–  –  –

Лекция 5 Комбинаторные сложности и всякая всячина 36/42 Свойства перестановочной сложности Перестановочная сложность слов Штурма равна n, и это минимум для перестановочной сложности слов.

[Макаров, 2006] Лекция 5 Комбинаторные сложности и всякая всячина 37/42 Свойства перестановочной сложности Перестановочная сложность слов Штурма равна n, и это минимум для перестановочной сложности слов.

[Макаров, 2006] Перестановочная сложность слова Туэ-Морса нашел S. Widmer (2011); Валюженич успел обобщить.

Лекция 5 Комбинаторные сложности и всякая всячина 37/42 Первый дополнительный слайд с красивой картинкой [Fon-Der-Flaass, Frid, 2005] Лекция 5 Комбинаторные сложности и всякая всячина 38/42 Второй дополнительный слайд с красивой картинкой Перестановки Штурма

–  –  –

Theorem (Avgustinovich, F., Kamae, Salimov, 2011) Бесконечная перестановка w непериодична тогда и только тогда, когда pw (n) n для всех достаточно больших n.

Лекция 5 Комбинаторные сложности и всякая всячина 40/42 Низкая сложность Камаэ Theorem (Avgustinovich, F., Kamae, Salimov, 2011) Бесконечная перестановка w непериодична тогда и только тогда, когда pw (n) n для всех достаточно больших n.

Несомненно, это аналог Theorem (Kamae, Zamboni, 2002) Бесконечное слово w не периодично тогда и только тогда, когда pw (n) 2n для всех достаточно больших n.

Лекция 5 Комбинаторные сложности и всякая всячина 40/42 Низкая сложность Камаэ Theorem (Avgustinovich, F., Kamae, Salimov, 2011) Бесконечная перестановка w непериодична тогда и только тогда, когда pw (n) n для всех достаточно больших n.

Несомненно, это аналог Theorem (Kamae, Zamboni, 2002) Бесконечное слово w не периодично тогда и только тогда, когда pw (n) 2n для всех достаточно больших n.

НО! Перестановки со сложностью ровно n это в точности перестановки Штурма.

–  –  –

Лекция 5 Комбинаторные сложности и всякая всячина 41/42 Перестановка Туэ-Морса Два совсем разных представителя!

0,1




Похожие работы:

«ПРИЛОЖЕНИЕ № 6 к протоколу заседания подкомиссии по использованию информационных технологий при предоставлении государственных и муниципальных услуг Правительственной комиссии по использованию информационных технологий для улучшения качества жизни и условий ведения предпринимательской деятельн...»

«Ю. Д. Д М И Т Р Е В С К И Й J A -s r ВН УТРЕН Н И Е ВОДЫ АФРИКИ И и х И СПО ЛЬЗО ВАНИЕ 'I Б ПО Е Л •' С '*'' Г И Д р С ;.1 ‘. Т С *’ ' •H L * ГИ Р М Т О О О Ч С О Д О Е Е Р Л ГИ Е К Е ИДТЛСВ ЗАЕЬ ТО ЛЕН Н И ГРАД У Д К 5 5 1.4 8 (6 ) Ответственный редактор доктор географ ичес...»

«Руководство пользователя LPD радиостанция, модель G-225 Основные функциональные особенности • 69 каналов (433 МГц,10 мВт) • 38 CTCSS кодов • Система управления голосом • Отключение автоматического шумоподавителя • Функция вибровызова • Многофункциональный ЖК -дисплей с подсветкой • Сканирование каналов •...»

«Посудомоечные машины конвейерные WD-151E WD-421E 4246211, 4246212, 4246213, 4246214, 4246215, 4246216, 4246217, 4246218, 4219100, 4219102 Руководство по установке и эксплуатации Действительно с 01.05.2010 Перевод оригинального документа Rev. 1.0 (01.05.2010) METOS WD-151E 421E 1. Общие поло...»

«Достаточность ограничительных мер, принимаемых в отношении должника в процессе принудительного исполнения О беспечить эффективность принудительного исполнения возможно только при наличии прочной законодательной...»

«Все экскурсии проводят лицензированные русскоговорящие гиды Malta Gozo Добро пожаловать на Мальту! Вам предстоит увидеть множество достопримечательностей и открыть для себя очарование маленьких островов Мальта и Гозо с помощью наших высокопрофессиональных, лицензированных экскурсоводов. Мы стремимся удовлетворить желания и п...»

«BRICS and Developing Countries Legal Experts Forum (11th Session of the Euro-Asian Law Congress) IIIrd Coordination Committee Meeting of the BRICS Law Institute 7 10 June 2017 Organizes: Russian Association of Legal Experts BRICS Law Institute...»

«ЗАКОН О НАЛОГЕ НА ДОБАВЛЕННУЮ СТОИМОСТЬ Входит в силу от дня вхождения в силу Договора о присоединении Республики Болгарии к Европейскому союзу Обн. ГГ. 63/4 Август 2006, изм. ГГ. 86/24 Октябрь 2006, изм. ГГ. 105/22 Декабрь 2006, изм. ГГ. 108/29 Декабрь 2006, изм. ГГ. 37/8 Май 2007, изм. ГГ. 41/22 Май 2007...»

«Совершение добрых дел ради мирской выгоды ] Русский – Russian – [ Абу Ясин Руслан Маликов 2014 1435 " " 5341 4102 С именем Аллаха Милостивого Милосердного. Восхваляем Аллаха, обращаемся к Нему за помощью, просим прощения и каемся перед Ним, прибегаем к Его защите от зла наши...»

«ОРГАНИЗАЦИЯ ОБЪЕДИНЕННЫХ НАЦИЙ Distr. BET GENERAL БЕЗОПАСНОСТИ RUSSIAN ORIGINAL: ENGLISH П С М ПРЕДСЕДАТЕЛЯ СПЕЦИАЛЬНОГО КОМИТЕТА ПРОТИВ ИЬО АПАРТЕИДА ОТ 7 МАРТА 1979 ГОДА НА И Я ГЕНЕРАЛЬНОГО М СЕКРЕТАРЯ Во исполнение решения Специального комитет...»








 
2017 www.kn.lib-i.ru - «Бесплатная электронная библиотека - различные ресурсы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.